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

Seoungbin Bae; Dabeen Lee

cs.LGOct 5, 2026

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

Authors: Seoungbin Bae, Dabeen Lee

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

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.

Figures & tables

Figure 1 : Queue length regret averaged over ten runs, with $\pm 2$ sample standard deviations and $25$ -round smoothing. Columns use normalized capacity slack $\epsilon=0.05,0.1,0.15$ . Rows use pointwise, average $(q=0.15)$ , and average $(q=0.50)$ distributions, where $q=\mathbb{P}_{X\sim\mathcal{D}}(p^{*}(X)<\lambda)$ .

Explore similar work

Jun 8, 2026cs.LG

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

Stochastic Exploration

Ask PDF

May 19, 2026cs.LG

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

College of Management of Technology, EPFL · Department of Computer Science, TU Munich

Adaptive Sampling

Ask PDF

Sep 14, 2026cs.LG

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let

d

be the dimension,

K

be the menu size, and

T

the time horizon. For

2\le K\le d

, we prove an upper bound

\widetilde O(K^{1/4}\sqrt{dT})

. When

T\ge d^2

, we further prove a lower bound

Ω(K^{1/4}\sqrt{dT})

. Thus, for

T\ge d^2

and

2\le K\le d

, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on

K

is optimal. Compared with the previous

\widetilde O(\sqrt{dKT})

bound, our upper bound improves the dependence on

K

by a factor of

K^{1/4}

. For

K\ge d

, we prove an upper bound

\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)

and a lower bound

Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)

. Here,

\widetilde O_{d,T}

omits logarithmic factors only in

d

and

T

. In particular, for polynomially large

K\ge d

, the upper and lower bounds both scale as

d^{3/4}\sqrt T

up to logarithmic factors, improving the standard

\widetilde O(d\sqrt T)

rate by a factor of

d^{1/4}

. As

K

grows further, the regret smoothly recovers the

d\sqrt T

scale once

\log K

reaches order

d

Tianyuan Jin

Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)

Contextual Bandit Framework Bandits Upper Bounds Logarithmic Scaling Polynomials Action Expert

Ask PDF