Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

Wansoo Choi; Seoungbin Bae; Dabeen Lee

cs.LGSep 29, 2026

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

Authors: Wansoo Choi, Seoungbin Bae, Dabeen Lee

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

Abstract

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.

Figures & tables

Setting	Benchmark / Objective	Result	Note
Known $T$ , IA	Regret against optimal IA	$\widetilde{O}(\sqrt{d/T})$	Algorithm 1 , Theorem 1
Known $T$ , IA/WC	Regret against optimum	$\Omega(\min\{d^{-1/2},\sqrt{d/T}\})$	Theorem 2
Unknown, IA/WC	Vanishing regret against finite-horizon optimum	Impossible: $\limsup_{t\to\infty}R_{t}^{\mathsf{S}}(\pi)>0$	Theorem 3
Unknown, WC	Tracking true SEPT	$\widetilde{O}(\sqrt{d/t})$	Algorithm 2 , Theorem 4

Table 1: Summary of main results. Known/unknown indicates whether the server knows the horizon; IA/WC denote the idling-allowed/work-conserving settings, and SEPT denotes the shortest-expected-processing-time policy. Logarithmic factors and fixed model constants are suppressed.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: The final four-round construction used in the lower-bound proof. Solid vertical lines mark round boundaries, and dashed lines separate service from the end-of-round arrival. The shaded region corresponds to $\mathcal{H}$ ; the candidate- $j$ arrival is appended afterward.

Queueing Theory

See all 18 papers

Oct 5, 2026

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

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.

Seoungbin Bae, Dabeen Lee

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

Multi-Armed Bandits Contextual Bandits Generalized Linear Bandits Queueing Theory

Ask PDF

Jun 8, 2026

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve

\widetilde{\mathcal{O}}(T^{-1/4})

queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon

T

. In this paper, we improve this rate to

\widetilde{\mathcal{O}}(T^{-1/2})

. The key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-

η

-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii)

η

-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length regret of order

\widetilde{\mathcal{O}}(T^{-1/2})

. We further prove a minimax lower bound of order

Ω(T^{-1/2})

. The proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon

T

up to logarithmic factors.

Seoungbin Bae, Dabeen Lee

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

Exploration-Exploitation Tradeoff Regret Minimization Contextual Bandits UCB Algorithms Queueing Theory

Ask PDF

Feb 2, 2026

Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits

Explosive demands for LLMs often cause user queries to accumulate in server queues, requiring efficient routing (query-LLM matching) and scheduling (query prioritization) mechanisms. Several online algorithms are being deployed, but they overlook the following two key challenges inherent to conversational LLM services: (1) unsatisfied users may retry queries, increasing the server backlog, and (2) requests for

explicit" feedback, such as ratings, degrade user experiences. In this paper, we develop a joint routing and scheduling algorithm that leverages

implicit" feedback inferred from user retrial behaviors. The key idea is to propose and study the framework of contextual queueing bandits with multinomial logit feedback (CQB-MNL). CQB-MNL models query retrials, as well as context-based learning for user preferences over LLMs. Our algorithm, anytime CQB (ACQB), achieves efficient learning while maintaining queue stability by combining Thompson sampling with forced exploration at a decaying rate. We show that ACQB simultaneously achieves a cumulative regret of

\widetilde{\mathcal{O}}(\sqrt{t})

for routing and a queue length regret of

\widetilde{\mathcal{O}}(t^{-1/4})

for any large

t

. For experiments, we refine query embeddings via contrastive learning while adopting a disjoint parameter model to learn LLM-specific parameters. Experiments on synthetic data, offline routing datasets (SPROUT, EmbedLLM, and RouterBench), and real user conversation logs (WildChat-1M) confirm that our methods improve routing, scheduling, and queue stability against strong online and offline-trained baselines.

Seoungbin Bae, Junyoung Son, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Graduate School of Data Science, KAIST · Department of Mathematical Sciences, Seoul National University

LLM Serving LLM Routing Contextual Bandits LLM Request Scheduling

Ask PDF

Abstract

Queueing Theory

Explore similar work

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

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits