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.
- Zeroth-order algorithms：easy to implement; rely only on average cost estimates (single scalar), without value/advantage function estimation.
- Analysis focus：back-pressure guarded policies; establish uniform smoothness of average cost objective w.r.t. policy parameters.
- Convergence guarantees：finite-time convergence to an $ε$-stationary policy for proposed algorithms.
- Numerical experiments：multiple queueing networks (including beyond classical exponential service distribution); competitive performance, outperforming gradient-based RL (e.g., PPO) and traditional queueing baselines.