Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning

In safety-critical IoT systems like industrial control or remote teleoperation, the system must ensure that the peak Age of Information (AoI) for every sensor remains below a hard deadline at every single time slot. Traditional approaches, such as Whittle-index scheduling or standard online convex optimization (OCO), either rely on restrictive stochastic channel assumptions or allow for cumulative constraint violations that can lead to system instability. This paper asks: can we design a scheduling framework that provides both zero per-slot deadline violations and no-regret learning performance in adversarial environments?

The authors observe that the peak-AoI deadline constraint can be mathematically reduced to an affine half-space constraint on the resource-allocation vector. This transformation allows the authors to treat hard real-time scheduling as a time-varying constrained online convex optimization problem. They propose the OCO-PAoI-Hard algorithm, which utilizes a strictly causal proposal-shield-update loop. In each slot, the algorithm generates a gradient-based proposal, which is then projected onto a polyhedral safe set (the 'shield') to ensure feasibility. A virtual queue is maintained, but only as an a-posteriori certificate of safety rather than as the primary mechanism for enforcing constraints.

OCO-PAoI-Hard achieves zero modeled-state deadline violations across all tested scenarios, outperforming representative baselines that suffer from significant miss rates (ranging from 1.65% to 64.0%). The algorithm provides theoretical guarantees of O(sqrt(T)) static and dynamic regret, matching the minimax lower bound for this class of problems. The authors also provide a margin-safe variant to handle execution noise and demonstrate that the empirical normalized regret remains within the theoretical envelope across multiple orders of magnitude in the time horizon.