Cheap Architecture Selection for Queueing Controllers via Differentiable Simulation

Neural controllers for queueing networks, such as hospital wards, fabrication lines and network switches, are trained inside discrete event simulators. A discrete event simulator is a program that jumps the clock from one event (an arrival, a service completion) to the next instead of stepping through time uniformly. Which network architecture the controller uses matters a great deal. Plain reinforcement learning with a generic policy fails to stabilize any of the 20 queueing benchmarks in QGym. Graph-based encoders beat simple feed-forward networks on large topologies in Virne. Yet nobody chooses these architectures per problem in any systematic way, because each candidate has to be scored by a full, noisy reinforcement-learning run. We propose to make that scoring cheap.

Differentiable discrete event simulation gives low-variance gradients along a single simulated trajectory. Differentiable Discrete Event Simulation for Queuing Network Control reports that one such trajectory beat 1,000 trajectories of a standard score-function gradient in 94.5% of scenarios. We will use these gradients to run short screening trainings of many candidate controller architectures, rank them, and fully train only the top few. The scientific aim is to learn which architectural ingredients a queueing network actually needs, and when. The ingredients are relational graph encoders, memory of elapsed service times, and output layers that never assign servers to empty queues. The practical aim is to close the gap on large instances where current learned controllers still lose to textbook rules.

Core Claim

We make two claims. First, on queueing control, short training runs driven by pathwise gradients rank candidate controller architectures far more faithfully than equal-budget short runs of PPO, the standard policy-gradient reinforcement-learning method. Pathwise gradients are gradients computed by differentiating through the simulated trajectory itself. With them, per-instance architecture selection becomes affordable. Second, the selected architectures will show a structured, predictable pattern rather than one universal winner. We expect the following. A work-conserving output layer is always needed. A graph encoder over the routing structure pays off only as the number of job classes and servers grows. Explicit memory pays off only when service times are non-exponential, because then queue lengths alone are no longer a sufficient state. Feeding elapsed time as an input feature may then be enough, as it was in Discrete Event, Continuous Time RNNs.

Relation to Prior Work

Two benchmarks motivate the gap. QGym shows that a single hand-fixed design, PPO with a work-conserving action mask (PPO-WC), beats classical rules on 77% of instances. The same design still loses to simple heuristics on the 497-bed hospital model after 5 million training steps, and QGym never varies the architecture. Virne compares fixed architectures (MLPs, CNNs, several graph attention variants, and a dual-graph encoder) for network resource allocation. It finds that the dual-graph encoder wins and that MLPs collapse at 500 nodes, but it selects nothing automatically and predicts nothing from problem features. Our proposal differs from both by making the architecture a per-instance decision and by testing what drives that decision.

Two papers supply our methods. Differentiable Discrete Event Simulation for Queuing Network Control supplies the gradient estimator. Its forward pass runs exact discrete events, and its backward pass treats the argmin over event times as a softmin. It also supplies the work-conserving softmax head, and it reports 50x to 1000x sample-efficiency gains over PPO. It searches no encoders, and it never uses its gradients to compare architectures. That second use is our new step. SeqNAS supplies the search template. It uses a modular search space, a surrogate-guided search, and a tabulated benchmark of 3,200 evaluated architectures. It also finds that recurrent units remain essential for irregular event sequences. SeqNAS works on offline classification, where each evaluation is a cheap supervised run. Our setting is closed-loop control, where evaluation noise is the main obstacle.

Two papers constrain the design. The null result in Discrete Event, Continuous Time RNNs found that hand-built multi-timescale memory did no better than a plain GRU (gated recurrent unit, a standard recurrent network) given elapsed time as an input. We therefore include "plain network plus elapsed-time features" as a search option rather than assuming bespoke temporal modules help. Dissecting Span Identification Tasks with Performance Prediction predicted which architecture would win on NLP tasks from measurable task statistics, with R² = 0.73. We borrow its regression method to test whether network features alone can pick an architecture without any screening. Those features are traffic intensity, service-time variance, number of classes, and degree of re-entrance (how often jobs revisit the same station). Neural Architecture Search for Sentence Classification with BERT found that searched lightweight heads beat a linear head by 3.0% in low-data settings. This motivates searching the head as well as the encoder, though in our setting the head must keep the work-conserving guarantee.

Research Program

We will port the straight-through differentiable simulator to the QGym instances. These are tandem lines, N-models, criss-cross networks, re-entrant lines, input-queued switches and the hospital ward, under both exponential and hyper-exponential (bursty, high-variance) service times. The search space has four axes. The input is queue lengths alone or queue lengths plus the elapsed time of in-progress services. Memory is none or a GRU over the event stream. The encoder is a flat MLP or a message-passing graph network over the bipartite graph linking job classes to servers. The head is the work-conserving softmax, a masked softmax with a small searched pooling layer, or an unmasked softmax kept as a control. Together these give roughly 50 architectures.

For every architecture on every instance, we will run full training with pathwise gradients to convergence over five seeds. This produces a small tabulated benchmark in the spirit of SeqNAS, giving each candidate a ground-truth final holding cost. Screening then means training each candidate for a fixed small budget of simulated trajectories, ranking by short-run cost, and fully training the top three. We also fit a feature-based regression that predicts the winning ingredients from network statistics alone, evaluated by holding out whole instance families.

Baselines

The naive reference point is the classical rule best suited to each instance, either the cμ-rule or MaxWeight. Both need no training. QGym reports that learned controllers still lose to these rules on the hospital ward after 5 million steps. Beating them on that instance is the main practical target.

The strongest existing learned method is the fixed architecture of the differentiable-simulation paper: an MLP with a work-conserving softmax, trained with pathwise gradients. We also run QGym's PPO-WC. The relevant reported numbers are a 21% holding-cost reduction over the best classical rule on re-entrant lines with high-variance noise, and outperformance of classical rules in 77% of instances, both from QGym. We found no reported absolute holding-cost values on Lacuna for individual QGym instances, so we will rerun both baselines ourselves in the same simulator, at the same total simulated-trajectory budget as our method including screening cost, with the same tuning budget. Beating them means a lower mean holding cost with non-overlapping seed intervals on the large instances (hospital and the 21-class re-entrant line), with no regressions elsewhere.

The strongest single-architecture competitor is a graph encoder with a work-conserving head used everywhere, the queueing analogue of Virne's winning dual-graph design. We will fully train it at a budget equal to our screening plus final training.

The key ablation replaces pathwise screening with PPO screening at an identical simulated-trajectory budget. It isolates whether the gradient estimator is what makes cheap selection work. Random selection from the space at equal budget is the floor.

Why not just…?

Why not just use the cμ-rule or MaxWeight? On small Markovian networks this may well be enough, and we will report it honestly. QGym shows that learned controllers' advantage over these rules roughly doubles, from 10% to over 20%, under hyper-exponential noise. That is exactly the regime where our hypothesis says memory or elapsed-time inputs should matter. The hospital comparison directly tests whether the rules remain unbeaten at scale.

Why not just use one strong architecture, a graph encoder with a work-conserving head, everywhere? This is the real threat. Virne's results suggest such a design wins broadly. If the fixed graph controller comes within seed noise of per-instance selection on all instances, the selection claim fails, and we will report that. What would survive is the narrower and still useful finding that the routing graph is the only bias that matters. Our tabulated full runs settle this directly, because they show how much regret each fixed choice has on each instance.

Why not just run standard search, such as Hyperband or Bayesian optimization, on PPO training? Kenneweg et al. used Bayesian optimization with Hyperband scheduling, an early-stopping scheme, for head search on BERT. The equal-budget PPO-screening ablation is exactly this test. The differentiable-simulation paper's variance results predict that short PPO runs will rank architectures poorly. If PPO-screening rank correlation matches pathwise screening, the gradient ingredient adds nothing.

Why not just give a plain MLP the elapsed service times? Mozer et al.'s null result makes this plausible, so it is a first-class option in the search space rather than a strawman. If it matches the GRU under hyper-exponential noise, we will conclude that memory architecture is unnecessary and features suffice.

Proposed Experiments

The first decisive check is ranking fidelity. We compute the Kendall rank correlation between screening-run cost and fully trained cost, for pathwise versus PPO screening, as a function of screening budget. Success means pathwise screening reaches a correlation PPO needs an order of magnitude more trajectories to match.

The second check is selection regret. This is the holding cost of the selected architecture relative to the best fully trained one, compared against the fixed MLP and fixed graph controllers, with the hospital and 21-class re-entrant line as the instances that matter most.

The third check tests the structural hypotheses through main effects in the tabulated benchmark. We expect the work-conserving head to be needed everywhere. We expect the graph-encoder gain to grow with class count. We expect the memory or elapsed-time gain to appear only under non-exponential service.

The fourth check asks whether the feature-based predictor, trained on held-out instance families, picks architectures with regret close to screening's. If it does, selection would need no extra simulation at all.