Many networked systems make a discrete choice every time step: which server takes a task, which channel a cache uses, which link gets scheduled. They must also keep a long-run average, such as power, accuracy, or delay, within a budget. The standard tool here is drift-plus-penalty. It tracks each budget as a "virtual queue", a running tally of how far the system has overspent. At each step it picks the action that best balances shrinking those tallies against the immediate cost, and a single knob $V$ sets the balance. The method is provably stable but myopic. Deep reinforcement learning (RL) plans over long horizons but loses the stability guarantee, both during training and often after it. This note proposes a hybrid suited to discrete actions. Score each action with the exact drift-plus-penalty expression, add a learned correction whose magnitude is hard-capped, and choose the best action by enumeration.
With the correction set to zero, the policy is exactly classical drift-plus-penalty from the first training step. With the cap in place, it stays within a known additive slack of the drift-plus-penalty choice, and that slack inherits the classical cost-versus-backlog guarantee. Because the drift term grows with queue length while the cap does not, the learned part steers only when queues are short. When queues are long, control automatically returns to the provably stabilizing rule. The empirical half of the project rebuilds the bespoke simulators of this literature, plus constrained variants of standardized operations-research environments, as open benchmarks. On them we measure what the theory leaves unanswered: whether the learned controller actually shifts the cost-backlog frontier, and how much it costs to train.
Core Claim
Discrete action spaces are where drift-plus-penalty and learning fit together most cleanly, not least. Let $Q_n(t)$ be the virtual queues, $a$ a candidate action from a finite set $\mathcal{A}$, and $D_t(a)$ the usual per-slot bound, i.e. queue-weighted drift plus $V$ times the immediate cost of $a$. The controller acts by
$$ a_t = \arg\min_{a \in \mathcal{A}} \Big[ D_t(a) - h_\theta(s_t, a) \Big], \qquad |h_\theta(s_t,a)| \le B, $$
where $h_\theta$ is a neural network with output limited to $[-B, B]$ by a scaled tanh. It is trained to estimate the long-horizon benefit of $a$ beyond what the one-step bound captures, and $B$ is a designer-chosen cap.
The argmin is exact because $\mathcal{A}$ is finite. The chosen action therefore minimizes $D_t$ to within $2B$. The standard additive-approximation property of the drift-plus-penalty analysis then gives time-averaged cost within $O((C_0+2B)/V)$ of optimal and average backlog $O(V + C_0 + 2B)$, where $C_0$ is the usual constant from the drift bound. In plain terms, the classical $[O(1/V), O(V)]$ tradeoff survives, with the constant inflated by the cap. The guarantee holds for every parameter value of $h_\theta$, including random initialization, so it covers the whole training run and not only a converged policy.
The new empirical claim is that, at matched average backlog, this controller reaches lower average cost than tuned classical drift-plus-penalty. The gap should be largest at small $V$, the low-delay regime where myopia hurts most. It should also come with no training-time constraint excursions, unlike unconstrained discrete RL that uses Lyapunov-shaped rewards.
Relation to Prior Work
Three papers motivate the gap. A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability shows that one-step drift-plus-penalty stalls in non-convex landscapes. It derives a quadratic reward $R(t) = -\tfrac12\sum_n (Q_n^2(t+1)+Q_n^2(t)) - Vp(t)$ that, when optimized greedily, reduces to drift-plus-penalty, and it trains PPO on that reward. We reuse this reward as the training signal for $h_\theta$. Their PPO policy is unconstrained, however, so stability holds only in the limit, and they evaluate continuous offloading and power on private Poisson simulators. Our cap gives the guarantee throughout training, and our actions are natively discrete.
A neural drift-plus-penalty algorithm for network power allocation and routing learns backlog functions with a graph network. Its bounded "Neural-B" variant keeps stability, which is the closest precedent for our bounded-correction idea. It avoids the discrete max-weight argmax by relaxing it to Sinkhorn optimal transport, which lets traffic split across links. We keep the decision indivisible and enumerate it. That matters for non-splittable offloading and channel choices of the kind studied in AoI-Delay Tradeoff in Mobile Edge Caching: A Mixed-Order Drift-Plus-Penalty Method and Accuracy-Guaranteed Collaborative DNN Inference in Industrial IoT via Deep Reinforcement Learning. The second of these uses an accuracy-deficit virtual queue with a continuous DDPG agent and offers no stability guarantee for the learned policy.
The closest work in safe RL is A Lyapunov-based Approach to Safe Reinforcement Learning. It restricts discrete action probabilities using a Lyapunov function built by linear programming from a known safe baseline policy, under episodic assumptions. In our setting the baseline comes for free, since classical drift-plus-penalty is itself the stabilizing policy, and the guarantee is for the infinite-horizon queueing setting. We give up their per-state constraint satisfaction in exchange for time-average guarantees.
Two further papers supply supporting evidence and constraints. Constrained Deep Q-Learning Gradually Approaching Ordinary Q-Learning supports relying on exact discrete maximization for stable value targets. RN-D: Discretized Categorical Actors for On-Policy Reinforcement Learning shows that categorical actors stabilize PPO through bounded gradient variance, which makes it the natural discrete-policy baseline. It also warns that very fine discretizations degrade. For continuous knobs such as transmit power, we therefore discretize coarsely, with $K$ around 41 as in RN-D, and do not grid finely.
Research Program
The method has three parts. First, a per-slot scorer computes $D_t(a)$ exactly for every action. For combinatorial sets that are too large to enumerate, such as joint schedules across many links, it falls back to a fixed candidate set: the drift-plus-penalty minimizer plus its top-$M$ neighbors. The guarantee is restated relative to that candidate set.
Second, a residual network $h_\theta$ is trained by fitted Q-learning, with targets built from the tailored quadratic reward. The network takes the observed state and the normalized virtual queues as input. Its target is the long-horizon return minus the part already explained by $D_t$.
Third, an analysis component. It states the additive-slack theorem carefully, including the candidate-set version, and derives how the "learning region" shrinks as the queues grow. The learned part can change the decision only when the gap between the best and second-best $D_t$ scores is below $2B$. We log the fraction of slots in which the residual actually overturns the drift-plus-penalty choice, which shows directly where the learning is spent.
The empirical program addresses the validation gap directly. The MEC offloading, mobile edge caching, and random-geometric-network routing settings exist only as private simulators. We reimplement them as Gym environments with fixed seeds and traces, and release them. We also add a long-term budget to two standardized environments from OR-Gym: A Reinforcement Learning Library for Operations Research Problem: an average active-machine (energy) budget on Azure VM packing, and an average holding-cost budget on the multi-echelon inventory task. These budgets are our own additions, not part of the original benchmark. We report wall-clock cost per decision and total training time next to the control metrics, since OR-Gym's own finding is that RL training takes hours where solvers take minutes.
Baselines
The naive reference point is classical drift-plus-penalty with exact discrete minimization. We sweep $V$ on a logarithmic grid to trace its full cost-versus-backlog frontier. It needs no training, it carries the guarantee, and it is the policy our method reduces to at $B=0$. If the learned frontier does not sit strictly below this one at matched backlog, the project fails. That is the most informative outcome either way.
The strongest learned competitor is the tailored-reward method of A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability, run with a discrete policy. We implement it in two forms: PPO with a categorical head using the RN-D codebase alwaysbyx/RND-RL, and a DQN on the same reward. It uses the same reward, state, environment steps, network size, and hyperparameter-search budget as our residual learner. No reported result was found on Lacuna for its numeric energy or queue values on the MEC simulator; that paper reports only qualitative superiority over its naive variants. We therefore reproduce it before comparing. Beating it means one of two things: equal or lower cost at matched backlog with zero training-time budget excursions above the drift-plus-penalty envelope, or strictly lower cost at matched excursions.
For constrained-RL practice we include PPO-Lagrangian with action masking, as in OR-Gym. On VM packing, the reference number from OR-Gym is that masked PPO outperforms the First-Fit heuristic by 9%. We first reproduce that unconstrained figure as a sanity check, then compare on the budgeted variant.
On the routing benchmark only, where traffic is genuinely splittable, we include the Sinkhorn neural method of A neural drift-plus-penalty algorithm for network power allocation and routing. It is trained on the same random geometric networks of 20 to 50 nodes, reported with queue ratio and power. No numeric values were found on Lacuna for it either.
The key ablation varies the cap $B$. $B=0$ is classical drift-plus-penalty. An uncapped residual is ordinary discrete Q-learning with drift-plus-penalty features. Intermediate values show whether the cap alone accounts for training-time stability and how much frontier improvement it gives up. A second ablation replaces the learned residual with a fixed hand-tuned lookahead bonus, which tests whether learning is needed at all.
Why not just…?
Why not just tune $V$ in classical drift-plus-penalty? This is the real threat. In memoryless problems where actions affect only the current slot, drift-plus-penalty may already sit near the optimal frontier, and the residual would have nothing to learn. The work therefore concentrates on settings where an action has delayed consequences: cache contents that persist across slots, VM placements that cannot be undone cheaply, and inventory carried between periods. Myopia should cost something real there. The frontier comparison will settle this per environment, and we will report honestly if the gain shows up only in the delayed-effect settings.
Why not just train a categorical PPO agent on the tailored Lyapunov reward? RN-D makes that agent trainable, and the LDPTRLQ paper supplies the reward, so this simple combination is a likely competitor. Its weakness is that nothing restrains the policy before convergence. Both the Lyapunov safe RL work and model-based constrained PPO document severe constraint violations during training for unconstrained or Lagrangian learners. Our experiments measure the full time series of virtual-queue length during training, not just the final policy. If categorical PPO matches our controller on both the final frontier and the training-time excursions, the cap adds nothing, and we will say so.
Why not just use PPO-Lagrangian with action masking? Masking enforces hard per-step feasibility, while long-run budgets need a running memory of past overspending. A Lagrange multiplier provides that memory, but its oscillation is the documented failure in model-based constrained PPO, which needed an extra safety buffer to suppress violations. Running the same masked environments under both methods will show whether the virtual queue gives smoother constraint tracking at equal reward.
Why not just relax the discrete choice with Sinkhorn or Gumbel-Softmax? For splittable traffic this is legitimate, and we include it on routing. For indivisible offloading, cache slots, and VM placement, the relaxed action cannot be executed. Rounding it afterwards breaks the per-slot bound on which the guarantee rests, and our exact enumeration avoids that problem.
Proposed Experiments and Decisive Checks
On each environment we trace cost versus average backlog by sweeping $V$ for every method, using at least five seeds. We report the area between each method's frontier and the drift-plus-penalty frontier. We also report peak and 95th-percentile virtual-queue length during training, the fraction of slots where the residual overturns the drift-plus-penalty choice, the time per decision, and the total training time.
The first decisive check is whether the residual frontier lies strictly below classical drift-plus-penalty at small $V$ on the delayed-effect environments: caching, budgeted VM packing on Azure traces, and budgeted inventory.
The second is whether, throughout training, the residual controller's backlog stays within the theoretical envelope implied by $C_0 + 2B$, while categorical PPO on the tailored reward exceeds it early in training.
The third is whether the gain vanishes on the memoryless MEC offloading setting, as the myopia argument predicts. Confirming that would show the mechanism is long-horizon credit assignment rather than generic extra capacity.
A stress test with non-stationary arrival rates checks whether the automatic return to drift-plus-penalty under long queues keeps the controller stable when the learned residual is wrong. Together with the released benchmarks, these results would give the first standardized, quantified answer to whether learning improves on drift-plus-penalty for discrete decisions, and at what training cost.
References
- A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability
- A neural drift-plus-penalty algorithm for network power allocation and routing
- AoI-Delay Tradeoff in Mobile Edge Caching: A Mixed-Order Drift-Plus-Penalty Method
- Accuracy-Guaranteed Collaborative DNN Inference in Industrial IoT via Deep Reinforcement Learning
- A Lyapunov-based Approach to Safe Reinforcement Learning
- Constrained Deep Q-Learning Gradually Approaching Ordinary Q-Learning
- RN-D: Discretized Categorical Actors for On-Policy Reinforcement Learning
- OR-Gym: A Reinforcement Learning Library for Operations Research Problem
- Model-based Safe Deep Reinforcement Learning via a Constrained Proximal Policy Optimization Algorithm