When a packet will arrive after its deadline, delivering it is worse than useless. It occupies the link and delays every packet queued behind it, so those packets start missing their deadlines too. The best current method, Delta, handles this with a learned model of link delay. Each time a packet arrives, it searches over every possible subset of queued packets to drop. That search grows as $2^N$ in the queue length $N$, so Delta only optimizes the first 15 packets (Mostafavi et al. 2023). It is a clean example of the "discrete action space limitation" studied in reinforcement learning (RL): a combinatorial choice too large to enumerate.
This note argues that, in this domain, the limitation comes from how the problem is represented rather than from the problem itself. Delta's delay model conditions each packet's delay only on how many packets are still ahead of it. The expected number of on-time deliveries is therefore a sum of per-packet terms, and each term depends only on that packet's position and a running count of kept packets. An exact dynamic program over (position, count kept) then solves Delta's own objective in $O(N^2)$ time instead of $O(2^N)$. With the search this cheap, the remaining budget can go to what Delta cannot do at all. It can add a learned correction for the effect of today's decisions on future arrivals, it can decide whether to retransmit lost packets, and it can tune a continuous transmit-power setting by simple outer search, with no need for hybrid-action RL machinery.
Core Claim
Let the queue hold packets $i=1,\dots,N$ in FIFO order. Let $v_i\in\{0,1\}$ mark whether packet $i$ is kept, let $\delta_i$ be its remaining time budget, and let $k_i=\sum_{j<i}v_j$ be the number of kept packets ahead of it. Let $F_k(\delta)$ be the probability, under the learned delay model, that a packet with $k$ kept predecessors is delivered within $\delta$. By linearity of expectation, the expected on-time count is
$$J(v)=\sum_{i=1}^{N} v_i\,F_{k_i}(\delta_i),$$
and it is maximized exactly by the backward recursion
$$V_i(k)=\max\big(V_{i+1}(k),\;F_k(\delta_i)+V_{i+1}(k+1)\big),\qquad V_{N+1}(k)=\lambda\,W(k).$$
Here $V_i(k)$ is the best achievable on-time count from position $i$ onward given $k$ kept predecessors. $W(k)$ is a learned estimate of how much a residual backlog of $k$ packets hurts future arrivals, and $\lambda$ weights that term. With $\lambda=0$ the recursion reproduces Delta's myopic objective exactly, in $N^2$ table lookups.
Delta's papers describe the delay model as conditioned on the number of backlogged predecessors (Mostafavi et al. 2021). The first experiment verifies that the decomposition matches Delta's actual objective, not just the summary of it.
The idea links the two directions as follows. Li, Ju, and Shroff (2024) show that grouping similar actions trades a little bias for a large cut in estimation variance, using groupings designed by hand. Here the grouping by count kept costs no bias at all, because it is a sufficient statistic for the objective. The bias only appears when the model is enriched, for example with variable packet sizes, where the state becomes total kept work and has to be discretized. The discretization width is then an explicit, measurable form of Li et al.'s bias-variance knob.
Research Program
The first stage is verification and scaling. We re-implement Delta's Gamma-service FIFO queue (Mostafavi et al. 2023) and confirm that for $N\le 15$ the dynamic program returns the same drop vector as exhaustive tree search. We then run the program on buffers of hundreds of packets. The open question it answers is whether the $N=15$ cap was costing Delta deliveries in deep queues, particularly with several flows whose deadlines are not ordered like FIFO positions.
The second stage removes myopia. Delta optimizes only over packets already queued. The terminal term $W(k)$ is a scalar function of backlog, so it is cheap to learn. We fit it by temporal-difference regression on simulated rollouts. This is the single place RL enters. The critic's input is one integer rather than a $2^N$ action set, which is why we expect it to need far fewer samples than DeepQ-style end-to-end control. This is the same scaling argument Li et al. make, applied to a critic over one integer.
The third stage adds retransmission. Following the delay-field NACK idea of Schoutteet et al., a lost head-of-line packet can be retransmitted or discarded. A retransmission adds one service time plus a round trip. The state becomes (position, discretized kept work), and "retransmit packet $i$" becomes a third branch in the recursion with its own success probability. This joint drop-and-retransmit decision is the setting that neither Delta (which only drops) nor Schoutteet et al. (who suppress retransmission one packet at a time) addresses.
The fourth stage adds one continuous knob, the transmit power for the next attempt. It sets the loss probability and service time following the finite-blocklength tradeoff in She, Yang, and Quek (2017). Because the discrete inner problem now costs $O(N^2)$, we choose power by a one-dimensional grid or golden-section search that calls the dynamic program at each candidate. This is deliberately simpler than parameterized-action networks. The claim to be tested is that once the discrete part has exploitable structure, hybrid-action RL is unnecessary here.
Baselines
The naive reference points are FIFO tail drop and deadline-expiry eviction in the style of Guan et al., which removes a packet only once its budget has run out. CoDel is included because it is the deployed delay-based queue manager. These tell us how much any predictive method buys.
The strongest existing method is Delta itself with its $N=15$ truncated tree search (Mostafavi et al. 2023). For the metric that matters, failed-tasks ratio, I found no reported numerical result on Lacuna. The file states only that at 96.7% link utilization Delta beat CoDel and DeepQ and approached an offline-optimum policy with perfect future knowledge. It also reports that Delta's mixture density network was stable when trained on 4,096 samples and inadequate at 512.
To make the comparison fair, every method uses the same trained delay model: the same 4,096-sample training set and the same $F_k$ tables. Only the decision procedure differs, and all methods run at the same utilizations, 91.6% and 96.7%. Beating Delta means the following. At $N\le15$, the $\lambda=0$ dynamic program must match it exactly. With deep buffers and multiple flows, it must show a lower failed-tasks ratio with non-overlapping confidence intervals over seeds. At all sizes, its per-decision compute must be lower.
The learned-policy baselines are DeepQ, as benchmarked in Delta, and a parameterized-action agent in the style of P-DQN (Xiong et al. 2018) for the retransmit-and-power setting. Both get the same simulator-sample budget as our critic $W$ and equal hyperparameter-tuning trials.
A greedy baseline keeps packets in order whenever $F_{k}(\delta_i)$ exceeds a tuned threshold.
Three ablations isolate the ingredients: $\lambda=0$ versus the learned $W$ (effect of the future-arrival term), work discretization widths (bias versus resolution), and Delta's delay model versus the true delay distribution plugged into the dynamic program (errors from the delay model versus errors from the search).
Why not just…?
Why not just keep a packet whenever its own on-time probability is high enough? This greedy rule is the most serious threat. It is also an $O(N)$ pass and uses the same delay model. Its failure mode is exactly the cascading delay problem. It keeps a marginally viable packet that then dooms several tight-deadline packets behind it, and only a joint optimization sees that tradeoff. Whether this happens often enough to matter is an empirical question. We measure the gap between greedy and the exact optimum across utilization levels and deadline heterogeneity. If greedy stays within 1% everywhere, we will report that the exact search is unnecessary in practice. The contribution then narrows to the future-arrival term and joint retransmission, both of which greedy lacks.
Why not just keep Delta's truncation at 15? Deep packets under FIFO often have plenty of slack, so truncation may cost little. That does not hold when flows with different deadlines share a queue. We measure how often the untruncated optimum changes a decision beyond position 15, and what that does to the failed-tasks ratio.
Why not just use hybrid-action or latent-action RL? HyAR (Li et al. 2022) needs a warm-up phase with random exploration and assumes roughly single-peaked action distributions. Drop decisions near a deadline are sharply bimodal, which violates that assumption. Both HyAR and P-DQN approximate a problem that here has an exact cheap solution. The P-DQN baseline at matched sample budget tests this directly.
Why not just solve a linear program, as in multihop deadline scheduling? The flow-based relaxation in Near-Optimal Packet Scheduling provides guarantees for traffic in aggregate, but it has no per-packet predictive eviction and no continuous power control. We treat its multihop setting as future work rather than as a competitor on single-queue decisions.
Proposed Experiments
We use the Gamma-service FIFO queue from Delta at 91.6% and 96.7% utilization. Buffers range from 15 to 500 packets, and traffic runs with one flow and with three flows at 20, 50, and 100 ms deadlines. For the retransmission and power stage, we add Bernoulli and two-state bursty losses and a finite-blocklength power model following She et al.
The metrics are failed-tasks ratio, delay quantiles from 0.80 to 0.999, per-decision compute time, and, in the power stage, energy per on-time packet.
Four checks are decisive. First, exact agreement with Delta's tree search at $N\le15$. Second, the gap between greedy and exact, and between truncated and full search, as queue depth grows. Third, whether the learned $W$ reduces failed tasks at 96.7% load relative to $\lambda=0$ while using fewer samples than DeepQ. Fourth, whether the dynamic program with outer power search matches or beats the P-DQN baseline on on-time delivery per unit energy.
A negative result on the first check, meaning Delta's objective does not in fact decompose, would redirect the work toward identifying which delay-model assumptions do allow exact decomposition.
References
- Active Queue Management with Data-Driven Delay Violation Probability Predictors
- Data-Driven End-to-End Delay Violation Probability Prediction with Extreme Value Mixture Models
- Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping
- An UDP protocol booster for multimedia communications over 802.11 wireless LAN.
- Cross-Layer Optimization for Ultra-Reliable and Low-Latency Radio Access Networks
- Joint QoS provisioning and congestion control for multi-hop wireless networks
- Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space
- HyAR: Addressing Discrete-Continuous Action Reinforcement Learning via Hybrid Action Representation
- Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints