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.
θk+1=θk+α\mathbbm1{J(πH,θk′)<J(πH,θk)}vk.
Algorithm 1 Zeroth-order policy optimization method for queueing network controls
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.
Figure 3: Performances (average-costs) of Algorithm 1 , Algorithm 2 , and PPO algorithm during training
Queueing Networks
cμ
MaxWeight
Algorithm 1
Algorithm 2
PPO
Criss-cross
17.51±0.46
17.04±0.43
15.62±0.38
15.20±0.38
15.88±0.42
N-model
183.52±5.37
44.43±1.80
44.62±1.79
45.16±1.71
44.66±1.75
9-layer Exp Reentrant
71.30±0.67
77.49±0.67
73.70±0.63
69.28±0.58
71.09±0.64
5-layer HyperExp Reentrant
69.73±0.87
77.50±0.93
72.78±0.88
67.12±0.75
69.52±0.79
Table 3: Performances of priority-based benchmark policies and the best RL training policies.
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 O~(KLT) worst-case queue length regret with high probability, where LT is the longest busy-period length. This result improves the previous T3/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.
Jongyeong Lee, Chansoo Kim
Korea Institute of Science and Technology · University of Science and Technology
Network decision-making tasks, including adaptive bitrate streaming, load balancing, and congestion control, require policies to process heterogeneous states and actions while balancing near- and long-term consequences. Existing solutions generalize poorly across network tasks, require substantial task-specific redesign, and lack reliable evaluation of long- horizon action consequences. Methods that learn through online interaction additionally face unstable optimization. We present NetRL, a two-stage LLM-based reinforcement learning framework that combines supervised fine-tuning on demonstration trajectories with online policy optimization. A universal mixed-embedding interface combines textual task descriptions with precise numerical states, while a network action head produces valid decisions. At its core, NetGRPO evaluates candidate actions over multiple future trajectories, directs deeper search toward uncertain alternatives through confidence-aware budgeting, and performs group-relative, clipped, and KL-regularized updates. NetRL achieves 23.6% higher QoE than NetLLM, 12.2% lower job completion time than Genet, and 24.1% higher network utility than Orca, yielding state-of-the-art performance among the evaluated methods. Confidence-aware budgeting reduces end-to-end training time by 27.1% without reducing validation QoE. NetRL also converges stably and generalizes to unseen network traces without retraining. Code and model weights are available at the repository linked in this paper.
Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the q⋆-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.
Onno Eberhard, Claire Vernade, Michael Muehlebach
Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · University of Technology Nuremberg.