Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

arXiv:2611.01186v1 Announce Type: new 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 $\epsilon$-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.