- 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
-
The problem is natural and the structural point is made cleanly. Nonpreemption is the realistic constraint in many systems.
-
The analysis is complete and the lower bound handles both work-conserving policies and policies that may idle.
-
The assumptions are weaker than in the preemptive prior work. The analysis needs only the error of the fitted departure probabilities, so no lower bound on the context covariance is required, and the workload condition replaces the pointwise traffic-slack condition.
Critical weaknesses
-
The regret notion removes the learning–scheduling trade-off, and the paper does not acknowledge this. Only the last rounds affect because of the exponential workload tails (this is the term in (8)), so Learn–clear–plan can serve FCFS for 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 i.i.d. samples. The 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.
-
The planner is quasi-polynomial and nothing practical is offered.
-
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
-
Is SEPT average-cost optimal in your model among nonpreemptive work-conserving policies, as the rule is for M/G/1?
-
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?
-
What is the practical version of Learn–clear–plan?
5 comments
[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 , while retaining regret guarantees that vanish as (Appendix K).
First, Theorem 8 establishes a deterministic polynomial-work algorithm achieving for some constants . The key idea is to restrict the number of distinct success-probability labels in the empirical distribution used for Bellman planning. Specifically, we choose equally spaced grid points in 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 values.
With the Clear–Plan window set to , the resulting Bellman recursion has a polynomial number of states and requires polynomial total arithmetic work. Moreover, each rounding error is at most , which contributes only 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 or vanishes as .
[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 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 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 denotes the empirical WC Bellman policy. Indeed, from this common empty state, the optimal WC policy follows an optimal policy for the remaining rounds, whereas WC-LCP enters its Plan phase and follows . 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.
[CW1] The regret notion removes the learning--scheduling trade-off, and the paper does not acknowledge this. Only the last O(logT) rounds affect E[QT+1] because of the exponential workload tails (this is the ψ(r)H term in (8)), so Learn--clear--plan can serve FCFS for T−log2T 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) i.i.d. samples. The 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)).
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 L and the clearing–planning window H=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.