- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies a contextual-bandit-based problem in queueing theory. The model is a queue with Bernoulli arrivals and service probabilities that depend on the job's context and the chosen machine through the logistic function. Under a standard stability condition, the authors give an horizon-free algorithm that is minimax optimal up to log-factors, with expected queue-length regret for all sufficiently large . Experiments compare the algorithm to prior work baselines.
Critical strengths
- The paper solves an interesting problem at the intersection of online scheduling and online learning: optimal context-dependent scheduling. While the main result is stated in discrete time, it is not hard to imagine an extension to continuous time (e.g., M/M/1 queues with modes for each job).
- The assumptions used to derive the rate are reasonable and a significant improvement over prior work. In particular, the stability condition (Assumption 2) is standard: it essentially requires that the arrival rate be strictly less than the maximal service rate, so that the queue does not have to blow up.
Critical weaknesses
No critical weaknesses to report. Please address minor weaknesses in the questions below.
Questions for authors
- Could you strengthen the paper's positioning within online scheduling/learning theory? In particular, [1, 2, 3] seem relevant to the considered scheduling setup. Moreover, the intersection of online learning and scheduling was previously studied in [4] for multi-armed bandits, with a focus on minimizing learning regret while scheduling.
- It is a bit misleading to present the problem as having servers, which suggests that multiple jobs can be processed in parallel. In this paper, only one job-server pair can be processed per round. A more accurate interpretation is therefore a single server with modes of operation.
- In Lemma 5, you show that the queue is empty sufficiently often, which effectively controls each job's sojourn time. I think it is very important that no job stays queued indefinitely. Could you derive or conjecture a high-probability upper bound on the maximum number of rounds any job spends in the queue (its sojourn time)?
- In Theorem 1, you provide the upper bound, which holds for sufficiently large . However, the second term in the minimum eventually drops below , so the minimum is attained by the second term for all sufficiently large . Why keep the first term here?
[1] D. G. Kendall (1953). Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain.
[2] R. M. Loynes (1962). The stability of a queue with non-independent inter-arrival and service times.
[3] Tassiulas and Ephremides (1992). Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks.
[4] A. Ryabchenko, I. Attias, and D. M. Roy (2025). Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs. COLT.
4 comments
[Q3] In Lemma 5, you show that the queue is empty sufficiently often, which effectively controls each job's sojourn time. I think it is very important that no job stays queued indefinitely. Could you derive or conjecture a high-probability upper bound on the maximum number of rounds any job spends in the queue (its sojourn time)?
The reviewer's intuition about jobs' sojourn times is correct. A high-probability bound on the maximum sojourn time follows as a corollary of our existing Lemma 5. We have added this result as Corollary 1 in Appendix F.2.
-
Using Lemma 5, we show that the maximum sojourn time among all jobs that enter the queue in rounds satisfies, with probability at least ,
-
Consider a job arriving in round that remains for more than rounds. With , Lemma 5(i) gives where the first inequality holds for . Next, if , at least one job that entered in rounds remained for more than rounds. A union bound over these arrival rounds gives Choosing such that ensures that and makes this probability at most , giving the result in the first bullet.
[Q4] In Theorem 1, you provide the upper bound, which holds for sufficiently large . However, the second term in the minimum eventually drops below , so the minimum is attained by the second term for all sufficiently large . Why keep the first term here?
We thank the reviewer for pointing this out and have removed the term from the minimum in revised Theorem 1 in Section 5.1.
References
[1] Kendall, "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain", Ann. Math. Statist., 1953.
[2] Loynes, "The stability of a queue with non-independent inter-arrival and service times", Math. Proc. Cambridge Philos. Soc., 1962.
[3] Tassiulas and Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks", IEEE Trans. Autom. Control, 1992.
[4] Ryabchenko et al., "Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs", COLT, 2025.
Thank you for the detailed response. I maintain my positive score.
Dear Reviewer wnq3,
We thank you again for your valuable comments and positive evaluation of our work!
Thanks, Authors
[Q1] Could you strengthen the paper's positioning within online scheduling/learning theory? In particular, [1, 2, 3] seem relevant to the considered scheduling setup. Moreover, the intersection of online learning and scheduling was previously studied in [4] for multi-armed bandits, with a focus on minimizing learning regret while scheduling.
We thank the reviewer for pointing out these connections and helping us broaden our perspective on the related literature. We have added comparisons with [1-4] in Appendix A.
Queueing theory and stability [1-3]. Kendall [1] analyzes queue-length and waiting-time distributions under given arrival and service models. Loynes [2] shows that a single-server queue is stable under the load condition ρ=λE[B]<1, where B is the time needed to serve one job. Tassiulas and Ephremides [3] consider queueing networks in which only certain servers can operate at the same time. They construct a policy that stabilizes the network whenever the arrival-rate vector lies strictly inside the capacity region.
Relation to our work. Our capacity slack assumption is the counterpart of these stability conditions. Under best-server service, a job with context X needs E[B∣X]=1/p∗(X) rounds in expectation, so Loynes' load condition becomes λE[1/p∗(X)]<1, which is Assumption 2. The works in [1-3] do not involve learning unknown service rates. In our setting, the service probabilities must be learned from service outcomes, and we bound Rt=E[Qπ(t)−Q∗(t)], the expected excess queue length relative to an oracle that knows the service rates.
Ryabchenko et al. [4]. They study bandits with delayed feedback in which only a limited number of past rounds can be tracked until their feedback arrives. They characterize how this limit and the delays affect cumulative loss regret. Both works combine online learning with scheduling, but the settings and objectives differ. Our scheduler selects a waiting job and a server and observes success or failure immediately after the attempt. We bound the expected excess queue length at each round, instead of cumulative loss regret.
[Q2] It is a bit misleading to present the problem as having K servers, which suggests that multiple jobs can be processed in parallel. In this paper, only one job-server pair can be processed per round. A more accurate interpretation is therefore a single server with K modes of operation.
We thank the reviewer for pointing this out and have added a statement in Section 2.1 that only one job-server pair is served per round, corresponding to a single server with K modes of operation.