🤖 machine learning

Online Packet Scheduling with Deadlines and Learning

This paper addresses the Online Packet Scheduling with Deadlines problem under partial feedback by establishing a connection to sleeping bandits, proposing algorithms that achieve optimal $\alpha$ -regret bounds of $\widetilde{\mathcal{O}}(\sqrt{KT})$ , and demonstrating that for finite packet types, deterministic strategies can surpass the classical competitive ratio barrier of $\frac{1+\sqrt{5}}{2}$ .

Original authors: Gianmarco Genalti, Achraf Azize, Vianney Perchet

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gianmarco Genalti, Achraf Azize, Vianney Perchet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a very busy, high-speed post office. Every second, new letters (packets) arrive at your desk. Each letter has a specific deadline by which it must be mailed, or it becomes worthless and gets thrown away.

Here is the tricky part: You don't know how "important" or "valuable" each letter is until you actually mail it. Maybe a letter is just a junk flyer, or maybe it's a winning lottery ticket. You only find out the value after you've sent it.

Your goal is to mail as many high-value letters as possible before their deadlines expire. This is the core problem the paper tackles, called Online Packet Scheduling with Deadlines.

The Twist: Learning While You Go

In the past, computer scientists assumed the post office manager had to make decisions based on pure guesswork or rigid rules. This paper introduces a new idea: Learning.

Imagine you have a box of different types of envelopes (let's say there are $K$ types). You know that "Type A" envelopes usually contain valuable letters, while "Type B" usually contain junk. But you don't know the exact average value yet. You have to figure it out by mailing some and seeing what happens.

The paper asks: Can we build a manager who learns which envelopes are valuable while still meeting all the deadlines, without losing too much money in the process?

The "Sleeping" Problem

The authors compare this to a game called the "Sleeping Bandit." Imagine you are a gambler with $K$ different slot machines.

In a normal game, all machines are available.
In the "Sleeping" version, some machines are "asleep" (unavailable) at any given moment. You can only pull the levers of the machines that are awake.
You don't know which machine pays out the most, and you have to learn while playing.

The paper proves that the post office problem is actually a fancy, harder version of this gambling game. The "sleeping" machines are the packets that haven't arrived yet or have already expired.

The Results: Beating the "Golden Ratio"

For decades, experts believed there was a hard limit to how well a manager could perform in this scenario. They called this limit the Golden Ratio (about 1.618). It meant that even the best possible manager would, in the worst case, only achieve about 62% of the value of a "perfect" manager who knew the future.

This paper breaks that barrier in specific situations:

The Deterministic Manager (The Strict Planner):
If the post office only deals with a fixed, finite number of envelope types (e.g., only 2 or 3 types of envelopes), the authors created a new algorithm called ALGθ.
- The Analogy: Instead of using a rigid rule, this manager uses a dynamic "smart scale." It weighs the urgency of a letter against its estimated value.
- The Result: When there are only a few types of letters, this manager can beat the Golden Ratio limit, getting closer to 1.41 (the square root of 2) in the best cases. It's like finding a secret shortcut that the old rules didn't allow.
The Randomized Manager (The Lucky Gambler):
The paper also looks at managers who are allowed to flip a coin to make decisions.
- The Analogy: Sometimes, being slightly unpredictable helps. If you always do the same thing, a tricky opponent (or a chaotic system) can exploit you. By mixing things up, the manager can avoid getting stuck in bad patterns.
- The Result: These "coin-flipping" managers can achieve an even better performance ratio (1.25) in short-deadline scenarios, matching the best theoretical limits known for random strategies.

How They Do It: Confidence Intervals

Since the manager doesn't know the true value of the letters, they use a tool called Confidence Intervals.

The Metaphor: Imagine the manager keeps a "best guess" and a "worst guess" for every envelope type.
- UCB (Upper Confidence Bound): "This envelope might be worth a lot, so let's be optimistic and try it."
- LCB (Lower Confidence Bound): "This envelope is probably safe, but let's be cautious."
The algorithms constantly update these guesses. If an envelope type keeps delivering high value, the "best guess" goes up, and the manager prioritizes it. If it's usually junk, the manager stops wasting time on it.

The Bottom Line

The paper shows that by combining learning (figuring out values on the fly) with scheduling (meeting deadlines), we can build systems that are smarter than previously thought possible.

For simple systems (few types of packets): We can beat the long-standing "Golden Ratio" barrier and get much closer to perfect performance.
For complex systems: We can still achieve the best possible performance limits known in mathematics, ensuring that even with uncertainty, the system remains highly efficient.

In short, the paper teaches us how to be a better post office manager when you don't know the value of the mail until you've already sent it, proving that learning on the job can lead to near-perfect results.

Technical Summary: Online Packet Scheduling with Deadlines and Learning

Problem Definition

The paper addresses the Online Packet Scheduling with Deadlines (OPSD) problem, a theoretical framework modeling Quality-of-Service (QoS) buffer management where packets arrive with specific deadlines and must be processed or discarded. In the standard OPSD setting, an algorithm must decide which packet to transmit at each clock cycle to maximize total weight, without knowing future arrivals.

The authors introduce a novel variant called Stochastic Online K-Packet Scheduling with Deadlines (K-OPSD). In this setting:

Packets belong to one of $K$ distinct types known to the scheduler.
The actual weight of a packet is unknown until it is processed; instead, weights are sampled from a probability distribution specific to the packet's type.
The scheduler operates under partial feedback (bandit setting), observing weights only after execution.
The goal is to maximize expected cumulative gain while minimizing $\alpha$ -regret, defined as $R_{\alpha, T} = \mathbb{E}[G_{OPT}] - \alpha \mathbb{E}[G_{ALG}]$ , where $G_{OPT}$ is the expected gain of an optimal scheduler that knows the mean weights of all types.

The paper distinguishes between deterministic algorithms (where decisions are predictable given the history) and randomized algorithms. It focuses on specific constraints regarding "slackness," particularly $s$ -bounded instances where a packet's deadline is at most $s-1$ cycles after its arrival.

Methodology

The authors establish a connection between K-OPSD and the Sleeping Bandits problem, where the set of available actions (packet types) changes adversarially at each round. They leverage techniques from Multi-Armed Bandits (MAB), specifically Upper Confidence Bounds (UCB) and Lower Confidence Bounds (LCB), to handle the uncertainty of packet weights.

The core methodology involves:

Confidence Bounds: Constructing UCBs and LCBs for the mean weights of packet types based on observed samples. The confidence width $\beta_{i,t}$ scales with $\sqrt{\frac{\log(KT)}{N_i(t)}}$ .
Charging Schemes: To analyze $\alpha$ -regret, the authors employ charging schemes that map the actions of the algorithm to the optimal schedule (OPT). This is non-trivial because a single decision in K-OPSD alters the buffer state for future rounds, unlike in standard MABs where actions are independent.
Epoch-Based Analysis: For deterministic algorithms, the schedule is divided into "epochs" based on specific termination conditions (e.g., when a packet with a specific deadline is processed). This allows for bounding the competitive ratio within each epoch.
Potential Functions: For randomized algorithms, the analysis utilizes potential functions to quantify the advantage of the algorithm over OPT, accounting for the stochastic nature of both the environment and the algorithm's decisions.

Key Contributions and Results

1. Deterministic Algorithms

$\Phi$ -Regret in 2/3-Bounded Settings: The authors propose EDF $^\Phi_L$ , an adaptation of the $\beta$ -Ratio Earliest Deadline First algorithm using UCBs. They prove this algorithm achieves a $\Phi$ -regret (where $\Phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ ) bounded by $\tilde{O}(\sqrt{KT})$ . This matches the regret bounds of the AUER algorithm for Sleeping Bandits.
Breaking the $\Phi$ Barrier: In the 2-bounded setting with a finite number of types $K$ $K$ , the paper introduces ALG $_\theta$ . This algorithm solves a system of equations to determine a dynamic threshold $\theta_K$ $θ_{K}$ .
- Result: ALG $_\theta$ achieves a competitive ratio of $\theta_K$ , where $\theta_K \in [\sqrt{2}, \Phi)$ . As $K \to \infty$ , $\theta_K \to \Phi$ . This is the first result to improve upon the well-established $\Phi$ lower bound for deterministic algorithms in bounded-delay scheduling when $K$ is finite.
Learning with $\theta_K$ -Regret: The algorithm is extended to ALG $_{\theta, U}$ , which uses UCBs instead of true weights. It achieves a $\theta_K$ -regret upper bound of $\tilde{O}(\sqrt{KT})$ .
Lower Bounds: A lower bound of $\Omega(\sqrt{T})$ is proven for the $\theta_K$ -regret in 2-bounded $(K+1)$ -OPSD instances, showing that ALG $_{\theta, U}$ is nearly optimal.

2. Randomized Algorithms

$5/4$ -Regret in 2-Bounded Settings: The paper proposes ALG $^R_2$ , a randomized algorithm that achieves a $5/4$ -regret upper bound of $\tilde{O}(\sqrt{KT})$ . This matches the best-known competitive ratio for randomized algorithms in the 2-bounded OPSD setting without learning.
$e/(e-1)$ -Regret in Unbounded Settings: For general $s$ -bounded instances, ALG $^R_s$ is proposed. It achieves an $\frac{e}{e-1}$ -regret upper bound of $\tilde{O}(\sqrt{KT})$ , matching the best existing competitive ratio for randomized algorithms in the general OPSD setting.
Technical Distinction: The authors note that while deterministic learning algorithms rely solely on UCBs (optimism), randomized algorithms in this setting require both UCBs and LCBs to handle the ratios of estimates naturally.

Significance and Claims

The paper claims to be the first work exploring the interplay between bandit learning and online packet scheduling with deadlines. Its primary significance lies in:

Generalization: It strictly generalizes the $K$ -armed Sleeping Bandit problem to the K-OPSD setting, providing a theoretical framework for learning in QoS buffer management.
Breaking Barriers: It demonstrates that the assumption of a finite number of packet types ( $K$ ) allows deterministic algorithms to break the long-standing $\Phi$ competitive ratio barrier, achieving a tighter ratio $\theta_K$ .
Tight Regret Bounds: The proposed algorithms achieve $\alpha$ -regret upper bounds of $\tilde{O}(\sqrt{KT})$ , which match the lower bounds for standard bandit settings, indicating that the added complexity of deadlines does not degrade the learning rate.
Practical Motivation: The work is motivated by real-world applications such as QoS buffer management in digital advertising (auctions with short lifespans) and sensor networks, where decisions must be made with unknown rewards under strict deadlines.

The authors conclude that while they have established tight bounds for specific scenarios (particularly 2-bounded instances), challenges remain for general instances and for combining randomization with the finite-type assumption to further lower competitive ratios.