Knowing how much time remains can change the best job for a scheduler to serve, even in the same queue. In an exact constructed example, job B is uniquely optimal with one round left, but job A is uniquely optimal with 14 rounds left. The difference between the two choices at the longer horizon is about 0.0021 in expected terminal queue length. The analysis reaches a sharper conclusion when the final horizon is unknown: no anytime policy can make regret converge to zero against the finite-horizon optimum, whether idling is allowed or the server must keep working.
The finding comes from a theoretical preprint about queueing decisions made while service rates are learned. The scheduler observes service outcomes and chooses which waiting job to serve or whether to idle, with queue-length regret as its objective. Regret here means the gap between the queue produced by the learning policy and the queue produced by the best finite-horizon policy when the model and horizon are known. That benchmark is defined through a Bellman recursion, a step-by-step calculation that selects the action with the lowest expected terminal queue length.
A queue that learns as it works
This is not an empirical study. It uses constructed stochastic instances with dummy, baseline and candidate jobs rather than participants or a measured operational cohort. The underlying setting is a single queue with a single server and nonpreemptive service, so a service decision cannot be revised halfway through the job. Job contexts are fed into an unknown logistic service model: each attempted service either produces a departure or does not, and the chance of departure depends on the context and an unknown parameter.
For the known-horizon case, the authors propose Learn-Clear-Plan, or LCP. It estimates the unknown model, clears the queue, and then follows a Bellman policy built from that estimate. The guarantees assume that arrival and context pairs are identically distributed across rounds, arrivals and contexts are independent, contexts and parameters are bounded, service probabilities stay within fixed bounds, and the workload is stable.
What knowing the horizon buys
Under those assumptions, LCP has a theorem-level upper bound on queue-length regret in the known-horizon, idling-allowed setting, for sufficiently large horizons and fixed model and traffic parameters. The reported asymptotic rate depends on the number of context dimensions and the amount of expected traffic over the horizon. The guarantee is about how the learning policy compares with the finite-horizon Bellman optimum, not about a measured gain in a real queue.
A lower-bound construction places that result in context. It applies to every learning policy, including randomized policies, and the paper says that, in the idling-allowed setting, the lower bound matches LCP up to polylogarithmic factors once the horizon is beyond a threshold tied to the squared dimension. In plain terms, the known-horizon guarantee is close to the best worst-case rate available within the model, apart from slowly growing logarithmic factors.
The small Bellman example shows why a single policy cannot simply ignore the clock. With one round remaining, B is uniquely optimal. With 14 rounds remaining, A is uniquely optimal instead. At 14 rounds, the action-value difference is approximately 0.0021 in expected terminal queue length. The example is theoretical, but it makes the horizon dependence concrete: the best immediate choice can change when future arrivals have more time to affect the queue.
When there is no final time
That dependence creates the paper’s unknown-horizon barrier. An anytime policy must operate without knowing the horizon at which it will be evaluated. Even if the service model is fully known, the paper shows that no anytime policy can make regret converge to zero against the finite-horizon optimum in either the idling-allowed or work-conserving setting. The obstacle is the moving target created by horizon-dependent optimal actions.
Because the finite-horizon optimum cannot be tracked by an anytime policy, the paper uses true SEPT as a fixed, horizon-independent reference. SEPT serves the waiting job with the highest departure probability. Its learning version, estimated-SEPT, updates its estimate only between busy periods, keeps that estimate fixed through the next busy period, and applies the corresponding priority rule. For fixed model and traffic parameters, estimated-SEPT is reported to have a vanishing tracking error against true SEPT, with a rate involving model dimension and inverse time. This does not establish that SEPT is optimal in the finite-horizon model.
A theoretical boundary, not a deployment result
The evidence has a narrow scope. The guarantees depend on the stated i.i.d., boundedness, logistic-model and workload-stability assumptions, and the analysis is limited to a single-server theoretical queue. No empirical evaluation, external validation or real-world deployment analysis is reported. The instances are constructed stochastic examples, not a participant sample or an operational data set.
The manuscript is an arXiv version-one preprint dated 29 September 2026. Its contribution is a set of boundaries for learning in nonpreemptive queues: when the horizon is known, LCP is reported as near-optimal up to polylogarithmic factors; when the horizon is unknown, zero regret against the finite-horizon optimum is not available to any anytime policy under the stated assumptions.
Paper data and sources
Original title: Nonpreemptive Scheduling While Learning Context-Dependent Service Rates
Authors: Wansoo Choi, Seoungbin Bae, Dabeen Lee
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-09-29
DOI: Not available
Original paper · Full text