Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

Deyi Wang; Qining Zhang; Lei Ying

cs.LGOct 31, 2026

Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

Authors: Deyi Wang, Qining Zhang, Lei Ying

Organizations: University of Michigan, Ann Arbor

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.

Figures & tables

Figure 1: Illustration of a criss-cross queueing network.

{\bm{\theta}}_{k+1}={\bm{\theta}}_{k}+\alpha\mathbbm{1}\left\{J(\pi_{H,{\bm{\theta}}_{k}^{\prime}})<J(\pi_{H,{\bm{\theta}}_{k}})\right\}{\bm{v}}_{k}.

Algorithm 1 Zeroth-order policy optimization method for queueing network controls

{\bm{\theta}}_{k+1}={\bm{\theta}}_{k}+\alpha\sum_{j=1}^{D}\mathbbm{1}\left\{J(\pi_{H,{\bm{\theta}}_{k,j}^{\prime}})<J(\pi_{H,{\bm{\theta}}_{k}})\right\}{\bm{v}}_{k}\circ{\bm{e}}_{{\mathcal{D}}_{j}}.

Algorithm 2 Partitioned zeroth-order policy optimization method for queueing network controls

Panel of Figure 2 — Figure 2: Topologies of queueing networks.

Queueing Networks	Algorithm 1	Algorithm 2	PPO
Criss-cross	$10000$	$2200$	$4000$
N-model	$4500$	$1000$	$1800$
9-layer Exp Reentrant	$135000$	$30000$	$54000$
5-layer HyperExp Reentrant	$121500$	$27000$	$50000$

Table 1: The length (number of steps) of each collected trajectory in RL training. The trajectory lengths are chosen to make the sample complexities almost the same across algorithms.

Queueing Networks	Criss-cross	N-model	9-layer Exp Reentrant	5-layer HyperExp Reentrant
Trajectory length	$10000$	$10000$	$300000$	$150000$

Table 2: The length (number of steps) of each evaluation trajectory.

Panel of Figure 3 — Figure 3: Performances (average-costs) of Algorithm 1 , Algorithm 2 , and PPO algorithm during training

Queueing Networks	$c\mu$	MaxWeight	Algorithm 1	Algorithm 2	PPO
Criss-cross	$17.51\pm 0.46$	$17.04\pm 0.43$	$15.62\pm 0.38$	$\mathbf{15.20\pm 0.38}$	$15.88\pm 0.42$
N-model	$183.52\pm 5.37$	$\mathbf{44.43\pm 1.80}$	$44.62\pm 1.79$	$45.16\pm 1.71$	$44.66\pm 1.75$
9-layer Exp Reentrant	$71.30\pm 0.67$	$77.49\pm 0.67$	$73.70\pm 0.63$	$\mathbf{69.28\pm 0.58}$	$71.09\pm 0.64$
5-layer HyperExp Reentrant	$69.73\pm 0.87$	$77.50\pm 0.93$	$72.78\pm 0.88$	$\mathbf{67.12\pm 0.75}$	$69.52\pm 0.79$

Table 3: Performances of priority-based benchmark policies and the best RL training policies.

Policy Optimization

Policy optimization develops algorithms for improving decision rules in reinforcement learning, language models, and sequential decision systems.

See all 233 papers

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits
Nov 2, 2026Jongyeong Lee, Chansoo KimBest-of-Both-Worlds Bandits Multi-Armed Bandits
Korea Institute of Science and Technology · University of Science and Technology
NetRL: Powering Network Decisions via NetGRPO-Driven Reinforcement Learning
Oct 12, 2026Lingfeng Peng, Xiaohui Xie, Yang Bao +1RL Control RL for LLM Agents
Tsinghua University
Commit to the Bit: Reactive Reinforcement Learning Done Right
May 27, 2026Onno Eberhard, Claire Vernade, Michael MuehlebachReinforcement Learning Partially Observable RL
Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · University of Technology Nuremberg.

Nov 2, 2026J/K move · Enter open · S save

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

Jongyeong Lee, Chansoo Kim

Korea Institute of Science and Technology · University of Science and Technology

Best-of-Both-Worlds Bandits Multi-Armed Bandits Parameter-Free Online Learning

Open paper AskPDF arXiv

We study online channel scheduling for a single queue served by

K

channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves

\tilde{\mathcal{O}}(\sqrt{K L_T})

worst-case queue length regret with high probability, where

L_T

is the longest busy-period length. This result improves the previous

T^{3/4}

dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.

Abstract

Policy Optimization

Explore similar work

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

NetRL: Powering Network Decisions via NetGRPO-Driven Reinforcement Learning

Commit to the Bit: Reactive Reinforcement Learning Done Right