# Online Packet Scheduling with Deadlines and Learning

arXiv: https://arxiv.org/abs/2606.00835 · HTML: https://mlsanity.com/paper/2606.00835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 7 of 7)

- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [On Preemption and Learning in Stochastic Scheduling](https://mlsanity.com/paper/2205.15695/) (2022)
- [Learning-Augmented Online Packet Scheduling with Deadlines](https://mlsanity.com/paper/2305.07164/) (2023)
- [A φ-Competitive Algorithm for Scheduling Packets with Deadlines](https://mlsanity.com/paper/1807.07177/) (2018)
- [Online Weighted Paging with Unknown Weights](https://mlsanity.com/paper/2410.21266/) (2024)

## Abstract (arXiv)

Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit, even when the value of the packet is unknown until it is processed. We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback: packets arrive at every clock cycle, with different deadlines, but the weights are only observed after execution. Under a stochastic assumption on the unknown weights, we explore different variants of the OPSD problem with bandit feedback. We establish a connection between our setting and the sleeping bandits problem, and set our learning goal to α-regret minimization. We provide algorithms with provable α-regret guarantees under different spans of slackness, distinguishing systems allowing for randomization and systems that do not. In every scenario, our algorithms achieve an α-regret upper bound of widetildeOleft(√KTright), matching the lower bound for the standard bandit setting. In the practically relevant case of 2-bounded deadline instances, where the deadline is set at most one clock cycle away from the arrival, our deterministic algorithm achieves the provably tightest possible competitive ratio. Remarkably, when the number of distinct packet types K≥ 2 is finite, it is possible to break the well-established Phi = frac1+√52 competitive ratio barrier and attain a tighter competitive ratio θK ranging in [√2, Phi).