CS Paper Radar

Review-Period Sensitivity in Multiclass Queue Scheduling

Mir Mikdad Talpur, Vahid Sarhangian

eess.SY ·submitted 2026-08-29 18:47 UTC · v2

Abstract

Optimal control of queueing networks is typically studied under continuous-time control. In many service settings, however, managers can adjust decisions only at discrete and potentially infrequent review epochs. We study a multiclass queue scheduling problem in which server assignments can be changed only at the beginning of discrete review periods, and examine how performance depends on the review-period length. We analyze a family of associated fluid control problems parameterized by the review-period length and characterize the first- and second-order sensitivity of the value function. For the two-class case, we derive explicit expressions for these derivatives and characterize their signs. We find that for short review periods, the value function need not be monotone. Once the review period is sufficiently large, the value function becomes monotone nondecreasing and may exhibit a convex or linear region before eventually becoming concave. These results provide insights on when the value of more frequent control, or \emph{flexibility} with respect to server assignments, is higher. We further numerically examine the robustness of these observations for the original stochastic scheduling problem and show that stochasticity smooths the nonmonotonicity at smaller scales, while the qualitative sensitivity patterns remain visible and become more pronounced as the scale of the system increases.

Closest papers

Nearest neighbours by meaning across the whole index.

Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

cs.LG ·2026-10-31 ·Deyi Wang, Qining Zhang, Lei Ying
similarity 0.57
Abstract

Reinforcement learning in queueing network scheduling presents significant challenges because of the countably infinite state space and the high stochasticity in transitions. In this paper, we propose zeroth-order policy optimization algorithms that are easy to implement and rely solely on estimates of the average cost, a single scalar quantity, without requiring the estimation of value or advantage functions. Our analysis focuses on back-pressure guarded policies and establishes uniform smoothness of the average cost objective with respect to the policy parameters. Building on this property, we establish finite-time convergence guarantees to an $ε$-stationary policy for the proposed algorithms. Numerical experiments on multiple queueing networks, including systems beyond classical exponential service distribution, demonstrate competitive performance, outperforming gradient-based RL methods like PPO and traditional queueing baselines.

0.24

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.57
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31

Joint Service Depth and Priority Design in Queueing Systems

cs.GT econ.THmath.OC ·2026-10-23 ·Adam N. Elmachtoub, Yash Kanoria, Jonathan Y. Tan
similarity 0.55
Abstract

In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient type to receive a weakly shorter sojourn time, so the optimal price menu never prioritizes the patient type. Consequently, there can be a welfare gap between the centralized decision maker's optimal control policy and the optimal decentralized pricing mechanism. With a continuum of types, the centralized optimum is monotone: more delay-sensitive customers receive weakly smaller depth and higher priority, so the optimum can be implemented by a price menu with no welfare loss. Allowing randomized depths similarly closes the gap in the two-type model. Finally, we calibrate an agentic AI service system using published coding-agent trials from DeepSWE and numerically examine priority inversion, the value of joint design, and the welfare gain from personalization.

0.26

Whittle index approach to multi-server scheduling with convex delay costs and impatient customers

cs.PF math.PR ·2026-09-17 ·Samuli Aalto
similarity 0.55
Abstract

We consider the dynamic scheduling problem in a multi-class M/G/N + M queue with convex delay costs and impatient customers that have exponential abandonment times. We apply the Whittle index approach to find a reasonable heuristic solution for this tricky problem. By assuming exponential abandonment times, we are able to make a very straightforward use of the results of the corresponding problem with patient customers presented in Queueing Systems, Vol. 110, Article no. 2, 2026. Our main theoretical achievements are proving that the closed version of the corresponding discrete-time problem is indexable and deriving an explicit expression for the Whittle index. The discrete-time results are utilized to develop the Whittle index policy for the original continuous-time scheduling problem.

0.24

Structure-Aware Online Optimization of the Age of Information with Unknown System Statistics

cs.IT math.OC ·2026-10-09 ·Yoshiaki Inoue, Michel Mandjes, Liron Ravner
theory similarity 0.54
Abstract

Timely information dissemination is essential in modern communication systems, where low informational latency is critical for networked control, monitoring, and real-time decision-making. The Age of Information (AoI) has emerged as a fundamental metric for quantifying information freshness at the receiver. A key challenge in AoI optimization is selecting the update generation rate: infrequent updates lead to stale information, whereas overly frequent updates increase queueing delays. We develop a structure-aware, data-driven framework for adaptive AoI optimization modeled as single-server queues with unknown system statistics. Our key idea is to exploit analytical representations of the AoI gradient, which depend on a finite-dimensional collection of system quantities that can be estimated from observations collected during system operation. This reduces the online learning problem to estimating the quantities required by the gradient, rather than learning the AoI objective as a black box. We propose an online stochastic approximation algorithm that jointly estimates these quantities and optimizes the update generation rate. We prove almost sure convergence of the algorithm to the optimal update generation rate under mild regularity and moment conditions, despite the temporal dependence induced by the underlying queueing process. We demonstrate the framework in four representative incomplete-information settings, including FCFS queues with unknown service characteristics or hidden background traffic, a preemptive LCFS system with partial observations, and a generate-at-will system with threshold waiting.

0.24

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

cs.LG ·2026-10-05 ·Seoungbin Bae, Dabeen Lee
theory similarity 0.53
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.

0.20

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

cs.LG ·2026-09-29 ·Wansoo Choi, Seoungbin Bae, Dabeen Lee
similarity 0.53
Abstract

We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a $d$-dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution $\mathcal{D}$, 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 $\widetilde{O}(\sqrt{d/T})$ queue-length regret, while a lower-bound construction gives $Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})$ regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when $T\ge d^2$. 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 $\widetilde{O}(\sqrt{d/t})$ without knowing the model.

0.18

Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control

cs.DS math.OC ·2026-10-30 ·Danny Segev
benchmark similarity 0.53
Abstract

In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be arbitrarily correlated and nonstationary. In this general information setting, Levi, P{á}l, Roundy, and Shmoys (Mathematics of Operations Research 2007) established that the fully adaptive optimum can be approximated within factor $2$, which had remained the best-known performance guarantee since then. Their marginal cost accounting and dual-balancing framework made this comparison possible without computing optimal decisions across future trajectories, opening a broad research program on approximation algorithms for stochastic inventory systems. We break this long-standing barrier for periodic-review stochastic inventory control, showing how to compete against the fully adaptive benchmark within factor $\frac{ e }{ e-1 } \approx 1.582$ while retaining general demand correlations and evolving forecasts. We attain these advances by discovering a structural connection between marginal inventory accounting and weighted stopping problems, where each unit's conditional holding charge forms a supermartingale, while postponing its order incurs a history-dependent backlog charge. To leverage the random thresholding approach of Ma and Tzamos (ICML 2023) in this context, we develop a potential-function analysis, leading to an $\frac{ e }{ e-1 }$-approximation with respect to any unit's stopping problem. Subsequently, our common-threshold policy coordinates these marginal decisions into a global replenishment policy without additional loss.

0.20