CS Paper Radar

Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

Deyi Wang, Qining Zhang, Lei Ying

cs.LG ·submitted 2026-10-31 18:37 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

cs.LG ·2026-09-29 ·Wansoo Choi, Seoungbin Bae, Dabeen Lee
similarity 0.62
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

A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

cs.LG ·2026-09-05 ·Menglong Li, Jiawei Zhang
similarity 0.59
Abstract

We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with one request type, for a fluid relaxation in which resource overuse incurs a quadratic penalty. The policy achieves $O(1)$ expected additive regret relative to the hindsight optimum, with a bound independent of the horizon $T$, under a general arrival model. This model includes independent and identically distributed arrivals with unknown probabilities, independent nonstationary arrivals with known probabilities, independent nonstationary arrivals with unknown probabilities and one historical sample path, and Markov-modulated arrivals with an unknown Markov chain. The policy does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.

0.20

Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems

cs.GT cs.LGcs.PF ·2026-10-13 ·Cristian Palma Foster, Eva Tardos
theory similarity 0.59
Abstract

We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to $m$ buffered servers with service rates $μ_1, \dots, μ_m$. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least $0.77$-competitive, which is also tight. We then study multi-queue systems where $n$ queues with arrival rates $λ_1, \dots, λ_n$, each at most $λ_{\max}$, compete for service from $m$ buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is $\frac{1}{1-λ_{\max}}$. Equivalently, in terms of the total arrival and service rates, the condition $\sum_{i=1}^n λ_i < (1-λ_{\max})\sum_{j=1}^m μ_j$ is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for $λ_{\max} = 1/2$, this improves the upper bound of Abel et al. (EC 2026) from $3$ to $2$, matching their lower bound and resolving their open question.

0.08

First-Order Model-Free Policy Gradient for Undiscounted LQR with Global Optimality and Convergence Guarantees

eess.SY math.OC ·2026-11-16 ·Vipul K Sharma, S Sivaranjani
similarity 0.59
Abstract

We provide a first-order model-free policy gradient (PG) framework for learning undiscounted infinite-horizon linear quadratic regulator (LQR) policies with global optimality and convergence guarantees. We first construct a stochastic wrapper policy class parameterized by the LQR gain to enable exploration around a deterministic linear control law. We analyze the additional cost induced by exploration over infinite-horizon, and establish a weak gradient dominance condition that characterizes global optimality under exploration. We then construct a model-free first-order PG algorithm using sampled trajectory information, without identifying the dynamics or approximating a value function. Finally, we establish finite-time convergence guarantees, providing the sufficient number of samples required for near-global optimality with our proposed PG algorithms.

0.27

Deadline-Aware Multi-Agent Reinforcement Learning for TSN-Based Vehicular Edge Networks

cs.NI cs.AI ·2026-10-07 ·Bernardo A. C. Pereira, Marcos Carvalho, Fatih Temiz, Shavbo Salehi, Melike Erol-Kantarci +3 more
similarity 0.58
Abstract

Vehicular edge computing (VEC) enables latency-sensitive applications by bringing computing and networking resources closer to vehicles. However, existing approaches often overlook network contention among co-located services with heterogeneous and dynamic latency requirements. While time-sensitive networking (TSN) provides bounded-latency communication, conventional and reinforcement learning-based schedulers struggle to adapt to highly dynamic vehicular environments and inter-queue dependencies. To address these limitations, we propose a multi-agent reinforcement learning (MARL) approach for queue-level scheduling in TSN-enabled VEC. Each TSN queue is assigned an autonomous agent that jointly learns the queue service order and time-slot duration to minimize deadline misses under speed-dependent latency requirements. We employ multi-agent proximal policy optimization (MAPPO) to enable coordinated yet autonomous scheduling decisions. Evaluation against single-agent, multi-agent, and non-learning-based baselines shows that MAPPO provides robust performance across different traffic profiles. Compared with centralized single-agent methods, it reduces service latency by up to 66.2% and improves reliability by up to 271.8%. Furthermore, unlike urgency-based heuristics, MAPPO ensures balanced scheduling while achieving lower inference times compared to other MARL methods.

0.21

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.58
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

Dynamic Skill-Based Routing for Call Centers with Transfers: A Value-Based Framework

eess.SY ·2026-10-18 ·Baris Ata, Ebru Kasikaralar
benchmarkcode/data similarity 0.57
Abstract

We consider a multi-class, multi-pool queueing model of a telephone call center in which a service completion does not always end the call. The caller may be transferred to another agent for a second service, so the assignment of an agent to a call affects not only the caller's waiting time but also whether the call is resolved and how much further work it creates. We model these transfers as Markovian routing from original to rework classes, and the system manager dynamically assigns agent pools to classes so as to maximize the value generated by service, net of transfer penalties and waiting and abandonment costs, over a finite horizon. Focusing on the Halfin-Whitt heavy-traffic regime, we derive an approximating Brownian control problem. Its Hamilton-Jacobi-Bellman equation is a semilinear partial differential equation whose dimension equals the number of classes. Building on the deep splitting method of Beck et al. (2021), we develop a simulation-based computational method that approximates the value function and its gradient by neural networks, and we use it to construct an implementable routing policy for the original (prelimit) system. We calibrate the model to publicly available data from a large U.S. bank call center. In all test problems we consider, the proposed policy outperforms the best available benchmark policy we could find.

0.34

Reinforcement Learning-Based Production Scheduling in an Industry-Based Coating Scenario Using the Digital Model Playground

cs.AI ·2026-08-14 ·Arne Kröger, Ralf Buschermöhle, Wilhelm Hasselbring, Henrik Wilbers
publishedbenchmarkcode/data similarity 0.57
Abstract · Copyright 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or…

Production scheduling in complex manufacturing environments is challenging when sequence-dependent setup times, stochastic disturbances, and due-date constraints must be addressed simultaneously. While reinforcement learning (RL) methods have shown promising results in research, most studies rely on simplified benchmark processes, limiting their industrial relevance. This paper demonstrates the applicability of RL-based scheduling in an industry-inspired coating process that reflects practical complexities such as sequence-dependent setup times, machine breakdowns, and variable utilization. The open-source Digital Model Playground (DMPG), a discrete event simulation framework, is used to model the scenario and to train RL agents. Two standard algorithms, Deep Q-Networks and Proximal Policy Optimization, are benchmarked against conventional dispatching rules to illustrate feasibility and to provide a transparent testbed for further research. Results indicate that RL-based scheduling achieves balanced improvements across key performance indicators, with PPO delivering the most robust performance. The main contribution of this work is to bridge the gap between academic research and industrial practice by validating RL-based scheduling in a realistic, shareable scenario and by providing a reusable open-source framework for future studies.

0.38