acceptodds
Under review as a conference paper at ICLR 2027

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

Abstract

We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a -dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution , 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 queue-length regret, while a lower-bound construction gives regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when . 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 without knowing the model.

Primary area:
reinforcement learning
Keywords:
Queueing bandits, Contextual bandits, Logistic bandits, Nonpreemptive scheduling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_VZoTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies contextual queueing bandits under nonpreemptive service, where a selected job must continue to be served until completion and its service rate depends on an unknown contextual logistic model. Unlike the preemptive setting, the optimal scheduling decision can depend on both the current queue state and the remaining horizon, so a simple priority rule is generally insufficient. For the known-horizon setting, the authors propose a LPC algorithm, which first learns the service model, clears the queue, and then follows an estimated finite-horizon bellman policy. They establish a near-optimal queue-length regret guarantee together with a matching lower bound up to logarithmic factors. For the unknown-horizon setting, the paper proves that no horizon-independent policy can achieve vanishing regret against the finite-horizon optimum. Motivated by this impossibility result, the authors instead use SEPT as a fixed benchmark and propose an estimated-SEPT algorithm that provably tracks it at a diminishing rate.

Critical strengths
  1. The problem is natural and the structural point is made cleanly. Nonpreemption is the realistic constraint in many systems.

  2. The analysis is complete and the lower bound handles both work-conserving policies and policies that may idle.

  3. The assumptions are weaker than in the preemptive prior work. The analysis needs only the L1L^1 error of the fitted departure probabilities, so no lower bound on the context covariance is required, and the workload condition ρ<1\rho<1 replaces the pointwise traffic-slack condition.

Critical weaknesses
  1. The regret notion removes the learning–scheduling trade-off, and the paper does not acknowledge this. Only the last O(log⁡T)O(\log T) rounds affect E[QT+1]\mathbb E[Q_{T+1}] because of the exponential workload tails (this is the ψ(r)H\psi(r)^H term in (8)), so Learn–clear–plan can serve FCFS for T−log⁡2TT-\log^2T rounds at no cost. Every served job also gives an unbiased sample regardless of the scheduling order, so there is no exploration problem at all, and learning is plain supervised regression on Θ(λT)\Theta(\lambda T) i.i.d. samples. The d/T\sqrt{d/T} rate is the parametric estimation rate times a polylog planning window. The sentence "making learning and planning fundamentally intertwined" on page 2 is not supported by the analysis.

  2. The planner is quasi-polynomial and nothing practical is offered.

  3. The lower bound covers both IA and WC, but the upper bound is only against the IA optimum, and Lemma 6 (which the proof of Theorem 1 needs) is proved only for policies that may idle, so the WC upper bound is open and Table 1 should say so.

Questions for authors
  1. Is SEPT average-cost optimal in your model among nonpreemptive work-conserving policies, as the cμc\mu rule is for M/G/1?

  2. Do you agree that under the terminal queue-length objective there is no exploration problem and the learning phase is free? What changes under a cumulative objective, and do the workload coupling and the planning-transfer lemma still give a bound there?

  3. What is the practical version of Learn–clear–plan?

5 comments

[CW1] The regret notion removes the learning--scheduling trade-off, and the paper does not acknowledge this. Only the last O(log⁡T)O(\log T) rounds affect E[QT+1]\mathbb{E}[Q_{T+1}] because of the exponential workload tails (this is the ψ(r)H\psi(r)^H term in (8)), so Learn--clear--plan can serve FCFS for T−log⁡2TT-\log^2 T rounds at no cost. Every served job also gives an unbiased sample regardless of the scheduling order, so there is no exploration problem at all, and learning is plain supervised regression on Θ(λT)\Theta(\lambda T) i.i.d. samples. The d/T\sqrt{d/T} rate is the parametric estimation rate times a polylog planning window. The sentence ``making learning and planning fundamentally intertwined'' on page 2 is not supported by the analysis.

We thank the reviewer for this important observation. We agree that the conventional exploration--exploitation trade-off is absent in our single-server IA setting. In particular, FCFS allows us to collect i.i.d. first-attempt observations without deliberately selecting less efficient scheduling actions for exploration.

Nevertheless, our framework can also be extended to the multi-server setting, where the exploration--exploitation trade-off becomes more explicit. In this setting, the scheduler must learn the unknown service probabilities associated with different servers. Since the selected server determines both the service efficiency and the information obtained from departure feedback, learning these probabilities may require assigning jobs to less efficient servers, potentially increasing the workload during exploration. In this sense, the multi-server setting exhibits precisely the learning–scheduling trade-off (exploration–exploitation trade-off) highlighted by the reviewer.

However, the central difficulty addressed in our paper is nonpreemptive scheduling and its queue-length regret analysis. Even when the service model is fully known, nonpreemption makes optimal scheduling decisions depend on the queue state and the remaining horizon, rather than a simple myopic rule. This fundamental scheduling difficulty already arises in the single-server setting, which motivated us to focus on that setting in our main analysis.

To further demonstrate the applicability of our approach, we have now included a multi-server extension in Appendix J. The extension combines round-robin exploration, learned server selection, workload reduction, and empirical Bellman planning, yielding a terminal queue-length regret bound of O~(Kd/(λT))\widetilde O(K\sqrt{d/(\lambda T)}).

Regarding the statement that learning and planning are fundamentally intertwined, we would like to explain our original intention. Unlike in the preemptive setting, an optimal nonpreemptive scheduling policy generally cannot be characterized by a simple myopic rule. Instead, it can be characterized by a finite-horizon Bellman recursion. Since the true service-probability function and its distribution are unknown, a natural approach is to first estimate these quantities and then make scheduling (planning) decisions using an empirical Bellman recursion that approximates the true one.

However, determining when to transition from learning to planning requires careful analysis. Under nonpreemption, each job may occupy the server for multiple rounds, so an insufficient learning period may fail to provide enough observations for accurate estimation. Conversely, learning for too long leaves fewer rounds to follow the optimal actions determined by the empirical Bellman recursion. Our analysis combines workload, concentration, sample-availability, and planning-transfer bounds to carefully choose the learning length LL and the clearing–planning window H=T−LH=T-L and obtain a near-optimal regret guarantee. This necessary coordination between learning and planning is what we intended by "fundamentally intertwined," rather than a conventional exploration–exploitation trade-off. We will revise the sentence to clarify our intended meaning and avoid potential misunderstandings.

[CW2] The planner is quasi-polynomial and nothing practical is offered.

[QA3] What is the practical version of Learn--clear--plan?

We agree that the quasipolynomial complexity of the original empirical Bellman planner limits its practical applicability. To address this issue, we have developed variants of LCP whose total computational work is polynomial in TT, while retaining regret guarantees that vanish as T→∞T\to\infty (Appendix K).

First, Theorem 8 establishes a deterministic polynomial-work algorithm achieving RT≤Cexp⁡(−clog⁡(eT))R_T\le C\exp(-c\sqrt{\log(eT)}) for some constants C,c>0C,c>0. The key idea is to restrict the number of distinct success-probability labels in the empirical distribution used for Bellman planning. Specifically, we choose M=⌈exp⁡(log⁡(eT))⌉M=\lceil\exp(\sqrt{\log(eT)})\rceil equally spaced grid points in [p−,p+][p_-,p_+] and round each estimated success probability to its nearest grid point. The empirical distribution used for planning is then constructed from these rounded probabilities, so its support contains at most MM values.

With the Clear–Plan window set to H=⌈log⁡(eT)⌉H=\lceil\sqrt{\log(eT)}\rceil, the resulting Bellman recursion has a polynomial number of states and requires polynomial total arithmetic work. Moreover, each rounding error is at most O(1/M)O(1/M), which contributes only O(H2/M)O(H^2/M) to the regret bound through the modified planning-transfer analysis. Combining this with the original estimation and workload bounds yields the stated vanishing regret rate.

We also develop a randomized multilevel planning algorithm (Theorem 9), which approximates Bellman action values with errors controlled through Lemma 22. It achieves polynomial total computational work and $ R_T \le C\exp\left( -\frac{c\log(eT)}{\Lambda(\log(eT))} \right)$, where $\Lambda(z)=1+\log\log(e^2+z) $. Detailed algorithms and proofs are provided in Appendices K.2--K.3.

In addition to these theoretical developments, our numerical experiments suggest that, among the three algorithms developed in this work(LCP, SEPT+LCP, and estimated-SEPT) estimated-SEPT achieves particularly favorable performance in terms of terminal and time-average queue lengths, comparable to SEPT+LCP and considerably better than original LCP. Moreover, unlike SEPT+LCP, estimated-SEPT requires no computationally expensive Bellman planning, making it a promising and computationally efficient alternative for practical use. However, these findings are based on numerical experiments, and it remains theoretically unknown whether estimated-SEPT's terminal regret against VTIAV_T^{\mathrm{IA}} or VTWCV_T^{\mathrm{WC}} vanishes as T→∞T\to\infty.

[CW3] The lower bound covers both IA and WC, but the upper bound is only against the IA optimum, and Lemma 6 (which the proof of Theorem 1 needs) is proved only for policies that may idle, so the WC upper bound is open and Table 1 should say so.

We thank the reviewer for pointing out this gap. We have developed a work-conserving LCP (WC-LCP) algorithm that achieves O~(d/(λT))\widetilde O(\sqrt{d/(\lambda T)}) regret against the optimal WC policy (Theorem 6). WC-LCP retains the original Learn–Clear–Plan structure but uses the WC Bellman recursion, which excludes idling when jobs are waiting (Section 4.2, Eq. (7), with the idling action removed as specified in Appendix I.1). We have also updated Table 1 to include this new WC regret upper bound.

As the reviewer correctly observes, Lemma 6 cannot be directly applied to the WC setting. We overcome this difficulty using a common-workload coupling (Lemma 17). Since both WC-LCP and the optimal WC policy are work-conserving, coupling their arrivals, contexts, and service requirements ensures that their workload processes are identical. Consequently, both queues become empty at exactly the same times.

In particular, if WC-LCP clears its queue with hh rounds remaining, the optimal WC policy is also at an empty state. Conditional on this common empty start, their expected terminal queue-length difference is $ J_h^p(\hat\pi)-V_h^{\mathrm{WC}}, $ where π^\hat\pi denotes the empirical WC Bellman policy. Indeed, from this common empty state, the optimal WC policy follows an optimal policy for the remaining hh rounds, whereas WC-LCP enters its Plan phase and follows π^\hat\pi. We can therefore apply the planning-transfer bound (Lemma 4) directly, without invoking Lemma 6. Combining this with the workload and concentration bounds yields the stated regret guarantee.

Reviewer_g1xSOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a single server queueing system where each job arrives with a visible context x. There is a common latent \theta^, which determines the service rate of the queue (depends on a non-linear transformation of (\theta^)^T x into a Bernoulli parameter, and the service time is geometric with this Bernoulli parameter). Such problems have been studied over the last decade. The new aspect here is to study non-preemptive service, where a job once scheduled to the server, continues to be served until it departs. The difficulty in this setting is that a work-conserving policy is no longer optimal, so the regret baseline is not easy to establish.

The authors establish to optimal scheduling (if \theta^* was known) using a dynamic program. This then drives their algorithm, which effectively learns the parameter specifically, learns the empirical dist of p(x)), solves the Bellman problem with this learned param, and schedules using certainty equivalence. They show a regret upper bound with scale as 1/\sqrt{T}, along with a worst-case lower bound.

Critical strengths

This is a new variant of the queueing bandit with non-preemption which is arguably a more realistic setting that assuming preemption. This brings up difficulties in establishing the baseline in closed form, because of which there is need to use a MDP. The paper is “clean” in the sense that the upper and matching lower bounds are provided.

Critical weaknesses

A few weaknesses are (i) The algorithm is not surprising, meaning estimate the parameters of the learning-free optimal (the MDP). Also, the proof approach seems standard (specifically, it appears that the usual concentrations using DKW need to be established for the learning problem leading to Lemma 2). (ii) The worst-case bound is order 1/\sqrt{T} and the achievability is of a similar scale. However, the upper bound is not the worst-case. I wonder if 1/T is possible in this setting (the original queueing bandits had this sharper rate). (iii) It would be nice to think about the multi-server version of this problem.

Questions for authors

I would be interested in knowing the authors thoughts on the three weakness comments above. I am happy to reconsider my review based on their response.

3 comments

[CW1] The algorithm is not surprising, meaning estimate the parameters of the learning-free optimal (the MDP). Also, the proof approach seems standard (specifically, it appears that the usual concentrations using DKW need to be established for the learning problem leading to Lemma 2).

We agree with the reviewer that LCP has a relatively simple algorithmic structure. However, our main novelty lies in developing the theoretical tools needed to establish its near-optimal regret guarantee, and in designing the algorithm based on these results.

First, we establish a planning-transfer bound (Lemma 4). LCP constructs an empirical Bellman policy by treating the estimated success-probability function and distribution as the true model. We prove that the gap between the expected terminal queue length under this policy and the true optimal value can be controlled by the estimation errors: the L1L^1 prediction error of the success-probability function and the Wasserstein error of the estimated distribution. This allows us to control the regret incurred during planning when the model is learned accurately. To establish this bound, we develop value-function comparison and service-time coupling arguments (Lemmas 7–8 and Eq. (33)).

Second, we develop a workload-based analysis (Lemma 1). Directly analyzing departures under nonpreemptive scheduling is challenging because they depend on the scheduling decisions. Instead, we use a workload process independent of the service order under work-conserving policies. Its exponential bounds allow us to control the terminal-regret contribution of unsuccessful clearing, without directly analyzing the complicated departure process.

Combining these results with statistical concentration bounds yields the explicit regret guarantee in Theorem 1. We then carefully choose the Learn length L and Clear–Plan window H to obtain O~(d/(λT))\widetilde{O}(\sqrt{d/(\lambda T)}) regret.

Thus, the near-optimal regret guarantee does not directly follow from the standard approach of learning unknown parameters and distributions and then applying concentration inequalities. Instead, establishing this guarantee requires combining these ingredients with the planning-transfer and workload analyses developed in this work.

[CW2] The worst-case bound is order 1/T1/\sqrt{T} and the achievability is of a similar scale. However, the upper bound is not the worst-case. I wonder if 1/T1/T is possible in this setting (the original queueing bandits had this sharper rate).

We thank the reviewer for raising this question. The O~(1/T)\widetilde O(1/T) queue-length regret rate in the original queueing bandit literature (Krishnasamy et al., 2016 [1]; 2021 [2]) is established in a different setting, where a fixed positive optimality gap separates the best server from the others. This gap allows sufficiently accurate estimates to identify the optimal server, while queue-regeneration arguments yield the faster regret rate.

In contrast, our setting considers nonpreemptive scheduling of context-dependent jobs without any positive optimality-gap assumption. Theorem 2 establishes $ R_T=\Omega\left(\min\left\{1/\sqrt d,\sqrt{d/T}\right\}\right), $ even when the context distribution is known to the learner, while the parameter θ∗\theta^\ast remains unknown. Thus, a worst-case O(1/T)O(1/T) regret guarantee is impossible under our assumptions, and our upper bound matches this lower bound up to polylogarithmic factors for T≥d2T\ge d^2.

The absence of an optimality-gap assumption also necessitates a different analytical approach. Unlike previous gap-dependent settings, our setting does not impose an optimality-gap condition, so such identification-based arguments are not applicable. Instead, we establish a planning-transfer bound (Lemma 4) that directly controls the difference in expected terminal queue length using only the L1L^1 prediction error and the Wasserstein error of the estimated distribution, without requiring the uniform prediction-error bounds used in earlier gap-dependent queueing bandit analyses. Combined with our workload analysis, this yields a near-optimal regret guarantee under more general, gap-free assumptions.

Finally, closing the remaining polylogarithmic gap or obtaining faster instance-dependent rates under additional gap assumptions would be interesting directions for future work.


[1] Krishnasamy et al., Regret of Queueing Bandits, NeurIPS, 2016.

[2] Krishnasamy et al., Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach, Operations Research, 2021.

[CW3] It would be nice to think about the multi-server version of this problem.

We thank the reviewer for suggesting this natural and important extension. We have now included a multi-server extension of LCP in Appendix J, considering the nonpreemptive multi-server framework of Bae and Lee (2026b) [1], where there are KK selectable servers but at most one job--server pair can be active at a time. The success probability of serving job xx on server kk is given by p(x,k)=μ(ϕ(x,k)⊤θ⋆)p(x,k)=\mu(\phi(x,k)^\top\theta^\star), where ϕ(x,k)\phi(x,k) is the observable job--server feature vector and θ⋆\theta^\star is unknown.

Our extension relies on two key observations. First, the multi-server IA problem reduces to a single-server IA problem. Specifically, there exists an optimal policy that, whenever it chooses to serve a job xx, assigns it to a server maximizing p(x,k)p(x,k). Thus, defining p⋆(x)=max⁡k∈[K]p(x,k)p^\star(x)=\max_{k\in[K]}p(x,k), the single-server Bellman recursion constructed from (p⋆,Fp⋆)(p^\star,F_{p^\star}), where Fp⋆=Law⁡(p⋆(X))F_{p^\star}=\operatorname{Law}(p^\star(X)), yields exactly the same minimum expected terminal queue length as the optimal multi-server IA policy. Consequently, the planning phase of LCP can be extended by approximating this Bellman recursion using estimated service probabilities and their distribution.

Second, we establish prediction-error bounds for an estimated server-selection rule. During the initial learning phase, jobs are selected according to FCFS and assigned to servers in a round-robin manner, providing n/Kn/K observations per server from a total of nn observations. Applying the estimation bound underlying Lemma 2 separately to each server, we construct estimates p^n,k(x)\hat p_{n,k}(x) of p(x,k)p(x,k) and define q(x)=max⁡k∈[K]p^n,k(x),k^(x)∈arg⁡max⁡k∈[K]p^n,k(x)q(x)=\max_{k\in[K]}\hat p_{n,k}(x), \hat k(x)\in\arg\max_{k\in[K]}\hat p_{n,k}(x). We then obtain high-probability prediction-error bounds of the form E∣p⋆(X)−q(X)∣=O~(Kd/n),E[p⋆(X)−p(X,k^(X))]=O~(Kd/n)\mathbb E|p^\star(X)-q(X)|=\widetilde O\left(K\sqrt{d/n}\right), \mathbb E[p^\star(X)-p(X,\hat k(X))]=\widetilde O\left(K\sqrt{d/n}\right).

These bounds are useful in two important ways. First, they allow us to approximate the Bellman recursion based on (p⋆,Fp⋆)(p^\star,F_{p^\star}), extending the planning-transfer analysis of Lemma 4 to the multi-server setting. Second, under the natural traffic-slack condition ρ⋆=λE[1/p⋆(X)]<1\rho^\star =\lambda\mathbb E[1/p^\star(X)] < 1, the same prediction-error bounds ensure that the learned server-selection rule k^\hat k yields a stable queue with high probability once sufficiently many observations have been collected, satisfying λE[1/p(X,k^(X))]<1\lambda\mathbb E[1/p(X,\hat k(X))] < 1.

Based on these observations, our multi-server LCP algorithm first explores the servers through round-robin assignments, then uses the learned server-selection rule to reduce the workload accumulated during exploration, and finally performs empirical Bellman planning after clearing the queue. Combining these ingredients with the workload and planning-transfer analyses establishes O~(Kd/(λT))\widetilde O(K\sqrt{d/(\lambda T)}) terminal queue-length regret against the finite-horizon multi-server IA optimum.

We have included the problem setting, algorithm, main theoretical results, and proof outlines in Appendix J.


[1] Bae and Lee, Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm, arXiv:2610.06006, 2026.

Reviewer_mrn8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a stable single-server queue with iid arrivals and job contexts. Service success probabilities follow an unknown logistic model, and service is nonpreemptive: once a job starts, it must continue until completion. Performance is measured by expected terminal queue length relative to a model-aware, horizon-aware, nonanticipating oracle. The paper distinguishes idling-allowed (IA) and work-conserving (WC) policies.

The main contributions are:

  • Known-horizon learning: Learn-Clear-Plan first collects contextual service observations, waits for the queue to clear, and then uses a learned finite-horizon Bellman policy. It achieves IA terminal regret O~(d/(λT))\widetilde O(\sqrt{d/(\lambda T)}) without a feature-covariance lower bound (Theorem 1).
  • Lower bound: Theorem 2 proves Ω(min⁡d−1/2,d/T)\Omega(\min{d^{-1/2},\sqrt{d/T}}) for both policy classes. With fixed traffic/model constants, it matches the IA upper bound in d,Td,T, up to logarithms, when T≥d2T\ge d^2.
  • Horizon dependence and anytime learning: The paper establishes horizon-dependent optimal actions and fixed instances with a positive regret limsup for every anytime policy, even with a known model (Proposition 1; Theorem 3). Estimated shortest-expected-processing-time (SEPT) scheduling instead achieves vanishing tracking error relative to SEPT (Theorem 4).
  • Technical contribution: Workload coupling and busy-period regeneration control scheduling dependence, while prediction-error analysis avoids full parameter identification.
Critical strengths

The idea of avoiding a job with the highest probability of departure is very interesting.

Critical weaknesses
  • There are no performance experiments. Consequently, practical speed, scalability, or empirical superiority is not demonstrated. In addition, the paper mentions an accompanying exact-fraction script, but it was not supplied, and no repository was linked.

  • LCP has an upper bound of exp⁡(O(log⁡3T))\exp(O(\log^3 T)) Bellman-term evaluations, which is quasi-polynomial. Practical scalability, numerical bit complexity, and approximate-planning error are not analyzed (Theorem 1; E.2).

Questions for authors
  • local formula overflow: Four appendix displays extend beyond the official text width: p. 30, Eq. (44); p. 32, line 1690; p. 37, Eq. (53); and p. 41, Eq. (62).

  • conditional independence (p. 19, lines 994-1000): The wording suggests unconditional independence of terminal cost from the learning history.

  • computational necessity (p. 4, lines 171-175): Horizon dependence does not prove that every exact method must recompute the displayed Bellman recursion.

  • (Appendix E.2, p. 21, lines 1113–1117): The per-state Bellman successor count omits success/failure continuations. A factor-two correction preserves the quasi-polynomial complexity order.

  • (Appendix F.2, p. 27, lines 1436–1447): The displayed Bernoulli KL expansion has reversed orientation, and the Taylor expansion interval requires correction.

  • (Appendix F.5, p. 33, line 1758): An equality between the full expectation and an event-restricted expectation should be replaced by an inequality (≥\ge).

  • (Appendix G.3, p. 37, line 1992): The regret term inside sup⁡i≥s\sup_{i\ge s} incorrectly uses subscript ss instead of ii.

4 comments

[CW1] There are no performance experiments. Consequently, practical speed, scalability, or empirical superiority is not demonstrated. In addition, the paper mentions an accompanying exact-fraction script, but it was not supplied, and no repository was linked.

We thank the reviewer for pointing out the lack of empirical evaluation. We have added numerical experiments comparing six scheduling policies in Section 6: FCFS, random-idle, original LCP, SEPT+LCP, estimated-SEPT, and true SEPT. Among these, SEPT+LCP is a newly developed algorithm presented in Appendix L. It replaces FCFS scheduling in the Learn and Clear phases of the original LCP algorithm with busy-period estimated-SEPT, while retaining empirical Bellman planning in the final phase. We establish that this algorithm achieves O~(dT/λ)\widetilde O(\sqrt{dT/\lambda}) cumulative queue-length regret and O~(d/(λT))\widetilde O(\sqrt{d/(\lambda T)}) terminal queue-length regret, both against the respective finite-horizon IA-optimal benchmarks. We have included the SEPT+LCP algorithm, its theoretical guarantees, and the corresponding proofs in Appendix L. We will also incorporate these results into the main text in the revised version of the paper.

We consider three single-server instances: five contexts with d=10d=10 and ten paired replications, ten contexts with d=10d=10 and five replications, and twenty contexts with d=5d=5 and four replications. In each instance, the traffic intensity is fixed at ρ=0.97\rho=0.97. For each horizon T=20,40,…,2000T=20,40,\ldots,2000, we compute the empirical averages of the terminal queue length and the time-average queue length over the prescribed replications and plot these averages against TT, together with pointwise 95% Student-tt confidence intervals.

For LCP and SEPT+LCP, we use exact empirical-model Bellman planning in the five-context experiment. However, as the number of contexts increases, exact Bellman planning becomes computationally expensive. Therefore, in the ten- and twenty-context experiments, we instead use an adaptive compressed-state Bellman approximation, with a numerical acceptance threshold of 0.1 for the fitted-model planning loss. This practical approximation is motivated by, but is not identical to, the polynomial-work approximate-planning methods theoretically analyzed in Appendix K.

Table 1 summarizes the empirical mean terminal queue lengths of the six policies at T=2000T=2000.

Table 1: Empirical mean terminal queue lengths at T=2000T=2000.

Policy5 contexts10 contexts20 contexts
FCFS28.7026.6044.25
Random-idle31.2031.2042.75
LCP28.2026.4044.25
SEPT+LCP14.706.406.00
True SEPT9.006.606.00
Estimated-SEPT14.606.606.00

As shown in Table 1, among the evaluated learning-based policies, SEPT+LCP and estimated-SEPT achieve considerably lower empirical mean terminal queue lengths than original LCP in these instances. True SEPT, which knows the service probabilities, serves as a full-information benchmark. These experiments do not establish uniform empirical superiority or independently validate the theoretical regret guarantees, since the reported queue lengths are not estimates of regret against the uncomputed finite-horizon IA optimum.

Regarding practical speed, we measured the actual execution times and memory usage of the implementations described above, including approximate Bellman planning in the larger instances. The following table reports the average recorded execution times per successful simulation of LCP at four different horizons.

Table 2: Mean recorded LCP execution times (ms).

Horizon TT5 contexts10 contexts20 contexts
500151.0520.172582.787
10002635.9795.0771703.505
15005974.451237.0710.841
2000170.841651.9602588.883

Regarding practical scalability, the recorded execution times do not exhibit a consistent trend as the horizon TT increases. This variability arises partly because the computational cost depends strongly on whether LCP enters the Plan phase and on the actual planning horizon. In our experiments, not all simulation runs reached the Plan phase, making it difficult to reliably compare the computational costs of Bellman planning across different horizons. Consequently, the present measurements do not establish a reliable scaling relationship with respect to TT. Separately, LCP and SEPT+LCP shared Bellman caches, allowing previously computed results to be reused to reduce computational time. In particular, this reuse helped avoid excessively long execution times for SEPT+LCP. Therefore, the recorded execution times do not necessarily reflect the computational costs of independent runs without cache reuse. In future work, we plan to develop more controlled experimental procedures to systematically evaluate the practical scalability of these algorithms with respect to the horizon TT, the number of contexts, and other relevant problem parameters.

Detailed experimental results, implementation procedures, execution times for all six policies across the evaluated horizons, Bellman-worker memory measurements, additional computational statistics, and their limitations are provided in Section 6 and Appendix M.

Regarding the missing exact-fraction verification script mentioned in CW1, we will provide the verification script and the associated computational certificate for Proposition 1 as supplementary material, allowing the reported calculation to be independently checked.

[CW2] LCP has an upper bound of exp⁡(O(log⁡3T))\exp(O(\log^3 T)) Bellman-term evaluations, which is quasi-polynomial. Practical scalability, numerical bit complexity, and approximate-planning error are not analyzed (Theorem 1; E.2).

We thank the reviewer for highlighting these computational limitations. We agree that the original LCP algorithm requires quasipolynomially many Bellman-term evaluations. To address this issue, we have developed polynomial-work variants of LCP with vanishing regret guarantees in Appendix K.

First, we extend the planning-transfer bound to approximate Bellman policies (Lemma 21). Specifically, if the expected suboptimality of the selected Bellman action is at most djd_j with jj rounds remaining, uniformly over all reachable states and planning histories, then approximate planning adds at most ∑j=1Hdj\sum_{j=1}^{H}d_j to the regret bound. Thus, approximate-planning errors can be explicitly incorporated into the original regret analysis.

Based on this result, we develop two polynomial-work algorithms. Theorem 8 establishes a deterministic method that rounds estimated success probabilities to a fixed grid of M=⌈exp⁡(log⁡(eT))⌉M=\lceil\exp(\sqrt{\log(eT)})\rceil points and performs exact Bellman planning on the resulting compressed model. With H=⌈log⁡(eT)⌉H=\lceil\sqrt{\log(eT)}\rceil, the rounding error contributes at most O(H2/M)O(H^2/M) to regret, while the total computational work remains polynomial in TT. Consequently, RT≤Cexp⁡(−clog⁡(eT))R_T\le C\exp(-c\sqrt{\log(eT)}).

Theorem 9 develops a randomized multilevel planner that approximates Bellman action values. Lemma 22 controls its approximation errors, and Lemma 21 translates these into a regret bound. The resulting algorithm achieves polynomial total work and RT≤Cexp⁡(−clog⁡(eT)Λ(log⁡(eT)))R_T\le C\exp\left(-\frac{c\log(eT)}{\Lambda(\log(eT))}\right), where Λ(z)=1+log⁡log⁡(e2+z)\Lambda(z)=1+\log\log(e^2+z). Detailed constructions and proofs are provided in Appendices K.1–K.3.

Finally, we clarify that our polynomial-work guarantees count elementary arithmetic and sampling operations, including the planning computations. They do not establish polynomial numerical bit complexity for arbitrary real-valued inputs, which would require a separate finite-precision analysis.

[QA] Responses to Questions for Authors

We sincerely thank the reviewer for carefully identifying these issues. We have revised the manuscript to address all seven points raised in the Questions for Authors.

First, we have corrected all four instances of formula overflow, the reversed orientation and Taylor expansion interval in the Bernoulli KL expansion (Appendix F.2), the incorrect equality in Appendix F.5, and the incorrect subscript in Appendix G.3.

Second, regarding the Bellman successor count in Appendix E.2, we thank the reviewer for pointing out that the original proof did not account for the success/failure continuations. We have corrected the proof accordingly. The resulting per-state successor bound is twice the previously stated bound, but this correction does not change the quasi-polynomial complexity order.

Third, regarding conditional independence, we have clarified the statement in the revised manuscript (lines 1064–1068). Specifically, conditional on the history available at the beginning of the first empty round, future arrivals and contexts are independent of that history. However, subsequent departure indicators need not be independent of it, since scheduling decisions depend on the empirical Bellman policy constructed from the learning data.

Finally, regarding computational necessity, we have revised the statement (lines 185–188) to clarify that determining an optimal action generally requires accounting for the current queue state and the remaining horizon, and that the finite-horizon Bellman recursion provides an exact characterization of such optimal actions. We no longer claim that every exact method must recompute this recursion.

We greatly appreciate the reviewer's careful reading and constructive comments, which have helped us improve the correctness and clarity of the manuscript.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Author Response Summary and Updated Manuscript

We sincerely thank all three reviewers for their careful evaluations and constructive feedback.

We have now provided detailed responses to all comments and questions raised by the reviewers. We have also uploaded a revised version of our manuscript and updated supplementary materials incorporating the new results and revisions discussed in our responses.

The main updates include:

  • New theoretical extensions to work-conserving and multi-server settings.
  • Polynomial-work variants of LCP with vanishing regret guarantees.
  • New cumulative queue-length regret bounds and the SEPT+LCP algorithm.
  • Numerical experiments comparing six scheduling policies, together with practical computational performance analyses.
  • Corrections and clarifications addressing the technical and presentation issues identified by the reviewers.

Further details, including the relevant theorem statements, proofs, and locations of the revisions, are provided in our individual responses to each reviewer.

We greatly appreciate the reviewers' and Area Chair's time and consideration, and we welcome any further questions or comments.

Thank you for your thoughtful follow-up and for recognizing the improvements in our revised manuscript. We appreciate your remaining concerns about practical scalability and would like to clarify the theoretical scope of Appendix K while providing a more explicit complexity analysis.

1. Explicit computational complexity. We have further analyzed the arithmetic work required for Bellman planning in the two algorithms of Appendix K. For the deterministic grid method (Section K.2), we obtain

\le C H^2M^3\binom{H+M}{M} = T^{1-o(1)}.$$ as an asymptotic upper bound. For randomized multilevel planning (Section K.3), a refined analysis of the recursive computation using the shared-table implementation gives $$W_{\mathrm{MLMC}}(T) \le C H^5 2^H 8^{k_0} \binom{k_0+2H}{2H} = T^{3+o(1)}.$$ These are planning arithmetic-work upper bounds, rather than measured running times or complete end-to-end complexity bounds. We have derived these bounds by explicitly counting the states, transitions, and recursive computations required by the respective Bellman planners, and have incorporated the detailed derivations into Appendix K. This follows the same operation-counting perspective used for the Bellman recursion in Appendix E.2, with additional accounting for shared recursive computations in the MLMC case. **2. Practical computational costs.** We agree that our experiments illustrate significant computational challenges, including the relatively low Plan-entry rate of original LCP and substantial memory requirements. In particular, the high traffic intensity in our experiments ($\rho=0.97$) makes queue clearing relatively infrequent, while exact Bellman planning becomes computationally expensive as the state space grows. We acknowledge these practical limitations. **3. Scope of Appendix K and the larger experiments.** Our primary objective in Appendix K was to establish that vanishing terminal regret can be achieved with polynomial arithmetic work, overcoming the quasipolynomial complexity of exact empirical Bellman planning. Our goal was to establish this theoretical possibility rather than to claim practical scalability or experimentally benchmark the proposed algorithms against original LCP. In particular, the 10- and 20-context experiments were designed to compare the queue-length performance of different scheduling policies, not to evaluate the computational efficiency of the algorithms in Appendix K. Since exact Bellman planning becomes prohibitively expensive in these settings, we employed a separate adaptive approximation solver to reduce the computational burden while controlling the fitted-model policy-loss error to approximately $0.1$. These experiments therefore do not directly measure the practical costs of the two algorithms proposed in Appendix K. We acknowledge that the prescribed parameters of the randomized multilevel method can lead to substantial computational costs at finite horizons, including $8^{38}$ level-zero samples at $T=2000$. Importantly, however, this limitation does not apply to our deterministic grid-based algorithm, for which our refined analysis establishes a Bellman-planning arithmetic-work upper bound of $T^{1-o(1)}$. To summarize, Appendix K achieves our original goal of obtaining vanishing terminal regret with polynomial computational work, and our refined analysis further establishes explicit asymptotic planning-work bounds of $T^{1-o(1)}$ and $T^{3+o(1)}$ for the two algorithms. The approximation techniques developed in Appendix K also provide a useful framework for efficiently approximating the Bellman recursion with controlled errors, an approach that is also reflected in the separate adaptive solver used in our larger-context (10- and 20-context) experiments.

Thank you for your continued consideration of our work. We appreciate your comments and would like to further clarify the scope of our multi-server extension and the theoretical contributions underlying our analysis.

1. Scope of the multi-server extension. We acknowledge that our current multi-server model permits only one active job–server pair at a time and does not cover simultaneous processing by multiple servers. However, this modeling choice follows an established formulation in the queueing-bandit literature, where at most one server or job–server pair is selected for service at each time, as studied in Krishnasamy et al. [1, 2] and, in the contextual setting, Bae and Lee [3].

Our work extends this established learning-while-scheduling framework to the nonpreemptive setting, where an assigned job must remain in service until completion rather than allowing the scheduling decision to be revised after an unsuccessful service attempt. This captures practical situations in which ongoing service cannot be interrupted or reassigned. The extension also introduces challenges involving unknown server-dependent completion probabilities, exploration across servers, and controlling accumulated workload before planning.

Allowing multiple servers to operate simultaneously would constitute a further generalization and introduce substantially different difficulties. In particular, the best-server reduction used in our analysis would no longer apply directly, since server assignments would interact through capacity constraints, and choosing the best server for each job independently need not be globally optimal. Analyzing the resulting nonpreemptive scheduling problem and establishing corresponding regret guarantees would therefore require additional theoretical developments. We regard this more general setting as an important direction for future research.

2. Theoretical novelty and certainty equivalence. We agree that certainty equivalence is a familiar general principle: one estimates the unknown model and acts optimally as though the estimated model were correct. However, the crucial distinction is that the validity of this approach and its quantitative regret guarantees do not follow automatically from the principle itself.

This is particularly important under nonpreemptive service. Unlike in the preemptive setting, an incorrect scheduling decision may commit the server to a job for many subsequent rounds, potentially causing the queue-length trajectories of two policies to diverge substantially. Consequently, even small model-estimation errors can have nontrivial effects on finite-horizon scheduling performance. In particular, obtaining a sufficiently sharp regret upper bound to match the lower bound up to logarithmic factors is challenging in this setting.

Our Lemma 4 establishes precisely the quantitative guarantee needed for certainty-equivalent Bellman planning. Its proof, provided in Appendix E, requires separate analyses of the sensitivity of nonpreemptive Bellman values to the future-arrival distribution and the effect of service-probability errors through geometric service-time coupling. These estimates are not immediate consequences of certainty equivalence.

Combining this lemma with our estimation and workload analyses allows us to obtain terminal regret of order O~(d/(λT))\widetilde O(\sqrt{d/(\lambda T)}), matching our lower bound up to logarithmic factors when T≥d2T\ge d^2. Establishing such a nearly rate-optimal regret guarantee under nonpreemptive service is a central objective and theoretical contribution of our work.

Thus, our contribution is not the certainty-equivalence principle itself, but its rigorous quantitative justification in the nonpreemptive queueing setting, where the consequences of incorrect service commitments are substantially more difficult to control.

Beyond this result, our analysis also establishes cumulative regret guarantees, matching-order terminal lower bounds, anytime impossibility results, and polynomial-work approximate planning methods. We hope these results clarify the broader theoretical contributions of our work.


[1] Krishnasamy et al., Regret of Queueing Bandits, NeurIPS, 2016.

[2] Krishnasamy et al., Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach, Operations Research, 2021.

[3] Bae and Lee, Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret, arXiv:2606.09668, 2026.

AuthorsOpenReview ↗

Revision of the Manuscript: SEPT+LCP

We would like to inform you that we have revised our manuscript.

While retaining the original nonpreemptive contextual queueing bandit setting and all the main theoretical results from our previous submission, we have updated the manuscript to highlight SEPT+LCP, an improved algorithm combining estimated-SEPT scheduling in the Learn and Clear phases with finite-horizon Bellman planning.

The revised manuscript now establishes both terminal and cumulative queue-length regret guarantees for SEPT+LCP, supported by an estimated-SEPT tracking result. We have also incorporated work-conserving and multi-server extensions, polynomial-work planning methods, and additional numerical experiments.

Some section and appendix references have changed accordingly. We encourage you to consult the revised manuscript, particularly Table 1, Section 4, and Section 6, for an overview of the main contributions.

We sincerely appreciate your time and constructive feedback, and would be grateful if you could consider the updated manuscript in your evaluation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.