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

# Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning
Source: [https://arxiv.org/html/2607.27626](https://arxiv.org/html/2607.27626)
###### Abstract

Safety\-critical IoT systems such as industrial closed\-loop control, V2X coordination, and remote teleoperation require every sensor’s peak Age of Information \(peak AoI, also abbreviated PAoI\) to stay below a hard per\-slot deadline, not merely an average bound\. Existing approaches meet this requirement only under restrictive assumptions: stochastic channels for Whittle\-index AoI, simulator rollouts for deep reinforcement learning, or sublinear cumulative violation for long\-term constrained online convex optimization\.Under adversarial coefficients, OCO\-PAoI\-Hard guarantees zero per\-slot violation of the modeled AoI state under one\-step viability andO​\(T\)O\(\\sqrt\{T\}\)regret against any static safe comparator; packet\-level safety requires stronger service assumptions\.Our key observation is that the fractional peak\-AoI deadline collapses exactly to an affine half\-space constraint on theresource\-allocation vector, turning hard real\-time scheduling into time\-varying constrained online convex optimization over a polyhedral safe set\. A strictly causal proposal\-shield\-update loop enforces feasibility through one Euclidean projection per slot, the gradient step preserves no\-regret behaviour, and the classical virtual queue is reduced to an a\-posteriori certificate\. We establish closed\-form static and dynamic regret bounds, a matchingΩ​\(T\)\\Omega\(\\sqrt\{T\}\)minimax lower bound, a margin\-safe variant against execution noise, and a deadline\-induced competitive ratio\.On a four\-sensor adversarial fluid\-model trap channel, OCO\-PAoI\-Hard attains zero modeled\-state deadline violations across all ten seedswhile four representative baselines miss between1\.65%1\.65\\%and64\.0%64\.0\\%of slots, and the empirical normalized regret stays below the theoretical envelope across two orders of magnitude inTT\.

## IIntroduction

Safety\-critical wireless cyber\-physical systems, including industrial closed\-loop control, V2X coordination, remote surgery, smart\-grid protection, and immersive XR teleoperation, push real\-time networking well beyond best\-effort throughput\. What determines correctness is not how often a sensor’s data arrives, but how recent the controller’s last fresh sample is, captured by the Age of Information \(AoI\) metric\[[20](https://arxiv.org/html/2607.27626#bib.bib2),[30](https://arxiv.org/html/2607.27626#bib.bib3)\]\. The bottleneck is the worst\-case AoI rather than its average: IEC 61850\-5 assigns protection samples to transfer\-time class TT6 \(≤3​ms\\leq 3\\,\\mathrm\{ms\}\), and 3GPP specifies a general URLLC packet\-success probability of1−10−51\-10^\{\-5\}for 32 bytes within1​ms1\\,\\mathrm\{ms\}user\-plane latency\[[13](https://arxiv.org/html/2607.27626#bib.bib4),[1](https://arxiv.org/html/2607.27626#bib.bib5)\], so a single missed deadline trips a circuit breaker, derails a haptic\-feedback loop, or destabilizes a V2X platoon\. Multi\-sensor IoT systems must therefore meet a per\-sensor peak\-AoI deadline at every slot while sharing a wireless link subject to fading, interference, and adversarial blockers\. The question we address is whether sensors can be scheduled over an adversarial shared channel so that every sensor’s peak AoI stays below its deadline at every slot, while a good policy is still learned online\.

Three decades of work approach this question along progressively weaker assumptions, but none answers it completely\. The classical Markovian line, including restless multi\-armed bandits and the Whittle\-index AoI scheduler, treats freshness as a soft cost and proves index\-optimality under i\.i\.d\. or Markovian channel statistics\[[17](https://arxiv.org/html/2607.27626#bib.bib6),[22](https://arxiv.org/html/2607.27626#bib.bib7),[28](https://arxiv.org/html/2607.27626#bib.bib8)\], but the argument collapses once channels become non\-stationary\. Deep reinforcement learning replaces model\-based analysis with end\-to\-end policy search\[[21](https://arxiv.org/html/2607.27626#bib.bib9),[11](https://arxiv.org/html/2607.27626#bib.bib10),[2](https://arxiv.org/html/2607.27626#bib.bib11)\], delivering strong empirical reward but offering neither regret nor violation guarantees\. A third line brings adversarial robustness through online competitive analysis\[[5](https://arxiv.org/html/2607.27626#bib.bib12),[9](https://arxiv.org/html/2607.27626#bib.bib13),[26](https://arxiv.org/html/2607.27626#bib.bib14)\], but the guarantee is on a long\-run ratio rather than a per\-slot per\-sensor deadline\. In parallel, drift\-plus\-penalty and long\-term virtual\-queue OCO methods\[[32](https://arxiv.org/html/2607.27626#bib.bib15),[18](https://arxiv.org/html/2607.27626#bib.bib16),[23](https://arxiv.org/html/2607.27626#bib.bib17)\]achieve simultaneousO​\(T\)O\(\\sqrt\{T\}\)regret ando​\(T\)o\(T\)cumulative constraint violation, yet explicitly allow individual slots to violate the deadline as long as the running total grows sublinearly\. Even an algorithm withO​\(1\)O\(1\)cumulative violation can still miss a deadline in some slot, which under the weakly\-hard\(m,k\)\(m,k\)\-firm semantics\[[8](https://arxiv.org/html/2607.27626#bib.bib18),[15](https://arxiv.org/html/2607.27626#bib.bib19),[25](https://arxiv.org/html/2607.27626#bib.bib20)\]is precisely the failure mode that propagates to control\-loop instability\.No existing framework simultaneously offers zero per\-slot violation of the modeled peak\-AoI state,O​\(T\)O\(\\sqrt\{T\}\)no\-regret adaptation, and robustness to adversarial coefficient traces\.

This paper proposes OCO\-PAoI\-Hard, a scheduling framework that closes all three gaps with a single causal algorithm\. The starting point is a structural observation\. Under themodeledAoI dynamics, the per\-sensor peak\-AoI deadline collapses exactly, without any slack, to an affine half\-space constraintCt​x≥θtC\_\{t\}x\\geq\\theta\_\{t\}on thefractional resource allocation, whereCtC\_\{t\}encodes the realized channel, fresh\-arrival, and common\-observation pattern in slottt, andθt\\theta\_\{t\}is a refresh threshold determined by the current AoI and deadline vectors\. This reduction turns hard real\-time AoI scheduling into time\-varying constrained OCO over a polyhedral safe set𝒦t\\mathcal\{K\}\_\{t\}\. We then build a strictly causal proposal\-shield\-update loop: a gradient proposalztz\_\{t\}is hardened into a feasible actionxtx\_\{t\}by Euclidean projection onto𝒦t\\mathcal\{K\}\_\{t\}, the executed action incurs lossft​\(xt\)f\_\{t\}\(x\_\{t\}\), and the gradient update produceszt\+1z\_\{t\+1\}\.The shield enforces the modeled\-state deadline at every realized state–refresh pair for which𝒦t≠∅\\mathcal\{K\}\_\{t\}\\neq\\varnothing; this non\-emptiness is necessary for any current action to meet all modeled deadlines from that state\.The virtual queue is retained only as a zero\-violation certificate\. Table[I](https://arxiv.org/html/2607.27626#S1.T1)contrasts our guarantees with the four prior families\.On a four\-sensor adversarial fluid\-model trap channel, OCO\-PAoI\-Hard records zero modeled\-state deadline violationsacross all1010seeds \(max numerical excess≤10−12\\leq 10^\{\-12\}\), whereas vanilla OGD, drift\-plus\-penalty, greedy max\-deficit, and round\-robin baselines suffer per\-slot miss rates of41\.3%41\.3\\%,1\.65%1\.65\\%,64\.0%64\.0\\%, and63\.6%63\.6\\%, respectively, and the empirical static regret normalized byR​G​TRG\\sqrt\{T\}stays below0\.40\.4acrossT∈\[200,2×104\]T\\in\[200,2\\\!\\times\\\!10^\{4\}\], in agreement with theO​\(T\)O\(\\sqrt\{T\}\)theory\.

TABLE I:Comparison with representative AoI and constrained\-OCO scheduling frameworks\. “Hard PAoI” is the strongest per\-sensor peak\-AoI guarantee provided, and “Regret” is the static\-regret order over horizonTT\. “Sim/stoch\.” denotes simulator\-trained or stochastic\-channel assumptions\.MethodChannelHard PAoIRegretWhittle AoI\[[17](https://arxiv.org/html/2607.27626#bib.bib6),[22](https://arxiv.org/html/2607.27626#bib.bib7)\]i\.i\.d\./Markovsoft costN/ADRL AoI\[[21](https://arxiv.org/html/2607.27626#bib.bib9),[11](https://arxiv.org/html/2607.27626#bib.bib10)\]sim/stoch\.empiricalN/AAdv\. AoI\[[5](https://arxiv.org/html/2607.27626#bib.bib12),[9](https://arxiv.org/html/2607.27626#bib.bib13)\]adversarialtime\-avg\. ratioN/ALT\-OCO\[[32](https://arxiv.org/html/2607.27626#bib.bib15),[18](https://arxiv.org/html/2607.27626#bib.bib16)\]adversarialcumul\.o​\(T\)o\(T\)O​\(T\)O\(\\sqrt\{T\}\)Oursadversarialfluid/expected, per slotO​\(T\)O\(\\sqrt\{T\}\)Our contributions are as follows\.

- •AoI\-to\-safety reduction and algorithm\.We prove thatmodeledpeak\-AoI deadlines reduce exactly to affine half\-space constraints on the fractionalresource allocation, and use this reduction to design OCO\-PAoI\-Hard, a strictly causal proposal\-shield\-update algorithm that, to our knowledge, is the first to deliverO​\(T\)O\(\\sqrt\{T\}\)regret andzero modeled\-state violationunder fully adversarial channel, arrival, and common\-observation sequences,conditional on realized one\-step viability\.
- •Complete theoretical analysis with matching lower bound\.We establish a32​R​G​T\\frac\{3\}\{2\}RG\\sqrt\{T\}static\-regret bound, a path\-length dynamic\-regret boundR​G​T\+G​T​PTRG\\sqrt\{T\}\+G\\sqrt\{T\}\\,P\_\{T\}, a tightΩ​\(T\)\\Omega\(\\sqrt\{T\}\)minimax lower bound, a margin perturbation theoremξ≥L​ε\\xi\\geq L\\,\\varepsilonthat recoversmodeled\-state safetyunder approximate projection and execution noise, a deadline\-induced competitive ratioρD=\(∑iwi​Di\)/W\\rho\_\{D\}=\(\\sum\_\{i\}w\_\{i\}D\_\{i\}\)/W, a regret\-refined trace\-wise ratioαT\+R​G/\(W​T\)\\alpha\_\{T\}\+RG/\(W\\sqrt\{T\}\), and a fractional\-to\-integral interface delineating when fluid guarantees lift to packet\-level execution\.
- •Empirical validation on adversarial channels\.We validate every theoretical prediction on a multi\-sensor adversarial shared\-channel testbed:zero modeled fluid\-state deadline violationsfor our shielded scheduler against four representative baselines, a normalized regret ratio below the theoretical envelope across two orders of magnitude inTT, and a cleanξ≥L​ε\\xi\\geq L\\,\\varepsilonphase boundary on the margin and noise plane\.

## IIRelated Work

Our work bridges three lines of inquiry: AoI scheduling for wireless status updating, constrained online convex optimization, and real\-time scheduling with safety guarantees\.

### II\-AAoI Scheduling for Wireless Status Updates

Since Kaul et al\.\[[20](https://arxiv.org/html/2607.27626#bib.bib2)\]formalized AoI as a freshness metric, an extensive algorithmic toolbox has been built \(see the survey\[[30](https://arxiv.org/html/2607.27626#bib.bib3)\]\)\. For a single source\-channel pair, Sun et al\.\[[27](https://arxiv.org/html/2607.27626#bib.bib21)\]derive optimal samplers under general service distributions, and Bedewy et al\.\[[6](https://arxiv.org/html/2607.27626#bib.bib22)\]extend them to multi\-source preemptive systems with random arrivals and parallel servers\. In the multi\-source shared\-channel regime closest to our setting, the Whittle\-index family\[[17](https://arxiv.org/html/2607.27626#bib.bib6),[22](https://arxiv.org/html/2607.27626#bib.bib7),[28](https://arxiv.org/html/2607.27626#bib.bib8)\]reduces an otherwise intractable restless bandit to per\-source threshold rules under i\.i\.d\. or Markovian channels, and Kadota et al\.\[[19](https://arxiv.org/html/2607.27626#bib.bib23)\]prove matching lower bounds and an asymptotically optimal stationary randomized policy\. Two more recent threads relax these assumptions: online competitive analysis\[[5](https://arxiv.org/html/2607.27626#bib.bib12),[9](https://arxiv.org/html/2607.27626#bib.bib13),[26](https://arxiv.org/html/2607.27626#bib.bib14)\]removes channel stationarity and targets a constant\-competitive ratio for the time\-averaged AoI, while data\-driven schedulers replace analytical optima with deep\-RL policies trained on simulator rollouts\[[21](https://arxiv.org/html/2607.27626#bib.bib9),[11](https://arxiv.org/html/2607.27626#bib.bib10),[2](https://arxiv.org/html/2607.27626#bib.bib11)\]\. All these directions treat AoI as a stochastic cost, a long\-run competitive ratio, or a learning target without provable feasibility;we instead certify the per\-slot invariant of the modeled AoI state, under the scope stated above\.

### II\-BConstrained Online Convex Optimization

The OCO framework\[[36](https://arxiv.org/html/2607.27626#bib.bib24),[16](https://arxiv.org/html/2607.27626#bib.bib25)\]providesO​\(T\)O\(\\sqrt\{T\}\)regret for adversarial convex losses, an information\-theoretically optimal rate even without constraints\. Constrained extensions\[[23](https://arxiv.org/html/2607.27626#bib.bib17),[18](https://arxiv.org/html/2607.27626#bib.bib16),[32](https://arxiv.org/html/2607.27626#bib.bib15),[31](https://arxiv.org/html/2607.27626#bib.bib26)\]achieveO​\(T\)O\(\\sqrt\{T\}\)regret with sublinear cumulative violation under stochastic constraints, and dynamic\-environment work\[[12](https://arxiv.org/html/2607.27626#bib.bib27),[10](https://arxiv.org/html/2607.27626#bib.bib28),[29](https://arxiv.org/html/2607.27626#bib.bib29)\]handles drifting feasible sets and switching costs\.Prediction\-assisted dynamic\-regret methods exploit untrusted per\-round\-minimizer predictions while retaining the optimal prediction\-free rate under adversarial predictions\[[34](https://arxiv.org/html/2607.27626#bib.bib35)\]\. Complementary results give logarithmic dependence on the number of adversarial constraints in each constraint’s cumulative\-violation bound\[[35](https://arxiv.org/html/2607.27626#bib.bib36)\]and, in separate settings, noise\-adaptive high\-probability regret under sub\-Gaussian gradients and simultaneous high\-probability regret/long\-run\-violation guarantees under stochastic constraints\[[33](https://arxiv.org/html/2607.27626#bib.bib37)\]\.Drift\-plus\-penalty and long\-term virtual\-queue methods absorb constraint violations into a sublinear cumulative budget, but explicitly allow individual slots to violate the deadline as long as the running total grows sublinearly; even an algorithm withO​\(1\)O\(1\)cumulative violation can still miss a deadline in some slot\. Our algorithm instead enforces feasibility at every slot through Euclidean projection onto the current\-slot𝒦t\\mathcal\{K\}\_\{t\}, and the virtual queue is reduced from a primary safety mechanism to an a\-posteriori zero\-violation certificate, separating shield from accounting and yieldingper\-slot modeled\-state rather than long\-run guarantees\.

### II\-CHard Real\-Time and Safe\-Learning Schedulers

Classical hard real\-time theory\[[14](https://arxiv.org/html/2607.27626#bib.bib30)\]achieves per\-task deadlines through schedulability analysis with known service rates, while the weakly\-hard\(m,k\)\(m,k\)\-firm model\[[8](https://arxiv.org/html/2607.27626#bib.bib18),[15](https://arxiv.org/html/2607.27626#bib.bib19),[25](https://arxiv.org/html/2607.27626#bib.bib20)\], widely used in the hard real\-time community, relaxes this to “at mostmmmisses in anykk\-window,” yet ultimately relies on a base scheduler that does enforce per\-slot deadlines\. URLLC\[[7](https://arxiv.org/html/2607.27626#bib.bib31),[1](https://arxiv.org/html/2607.27626#bib.bib5)\]delivers sub\-millisecond reliability through resource reservation and packet replication but does not embed an online learning loop\. The safe\-RL literature provides complementary tools: trust\-region projections under expected\-cost constraints\[[3](https://arxiv.org/html/2607.27626#bib.bib32)\], reactive shields filtering unsafe actions in finite\-state MDPs\[[4](https://arxiv.org/html/2607.27626#bib.bib33)\], and zero\-duality\-gap results for constrained MDPs\[[24](https://arxiv.org/html/2607.27626#bib.bib34)\]\. These works depend on offline schedulability tests, on stochastic constrained MDPs with expected\-violation guarantees, or on shields synthesized from pre\-specified safety automata\. Our framework instead derives the safety shield analytically from the AoI dynamics via the affine reductionCt​x≥θtC\_\{t\}x\\geq\\theta\_\{t\}, instantiates it from observations available at the start of each slot, and composes it with an online gradient update so thatzero modeled\-state deadline violations andO​\(T\)O\(\\sqrt\{T\}\)regret hold simultaneously under adversarial traces, conditional on realized one\-step viability\.

## IIIProblem Setup

We consider a single\-cell,NN\-sensor IoT system that shares a wireless uplink to a common controller over a slotted horizont=1,…,Tt=1,\\dots,T\. Vectors are columns;𝟏∈ℝN\\mathbf\{1\}\\in\\mathbb\{R\}^\{N\}is the all\-ones vector andeje\_\{j\}thejj\-th canonical basis vector;∥⋅∥2\\\|\\cdot\\\|\_\{2\}is the Euclidean norm,⟨⋅,⋅⟩\\langle\\cdot,\\cdot\\ranglethe inner product,a⊙ba\\odot bthe Hadamard product,\[y\]\+=max⁡\{y,0\}\[y\]\_\{\+\}=\\max\\\{y,0\\\}, andΠ𝒞​\(y\)=arg⁡minx∈𝒞⁡‖x−y‖2\\Pi\_\{\\mathcal\{C\}\}\(y\)=\\arg\\min\_\{x\\in\\mathcal\{C\}\}\\\|x\-y\\\|\_\{2\}the unique Euclidean projection onto a non\-empty closed convex𝒞⊆ℝN\\mathcal\{C\}\\subseteq\\mathbb\{R\}^\{N\}\. Theunit resource\-allocation simplexisΔN=\{x∈ℝ≥0N:𝟏⊤​x=1\}\\Delta\_\{N\}=\\\{x\\in\\mathbb\{R\}^\{N\}\_\{\\geq 0\}:\\mathbf\{1\}^\{\\top\}x=1\\\}, with diameterR≤2R\\leq\\sqrt\{2\}\.

For reference, Table[II](https://arxiv.org/html/2607.27626#S3.T2)summarizes the principal notation used throughout the paper\.

TABLE II:Principal notation\. Vector inequalities are interpreted coordinatewise\.### III\-ASystem Model and Task Definition

A controller allocates a shared wireless uplink amongNNtransmitters over slotst=1,…,Tt=1,\\ldots,T\. At the beginning of slottt, it observes the current AoI vectorAtA\_\{t\}and the safety side information: the effective refresh matrixCtC\_\{t\}in the nominal setting, or an uncertainty set𝒰t∋Ct\\mathcal\{U\}\_\{t\}\\ni C\_\{t\}in the robust setting\. This side information is obtained before the action from current pilots/channel\-state measurements, packet timestamps and freshness indicators, or calibrated conservative bounds; no future channel or packet outcome is assumed\. The controller then commits toxt∈ΔNx\_\{t\}\\in\\Delta\_\{N\}, wherext,jx\_\{t,j\}is the deterministic fraction of slot\-ttairtime or bandwidth assigned to transmitterjjand𝟏⊤​xt=1\\mathbf\{1\}^\{\\top\}x\_\{t\}=1;xtx\_\{t\}is not a random draw of one transmitter\. Figure[1](https://arxiv.org/html/2607.27626#S3.F1)summarizes this model and the slot timing\.The matrixCtC\_\{t\}admits the optional decomposition

Ct,i​j=Bt,i​j​pt,j​rt,j,C\_\{t,ij\}=B\_\{t,ij\}\\,p\_\{t,j\}\\,r\_\{t,j\},\(1\)whereBt,i​j=1B\_\{t,ij\}=1means that a fresh update transmitted byjjalso refreshes information itemiiat the controller\. ThusBt=IB\_\{t\}=Imodels independent sensors, whereas aggregation, correlated measurements, or overhearing can create off\-diagonal ones\. The factorpt,j∈\[0,1\]p\_\{t,j\}\\in\[0,1\]represents effective link service andrt,j∈\[0,1\]r\_\{t,j\}\\in\[0,1\]fresh\-sample availability, so\(Ct​x\)i∈\[0,1\]\(C\_\{t\}x\)\_\{i\}\\in\[0,1\]is the modeled refresh intensity of itemii\. Under deterministic fractional service, the resulting state is a fluid AoI state; whenpt,jp\_\{t,j\}is a success probability, it is a conditional\-mean AoI state\.

\(a\) Physical meaningxt,jx\_\{t,j\}: deterministic airtime/bandwidth share\(not a random one\-packet draw\)Bt,i​j=1B\_\{t,ij\}=1: transmitterjj’s fresh updatealso refreshes information itemii;Bt=IB\_\{t\}=Iif independent\(b\) Slot\-tttimingRevealAt,CtA\_\{t\},C\_\{t\}or𝒰t\\mathcal\{U\}\_\{t\}Build𝒦t\\mathcal\{K\}\_\{t\}Shieldzt↦xtz\_\{t\}\\mapsto x\_\{t\}Fluid serviceAoI updateRevealft,stf\_\{t\},s\_\{t\}updatezt\+1z\_\{t\+1\}commitpre\-actionpost\-actionFigure 1:System model and slot timing\. The controller obtainsAtA\_\{t\}andCtC\_\{t\}\(or𝒰t∋Ct\\mathcal\{U\}\_\{t\}\\ni C\_\{t\}\) before commitment, allocates deterministic resource sharesxtx\_\{t\}, advances the modeled AoI state, and receives first\-order loss feedback only after execution\.Executingx∈ΔNx\\in\\Delta\_\{N\}produces the affine post\-decision AoI

at\+1i​\(x\)=1\+\(1−\(Ct​x\)i\)​Ati,i∈\[N\],a\_\{t\+1\}^\{i\}\(x\)=1\+\\bigl\(1\-\(C\_\{t\}x\)\_\{i\}\\bigr\)A\_\{t\}^\{i\},\\qquad i\\in\[N\],\(2\)and the system advances byAt\+1i=at\+1i​\(xt\)A\_\{t\+1\}^\{i\}=a\_\{t\+1\}^\{i\}\(x\_\{t\}\)\.

After commitment, the controller receives first\-order OCO feedback\(ft​\(xt\),st\)\(f\_\{t\}\(x\_\{t\}\),s\_\{t\}\)with convexftf\_\{t\}andst∈∂ft​\(xt\)s\_\{t\}\\in\\partial f\_\{t\}\(x\_\{t\}\)\. This is full\-subgradient, not bandit, feedback;sts\_\{t\}affects only the next proposalzt\+1z\_\{t\+1\}\.The canonical instance is the weighted post\-decision AoI,

ftcan​\(x\)\\displaystyle f\_\{t\}^\{\\rm can\}\(x\)=∑i=1Nwi​at\+1i​\(x\)\\displaystyle=\\sum\_\{i=1\}^\{N\}w\_\{i\}\\,a\_\{t\+1\}^\{i\}\(x\)=∑i=1Nwi​\(Ati\+1\)−⟨Ct⊤​\(At⊙w\),x⟩,\\displaystyle=\\sum\_\{i=1\}^\{N\}w\_\{i\}\(A\_\{t\}^\{i\}\+1\)\-\\bigl\\langle C\_\{t\}^\{\\top\}\(A\_\{t\}\\odot w\),\\,x\\bigr\\rangle,\(3\)which is affine inxx, hence convex; any other convex slot\-loss admitted by Assumption[2](https://arxiv.org/html/2607.27626#Thmassumption2)is also allowed\. The slot\-ttdeadline\-violation function and refresh threshold are

gt,i​\(x\)\\displaystyle g\_\{t,i\}\(x\)=at\+1i​\(x\)−Di,\\displaystyle=a\_\{t\+1\}^\{i\}\(x\)\-D\_\{i\},\(4\)θt,i\\displaystyle\\theta\_\{t,i\}=Ati\+1−DiAti,\\displaystyle=\\dfrac\{A\_\{t\}^\{i\}\+1\-D\_\{i\}\}\{A\_\{t\}^\{i\}\},\(5\)and the current\-slot safe set is

𝒦t\\displaystyle\\mathcal\{K\}\_\{t\}=\{x∈ΔN:gt,i​\(x\)≤0,∀i∈\[N\]\}\\displaystyle=\\\{x\\in\\Delta\_\{N\}:g\_\{t,i\}\(x\)\\leq 0,\\,\\forall i\\in\[N\]\\\}=\{x∈ΔN:Ct​x≥θt\},\\displaystyle=\\\{x\\in\\Delta\_\{N\}:C\_\{t\}x\\geq\\theta\_\{t\}\\\},\(6\)where the second equality follows from \([4](https://arxiv.org/html/2607.27626#S3.E4)\)–\([5](https://arxiv.org/html/2607.27626#S3.E5)\) together withAti≥1A\_\{t\}^\{i\}\\geq 1\. We also write𝒦1:T=⋂t=1T𝒦t\\mathcal\{K\}\_\{1:T\}=\\bigcap\_\{t=1\}^\{T\}\\mathcal\{K\}\_\{t\}for the static safe set\.

For any static safe comparatoru∈𝒦1:Tu\\in\\mathcal\{K\}\_\{1:T\}, the trace\-wise static regret is

RegT⁡\(u\)=∑t=1Tft​\(xt\)−∑t=1Tft​\(u\),\\operatorname\{Reg\}\_\{T\}\(u\)=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(u\),\(7\)and for an arbitrary comparator sequenceut∈𝒦tu\_\{t\}\\in\\mathcal\{K\}\_\{t\}the dynamic regret and its path length are

DRegT⁡\(u1:T\)\\displaystyle\\operatorname\{DReg\}\_\{T\}\(u\_\{1:T\}\)=∑t=1Tft​\(xt\)−∑t=1Tft​\(ut\),\\displaystyle=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(u\_\{t\}\),\(8\)PT​\(u1:T\)\\displaystyle P\_\{T\}\(u\_\{1:T\}\)=∑t=1T−1‖ut\+1−ut‖2\.\\displaystyle=\\sum\_\{t=1\}^\{T\-1\}\\\|u\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}\.\(9\)We seek a causal algorithm that,on every realized closed\-loop trace satisfying Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3), simultaneously delivers

RegT\(u\)=O\(T\)andmaxt∈\[T\],i∈\[N\]\[Ati−Di\]\+=0\.\\operatorname\{Reg\}\_\{T\}\(u\)=O\(\\sqrt\{T\}\)\\quad\\text\{and\}\\quad\\max\_\{t\\in\[T\],\\,i\\in\[N\]\}\[A\_\{t\}^\{i\}\-D\_\{i\}\]\_\{\+\}=0\.\(10\)

### III\-BAssumptions

###### Assumption 1\(Slotted system with causal side information\)\.

At every slott∈\[T\]t\\in\[T\]and before committing toxtx\_\{t\}, the controller observesAt∈ℝ\+NA\_\{t\}\\in\\mathbb\{R\}\_\{\+\}^\{N\}andCt∈\[0,1\]N×NC\_\{t\}\\in\[0,1\]^\{N\\times N\}; the AoI evolves by \([2](https://arxiv.org/html/2607.27626#S3.E2)\); and1≤A1i≤Di1\\leq A\_\{1\}^\{i\}\\leq D\_\{i\}for everyi∈\[N\]i\\in\[N\]\.

###### Assumption 2\(Convex losses\)\.

Eachft:ΔN→ℝf\_\{t\}:\\Delta\_\{N\}\\to\\mathbb\{R\}is convex, and there existsG<∞G<\\inftywith‖st‖2≤G\\\|s\_\{t\}\\\|\_\{2\}\\leq Gfor everyst∈∂ft​\(xt\)s\_\{t\}\\in\\partial f\_\{t\}\(x\_\{t\}\)along the trajectory\.

###### Assumption 3\(Realized one\-step viability\)\.

For everyt∈\[T\]t\\in\[T\],𝒦t≠∅\\mathcal\{K\}\_\{t\}\\neq\\varnothing\.

Assumption[1](https://arxiv.org/html/2607.27626#Thmassumption1)is the natural causal information pattern of slotted wireless protocols; futureCt′C\_\{t^\{\\prime\}\}are not revealed, and a robust variant under uncertainty is treated in Section[V\-J](https://arxiv.org/html/2607.27626#S5.SS10)\. The boundCt,i​j∈\[0,1\]C\_\{t,ij\}\\in\[0,1\]is inherent in any probability or airtime interpretation, and the affine fluid dynamic \([2](https://arxiv.org/html/2607.27626#S3.E2)\) is the standard expected\-refresh model; no stationarity, Markovianity, or mixing is imposed on\(Ct\)\(C\_\{t\}\)\. The initial\-safety part is necessary:A1i\>DiA\_\{1\}^\{i\}\>D\_\{i\}already misses a deadline\. Assumption[2](https://arxiv.org/html/2607.27626#Thmassumption2)accommodates the canonical AoI loss, soft\-max approximations of peak\-AoI, and linear losses; whenAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}along the trajectory \(which our algorithm enforces\),ftcanf\_\{t\}^\{\\rm can\}is automatically Lipschitz withGcan≤N​∑iwi​DiG\_\{\\rm can\}\\leq\\sqrt\{N\}\\sum\_\{i\}w\_\{i\}D\_\{i\}\. We do not require𝒦1:T≠∅\\mathcal\{K\}\_\{1:T\}\\neq\\varnothingexcept where the static\-regret theorem explicitly states so\.

## IVThe OCO\-PAoI\-Hard Algorithm

We now describe the proposed scheduler\. Its top\-level form is a strictly causal proposal\-shield\-update \(PSU\) loop:

zt→Π𝒦txt→xt−ηt​st,ΠΔNzt\+1,z\_\{t\}\\ \\xrightarrow\{\\ \\Pi\_\{\\mathcal\{K\}\_\{t\}\}\\ \}\\ x\_\{t\}\\ \\xrightarrow\{\\ x\_\{t\}\-\\eta\_\{t\}s\_\{t\},\\ \\Pi\_\{\\Delta\_\{N\}\}\\ \}\\ z\_\{t\+1\},\(11\)in which an unconstrained OCO iteratezt∈ΔNz\_\{t\}\\in\\Delta\_\{N\}is first hardened into the executed actionxtx\_\{t\}by a single Euclidean projection onto the current\-slot safe set𝒦t\\mathcal\{K\}\_\{t\}\(the shield\), and the gradient step is then anchored atxtx\_\{t\}, not atztz\_\{t\}, to produce the next proposal\. Compared with classical drift\-plus\-penalty schedulers, the loop separates three concerns that are usually conflated:*state observation*\(line 3\),*safety enforcement*\(lines 4–5\), and*regret minimization*\(lines 10–11\)\. Algorithm[1](https://arxiv.org/html/2607.27626#alg1)states the resulting procedure, and the virtual queueQtQ\_\{t\}is retained only as an a\-posteriori zero\-violation certificate, not as a primary safety mechanism\. We comment on each step below and discuss implementation aspects thereafter\.

Algorithm 1OCO\-PAoI\-Hard: causal proposal\-shield\-update\.0:deadlines

D∈ℝ\+ND\\\!\\in\\\!\\mathbb\{R\}\_\{\+\}^\{N\}, weights

w∈ℝ\+Nw\\\!\\in\\\!\\mathbb\{R\}\_\{\+\}^\{N\}, step sizes

\{ηt\}t≥1\\\{\\eta\_\{t\}\\\}\_\{t\\geq 1\}, initial AoI

A1A\_\{1\}with

A1i∈\[1,Di\]A\_\{1\}^\{i\}\\\!\\in\\\!\[1,D\_\{i\}\], optional margin

ξ∈ℝ\+N\\xi\\\!\\in\\\!\\mathbb\{R\}\_\{\+\}^\{N\}, optional uncertainty sets

\{𝒰t\}\\\{\\mathcal\{U\}\_\{t\}\\\}
0:executed actions

\(xt\)t=1T\(x\_\{t\}\)\_\{t=1\}^\{T\}, AoI trajectory

\(At\)t=1T\+1\(A\_\{t\}\)\_\{t=1\}^\{T\+1\}, queue trace

\(Qt\)t=1T\+1\(Q\_\{t\}\)\_\{t=1\}^\{T\+1\}
1:initialize:pick any

z1∈ΔNz\_\{1\}\\\!\\in\\\!\\Delta\_\{N\}\(e\.g\.,

z1=𝟏/Nz\_\{1\}\\\!=\\\!\\mathbf\{1\}/N\); set

Q1←𝟎∈ℝ\+NQ\_\{1\}\\\!\\leftarrow\\\!\\mathbf\{0\}\\in\\mathbb\{R\}\_\{\+\}^\{N\}
2:for

t=1,2,…,Tt=1,2,\\dots,Tdo

3:observecurrent AoI vector

AtA\_\{t\}and refresh matrix

Ct∈\[0,1\]N×NC\_\{t\}\\in\[0,1\]^\{N\\times N\}\(or

𝒰t∋Ct\\mathcal\{U\}\_\{t\}\\ni C\_\{t\}in the robust case\)

4:compute thresholds:

θt,i←Ati\+1−Di\+ξiAti\\theta\_\{t,i\}\\\!\\leftarrow\\\!\\dfrac\{A\_\{t\}^\{i\}\+1\-D\_\{i\}\+\\xi\_\{i\}\}\{A\_\{t\}^\{i\}\}for

i∈\[N\]i\\\!\\in\\\!\[N\]
5:build safe set:nominal

𝒦tξ←\{x∈ΔN:Ct​x≥θt\}\\mathcal\{K\}\_\{t\}^\{\\xi\}\\\!\\leftarrow\\\!\\\{x\\\!\\in\\\!\\Delta\_\{N\}:C\_\{t\}x\\\!\\geq\\\!\\theta\_\{t\}\\\}, or robust

𝒦t,robξ←\{x∈ΔN:C​x≥θt,∀C∈𝒰t\}\\mathcal\{K\}\_\{t,\\rm rob\}^\{\\xi\}\\\!\\leftarrow\\\!\\\{x\\\!\\in\\\!\\Delta\_\{N\}:Cx\\\!\\geq\\\!\\theta\_\{t\},\\,\\forall C\\\!\\in\\\!\\mathcal\{U\}\_\{t\}\\\}if

CtC\_\{t\}is partially observable

6:safety shield \(QP\):

xt←arg⁡minx∈𝒦tξ⁡12​‖x−zt‖22x\_\{t\}\\leftarrow\\arg\\min\_\{x\\in\\mathcal\{K\}\_\{t\}^\{\\xi\}\}\\tfrac\{1\}\{2\}\\\|x\-z\_\{t\}\\\|\_\{2\}^\{2\}⊳\\trianglerightEuclidean projection

7:execute:allocate the deterministic resource sharesxtx\_\{t\}and realize the modeled fluid service

8:advance AoI:

At\+1i←1\+\(1−\(Ct​xt\)i\)​AtiA\_\{t\+1\}^\{i\}\\\!\\leftarrow\\\!1\+\\bigl\(1\-\(C\_\{t\}x\_\{t\}\)\_\{i\}\\bigr\)A\_\{t\}^\{i\}for

i∈\[N\]i\\\!\\in\\\!\[N\]
9:receive feedback:convex loss

ft:ΔN→ℝf\_\{t\}:\\Delta\_\{N\}\\\!\\to\\\!\\mathbb\{R\}and subgradient

st∈∂ft​\(xt\)s\_\{t\}\\in\\partial f\_\{t\}\(x\_\{t\}\)with

‖st‖2≤G\\\|s\_\{t\}\\\|\_\{2\}\\\!\\leq\\\!G
10:a\-posteriori certificate:

Qt\+1,i←\[Qt,i\+gt,i​\(xt\)\]\+Q\_\{t\+1,i\}\\\!\\leftarrow\\\!\\bigl\[Q\_\{t,i\}\+g\_\{t,i\}\(x\_\{t\}\)\\bigr\]\_\{\+\}⊳\\trianglerightremains0by Lemma[7](https://arxiv.org/html/2607.27626#Thmlemma7)

11:gradient step \(anchored atxtx\_\{t\}\):

z~t\+1←xt−ηt​st\\widetilde\{z\}\_\{t\+1\}\\\!\\leftarrow\\\!x\_\{t\}\-\\eta\_\{t\}s\_\{t\}
12:simplex projection:

zt\+1←ΠΔN​\(z~t\+1\)z\_\{t\+1\}\\\!\\leftarrow\\\!\\Pi\_\{\\Delta\_\{N\}\}\(\\widetilde\{z\}\_\{t\+1\}\)
13:endfor

14:return

\(xt,At,Qt\)t=1T\+1\(x\_\{t\},A\_\{t\},Q\_\{t\}\)\_\{t=1\}^\{T\+1\}

### IV\-AImplementation Considerations

The dominant per\-slot cost is the safe\-set projection on line 5, a convex QP over the simplex withNNrefresh inequalities, solvable inO​\(N3\)O\(N^\{3\}\)by any active\-set or interior\-point method and amortizable by warm\-starting fromztz\_\{t\}\. The simplex projection in line 10 takesO​\(N​log⁡N\)O\(N\\log N\)via sort\-and\-threshold\. For a known horizonTT, the constant step size

η=RG​T,\\eta=\\dfrac\{R\}\{G\\sqrt\{T\}\},\(12\)withR≤2R\\leq\\sqrt\{2\}the diameter ofΔN\\Delta\_\{N\}, optimizes the static\-regret bound below, and the doubling\-free scheduleηt=R/\(G​t\)\\eta\_\{t\}=R/\(G\\sqrt\{t\}\)achieves the sameO​\(T\)O\(\\sqrt\{T\}\)order with a3/23/2overhead whenTTis unknown\. For the canonical AoI loss,GGmay be replaced by the data\-only boundGcan≤N​∑iwi​DiG\_\{\\rm can\}\\leq\\sqrt\{N\}\\sum\_\{i\}w\_\{i\}D\_\{i\}\. Anchoring the gradient step at the executedxtx\_\{t\}\(line 10\) rather than atztz\_\{t\}is essential: it aligns the OCO recursion with the subgradient observed atxtx\_\{t\}and is what allows the projection inequality to telescope; usingztz\_\{t\}instead would couple the shield correction with the gradient direction across slots and break both the regret bound and causality\. If only an uncertainty set𝒰t∋Ct\\mathcal\{U\}\_\{t\}\\ni C\_\{t\}is available \(e\.g\., a coordinatewise lower boundC¯t\\underline\{C\}\_\{t\}from channel\-state estimation\), replacing𝒦t\\mathcal\{K\}\_\{t\}in line 4 with the robust safe set

𝒦t,rob=\{x∈ΔN:C​x≥θt,∀C∈𝒰t\}\\mathcal\{K\}\_\{t,\\rm rob\}=\\\{x\\in\\Delta\_\{N\}:Cx\\geq\\theta\_\{t\},\\,\\forall C\\in\\mathcal\{U\}\_\{t\}\\\}\(13\)preserves every guarantee for any realizedCt∈𝒰tC\_\{t\}\\in\\mathcal\{U\}\_\{t\}\.

### IV\-BPer\-Step Reasoning

Lines 3–4 usethe pre\-action observationsAtA\_\{t\}andCtC\_\{t\}\(or a conservative𝒰t∋Ct\\mathcal\{U\}\_\{t\}\\ni C\_\{t\}\)to form the affine thresholdθt\\theta\_\{t\}and the polyhedral safe set𝒦t\\mathcal\{K\}\_\{t\}via Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1);no future packet outcome is used\. Line 5 hardens the proposalztz\_\{t\}, which encodes everything the algorithm has learned, into the closest feasiblext=Π𝒦t​\(zt\)x\_\{t\}=\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\(z\_\{t\}\), and Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)guaranteesAt\+1i≤DiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}without further mechanism\. Lines 6–7allocate deterministic resource shares and advance the modeled AoI state\. Lines 8–9 form the accounting layer: the convex lossftf\_\{t\}and a subgradientsts\_\{t\}become available only after the action commits,which is first\-order OCO rather than bandit feedback; the queue update is recorded but, by Lemma[7](https://arxiv.org/html/2607.27626#Thmlemma7), never leaves zero, so it serves as a runtime certificate rather than a control variable\. Lines 10–11 are the regret\-minimization step: a one\-step descent atηt​st\\eta\_\{t\}s\_\{t\}from the executed iteratextx\_\{t\}, followed by a single simplex projection\.Here “learning” means no\-regret sequential adaptation from first\-order feedback, not bandit exploration or channel\-model learning\.Anchoring the descent atxtx\_\{t\}rather than atztz\_\{t\}is what makes the squared\-distance terms in Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)telescope across slots; pulling the gradient back toztz\_\{t\}would couple the shield correction with future gradients and break theO​\(T\)O\(\\sqrt\{T\}\)rate\.

### IV\-CShield Versus Long\-Term Virtual Queue

The role of the shield can be made precise by contrasting it with the standard long\-term virtual\-queue \(LT\-VQ\) approach to constrained OCO\. LT\-VQ schedulers at every slot solvearg⁡minx⁡V​ft​\(x\)\+∑iQt,i​gt,i​\(x\)\\arg\\min\_\{x\}Vf\_\{t\}\(x\)\+\\sum\_\{i\}Q\_\{t,i\}g\_\{t,i\}\(x\)overΔN\\Delta\_\{N\}, whereV\>0V\>0is a Lyapunov weight andQtQ\_\{t\}is a queue that absorbs accumulated constraint violation\. WithV=Θ​\(T\)V=\\Theta\(\\sqrt\{T\}\)this attains bothO​\(T\)O\(\\sqrt\{T\}\)regret andO​\(T\)O\(\\sqrt\{T\}\)cumulative violation, but the queue is the only safety mechanism: at any slot in which the gradient direction conflicts with the deadline,gt,i​\(xt\)\>0g\_\{t,i\}\(x\_\{t\}\)\>0is permitted as long as the running sum∑τ\[gτ,i​\(xτ\)\]\+\\sum\_\{\\tau\}\[g\_\{\\tau,i\}\(x\_\{\\tau\}\)\]\_\{\+\}remains sublinear\. Proposition[1](https://arxiv.org/html/2607.27626#Thmproposition1)formalizes the fundamental gap: even anO​\(1\)O\(1\)cumulative\-violation budget is consistent withgt0,i​\(xt0\)\>0g\_\{t\_\{0\},i\}\(x\_\{t\_\{0\}\}\)\>0at somet0t\_\{0\}, and a single such slot is enough to trip a\(1,1\)\(1,1\)\-firm peak\-AoI constraint\.

The PSU loop reverses the roles\. The shieldΠ𝒦t\\Pi\_\{\\mathcal\{K\}\_\{t\}\}on line 5 enforcesgt,i​\(xt\)≤0g\_\{t,i\}\(x\_\{t\}\)\\leq 0in the slot itself, beforextx\_\{t\}is executed, and the queue update on line 9 is performed only as an audit trail\. Lemmas[6](https://arxiv.org/html/2607.27626#Thmlemma6)–[7](https://arxiv.org/html/2607.27626#Thmlemma7)together show that this design guaranteesQt,i=0Q\_\{t,i\}=0along the viable modeled trajectory, while the gradient step retains the sameO​\(T\)O\(\\sqrt\{T\}\)rate as unconstrained OCD onΔN\\Delta\_\{N\}\. The trade\-off between regret and safety that LT\-VQ exposes through the parameterVVis therefore avoided entirely: the regret bound depends only onRR,GG, andTT, not on any constraint\-tightness parameter, andthe safety premise is that each safe set encountered along this trajectory is non\-empty\.

## VMain Results

This section gives the complete theoretical analysis of Algorithm[1](https://arxiv.org/html/2607.27626#alg1): the AoI\-to\-affine\-safety reduction \(§[V\-A](https://arxiv.org/html/2607.27626#S5.SS1)\), the projection lemma \(§[V\-B](https://arxiv.org/html/2607.27626#S5.SS2)\), the safety invariant and main theorem \(§[V\-C](https://arxiv.org/html/2607.27626#S5.SS3)–[V\-D](https://arxiv.org/html/2607.27626#S5.SS4)\), a path\-length dynamic\-regret bound \(§[V\-E](https://arxiv.org/html/2607.27626#S5.SS5)\), a matchingΩ​\(T\)\\Omega\(\\sqrt\{T\}\)lower bound \(§[V\-F](https://arxiv.org/html/2607.27626#S5.SS6)\), margin and approximate\-projection robustness \(§[V\-G](https://arxiv.org/html/2607.27626#S5.SS7)–[V\-G](https://arxiv.org/html/2607.27626#S5.SS7)\), the link to weakly\-hard\(m,k\)\(m,k\)\-firm semantics \(§[V\-H](https://arxiv.org/html/2607.27626#S5.SS8)\), the fractional\-to\-integral interface \(§[V\-I](https://arxiv.org/html/2607.27626#S5.SS9)\), a robust safe projection under partial channel observability \(§[V\-J](https://arxiv.org/html/2607.27626#S5.SS10)\), and two competitive\-ratio statements \(§[V\-K](https://arxiv.org/html/2607.27626#S5.SS11)\)\. All proofs are full and self\-contained\.

### V\-AAoI\-to\-Affine\-Safety Reduction

###### Lemma 1\(Deadline\-to\-threshold equivalence\)\.

SupposeAti≥1A\_\{t\}^\{i\}\\geq 1\. Then for everyx∈ΔNx\\in\\Delta\_\{N\},

gt,i​\(x\)≤0⟺\(Ct​x\)i≥θt,i,g\_\{t,i\}\(x\)\\leq 0\\quad\\Longleftrightarrow\\quad\(C\_\{t\}x\)\_\{i\}\\geq\\theta\_\{t,i\},\(14\)whereθt,i=\(Ati\+1−Di\)/Ati\\theta\_\{t,i\}=\(A\_\{t\}^\{i\}\+1\-D\_\{i\}\)/A\_\{t\}^\{i\}\. Consequently, wheneverAti≥1A\_\{t\}^\{i\}\\geq 1for everyi∈\[N\]i\\in\[N\],

𝒦t=\{x∈ΔN:Ct​x≥θt\},\\mathcal\{K\}\_\{t\}=\\\{x\\in\\Delta\_\{N\}:C\_\{t\}x\\geq\\theta\_\{t\}\\\},\(15\)read coordinatewise\.

###### Proof\.

By \([2](https://arxiv.org/html/2607.27626#S3.E2)\),gt,i​\(x\)=Ati\+1−Di−Ati​\(Ct​x\)ig\_\{t,i\}\(x\)=A\_\{t\}^\{i\}\+1\-D\_\{i\}\-A\_\{t\}^\{i\}\(C\_\{t\}x\)\_\{i\}, sogt,i​\(x\)≤0⇔Ati\+1−Di≤Ati​\(Ct​x\)ig\_\{t,i\}\(x\)\\leq 0\\iff A\_\{t\}^\{i\}\+1\-D\_\{i\}\\leq A\_\{t\}^\{i\}\(C\_\{t\}x\)\_\{i\}\. SinceAti≥1\>0A\_\{t\}^\{i\}\\geq 1\>0, dividing byAtiA\_\{t\}^\{i\}preserves the inequality and givesθt,i≤\(Ct​x\)i\\theta\_\{t,i\}\\leq\(C\_\{t\}x\)\_\{i\}; each step is reversible\. Conjoining overiiand intersecting withΔN\\Delta\_\{N\}yields \([15](https://arxiv.org/html/2607.27626#S5.E15)\)\. ∎

The hypothesisAti≥1A\_\{t\}^\{i\}\\geq 1is preserved along the trajectory of Algorithm[1](https://arxiv.org/html/2607.27626#alg1)by Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)below, whose induction relies only on Assumption[1](https://arxiv.org/html/2607.27626#Thmassumption1), the dynamics \([2](https://arxiv.org/html/2607.27626#S3.E2)\), and the projection step, so \([15](https://arxiv.org/html/2607.27626#S5.E15)\) applies at every slot without circularity\.

###### Lemma 2\(Polyhedral structure of the safe set\)\.

Fix\(At,Ct\)\(A\_\{t\},C\_\{t\}\)withAti≥1A\_\{t\}^\{i\}\\geq 1for everyi∈\[N\]i\\in\[N\]\. The mapsx↦at\+1i​\(x\)x\\mapsto a\_\{t\+1\}^\{i\}\(x\),x↦gt,i​\(x\)x\\mapsto g\_\{t,i\}\(x\), andx↦ftcan​\(x\)x\\mapsto f\_\{t\}^\{\\rm can\}\(x\)are affine onℝN\\mathbb\{R\}^\{N\}\. Consequently,𝒦t\\mathcal\{K\}\_\{t\}is a closed convex polyhedron, and is non\-empty under Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3)\. Conversely, if𝒦t=∅\\mathcal\{K\}\_\{t\}=\\varnothing, then everyx∈ΔNx\\in\\Delta\_\{N\}pushes some sensor’s post\-decision AoI above its deadline, so Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3)characterizes exactly the sequences on which a zero\-violation guarantee can hold\.

###### Proof\.

By \([2](https://arxiv.org/html/2607.27626#S3.E2)\),at\+1i​\(x\)=Ati\+1−⟨ct,i,x⟩a\_\{t\+1\}^\{i\}\(x\)=A\_\{t\}^\{i\}\+1\-\\langle c\_\{t,i\},x\\ranglewithct,i=Ati​\(Ct,i​1,…,Ct,i​N\)⊤c\_\{t,i\}=A\_\{t\}^\{i\}\(C\_\{t,i1\},\\dots,C\_\{t,iN\}\)^\{\\top\}, which is the sum of a constant and a linear functional, hence affine;gt,i=at\+1i−Dig\_\{t,i\}=a\_\{t\+1\}^\{i\}\-D\_\{i\}remains affine, andftcan=∑iwi​Ati​\(1−\(Ct​x\)i\)f\_\{t\}^\{\\rm can\}=\\sum\_\{i\}w\_\{i\}A\_\{t\}^\{i\}\\bigl\(1\-\(C\_\{t\}x\)\_\{i\}\\bigr\)is a non\-negative weighted sum of affine functions and is thus affine\. By Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1),𝒦t=ΔN∩⋂i=1N\{x:\(Ct​x\)i≥θt,i\}\\mathcal\{K\}\_\{t\}=\\Delta\_\{N\}\\cap\\bigcap\_\{i=1\}^\{N\}\\\{x:\(C\_\{t\}x\)\_\{i\}\\geq\\theta\_\{t,i\}\\\}\. The simplexΔN\\Delta\_\{N\}is the intersection of the closed half\-spaces\{xj≥0\}\\\{x\_\{j\}\\geq 0\\\}with the closed affine hyperplane\{𝟏⊤​x=1\}\\\{\\mathbf\{1\}^\{\\top\}x=1\\\}, and each\{x:\(Ct​x\)i≥θt,i\}\\\{x:\(C\_\{t\}x\)\_\{i\}\\geq\\theta\_\{t,i\}\\\}is a closed half\-space, so𝒦t\\mathcal\{K\}\_\{t\}is a finite intersection of closed half\-spaces and an affine hyperplane and is therefore a closed convex polyhedron\. Non\-emptiness follows from Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3); the converse is immediate from Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)\. ∎

###### Lemma 3\(Common observations only enlarge the safe set\)\.

FixAtA\_\{t\}andDDand write𝒦t​\(C\)=\{x∈ΔN:C​x≥θt\}\\mathcal\{K\}\_\{t\}\(C\)=\\\{x\\in\\Delta\_\{N\}:Cx\\geq\\theta\_\{t\}\\\}\.\(i\)IfCt′≥CtC^\{\\prime\}\_\{t\}\\geq C\_\{t\}coordinatewise, then𝒦t​\(Ct\)⊆𝒦t​\(Ct′\)\\mathcal\{K\}\_\{t\}\(C\_\{t\}\)\\subseteq\\mathcal\{K\}\_\{t\}\(C^\{\\prime\}\_\{t\}\), and the inclusion is strict whenever some row ofCt′−CtC^\{\\prime\}\_\{t\}\-C\_\{t\}is non\-zero on the relative interior ofΔN∩\{x:\(Ct​x\)i=θt,i\}\\Delta\_\{N\}\\cap\\\{x:\(C\_\{t\}x\)\_\{i\}=\\theta\_\{t,i\}\\\}\.\(ii\)Whenever it is non\-empty,𝒦t\\mathcal\{K\}\_\{t\}is compact and equal to the convex hull of finitely many vertices, with diameter bounded bydiam​\(ΔN\)=2\\mathrm\{diam\}\(\\Delta\_\{N\}\)=\\sqrt\{2\}\.

###### Proof\.

\(i\) Take anyx∈𝒦t​\(Ct\)x\\in\\mathcal\{K\}\_\{t\}\(C\_\{t\}\)\. By Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1),Ct​x≥θtC\_\{t\}x\\geq\\theta\_\{t\}\. SinceCt′−Ct≥0C^\{\\prime\}\_\{t\}\-C\_\{t\}\\geq 0entry\-wise andx≥0x\\geq 0,\(Ct′​x\)i−\(Ct​x\)i=∑j\(Ct,i​j′−Ct,i​j\)​xj≥0\(C^\{\\prime\}\_\{t\}x\)\_\{i\}\-\(C\_\{t\}x\)\_\{i\}=\\sum\_\{j\}\(C^\{\\prime\}\_\{t,ij\}\-C\_\{t,ij\}\)x\_\{j\}\\geq 0for everyii\. HenceCt′​x≥Ct​x≥θtC^\{\\prime\}\_\{t\}x\\geq C\_\{t\}x\\geq\\theta\_\{t\}, and Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)givesx∈𝒦t​\(Ct′\)x\\in\\mathcal\{K\}\_\{t\}\(C^\{\\prime\}\_\{t\}\)\. The strictness claim follows because activating a row ofCt′−CtC^\{\\prime\}\_\{t\}\-C\_\{t\}relaxes a binding face of𝒦t​\(Ct\)\\mathcal\{K\}\_\{t\}\(C\_\{t\}\)into the interior of𝒦t​\(Ct′\)\\mathcal\{K\}\_\{t\}\(C^\{\\prime\}\_\{t\}\)\. \(ii\) Compactness is inherited fromΔN\\Delta\_\{N\}, and the Minkowski–Weyl theorem represents any non\-empty bounded polyhedron as the convex hull of its finitely many extreme points\. The diameter bound is inherited fromΔN\\Delta\_\{N\}\. ∎

Lemma[3](https://arxiv.org/html/2607.27626#Thmlemma3)is the structural reason the robust safe set in §[V\-J](https://arxiv.org/html/2607.27626#S5.SS10)retains feasibility under partial channel observability: replacingCtC\_\{t\}by any coordinatewise lower boundC¯t≤Ct\\underline\{C\}\_\{t\}\\leq C\_\{t\}yields a tighter polyhedron𝒦t​\(C¯t\)⊆𝒦t​\(Ct\)\\mathcal\{K\}\_\{t\}\(\\underline\{C\}\_\{t\}\)\\subseteq\\mathcal\{K\}\_\{t\}\(C\_\{t\}\), so projecting onto𝒦t​\(C¯t\)\\mathcal\{K\}\_\{t\}\(\\underline\{C\}\_\{t\}\)is a fortiori safe under the realized channel\. In conjunction with Lemma[2](https://arxiv.org/html/2607.27626#Thmlemma2), it also implies that𝒦t\\mathcal\{K\}\_\{t\}admits a finite\-vertex representation that an active\-set or simplex\-based projection routine can exploit, and that the projection in line 4 of Algorithm[1](https://arxiv.org/html/2607.27626#alg1)reduces to a quadratic program with at most2​N\+12N\+1linear constraints\.

### V\-BProjection Geometry

###### Lemma 4\(Existence, uniqueness, and Pythagorean inequality\)\.

Let𝒞⊂ℝN\\mathcal\{C\}\\subset\\mathbb\{R\}^\{N\}be non\-empty, closed, and convex\. For everyy∈ℝNy\\in\\mathbb\{R\}^\{N\}the projectionp=Π𝒞​\(y\)=arg⁡minx∈𝒞⁡12​‖x−y‖22p=\\Pi\_\{\\mathcal\{C\}\}\(y\)=\\arg\\min\_\{x\\in\\mathcal\{C\}\}\\frac\{1\}\{2\}\\\|x\-y\\\|\_\{2\}^\{2\}exists and is unique, and for everyu∈𝒞u\\in\\mathcal\{C\},

⟨y−p,u−p⟩\\displaystyle\\langle y\-p,\\,u\-p\\rangle≤0,\\displaystyle\\leq 0,\(16\)‖p−u‖22\\displaystyle\\\|p\-u\\\|\_\{2\}^\{2\}≤‖y−u‖22−‖y−p‖22≤‖y−u‖22\.\\displaystyle\\leq\\\|y\-u\\\|\_\{2\}^\{2\}\-\\\|y\-p\\\|\_\{2\}^\{2\}\\leq\\\|y\-u\\\|\_\{2\}^\{2\}\.\(17\)

###### Proof\.

Existence and uniqueness follow by Weierstrass on the compact sublevel set𝒞0=\{x∈𝒞:12​‖x−y‖22≤12​‖x0−y‖22\}\\mathcal\{C\}\_\{0\}=\\\{x\\in\\mathcal\{C\}:\\frac\{1\}\{2\}\\\|x\-y\\\|\_\{2\}^\{2\}\\leq\\frac\{1\}\{2\}\\\|x\_\{0\}\-y\\\|\_\{2\}^\{2\}\\\}withx0∈𝒞x\_\{0\}\\in\\mathcal\{C\}, together with the parallelogram law: ifp≠qp\\neq qboth minimized12∥⋅−y∥22\\frac\{1\}\{2\}\\\|\\cdot\-y\\\|\_\{2\}^\{2\}, thenm=\(p\+q\)/2∈𝒞m=\(p\+q\)/2\\in\\mathcal\{C\}would attain a strictly smaller value\. For anyu∈𝒞u\\in\\mathcal\{C\}andα∈\[0,1\]\\alpha\\in\[0,1\],p\+α​\(u−p\)∈𝒞p\+\\alpha\(u\-p\)\\in\\mathcal\{C\}, and minimality ofα=0\\alpha=0in12​‖p\+α​\(u−p\)−y‖22\\frac\{1\}\{2\}\\\|p\+\\alpha\(u\-p\)\-y\\\|\_\{2\}^\{2\}gives \([16](https://arxiv.org/html/2607.27626#S5.E16)\)\. Decomposingy−u=\(y−p\)\+\(p−u\)y\-u=\(y\-p\)\+\(p\-u\)and using \([16](https://arxiv.org/html/2607.27626#S5.E16)\) yields \([17](https://arxiv.org/html/2607.27626#S5.E17)\)\. ∎

### V\-CSafety Invariants and Zero\-Violation Certificate

###### Lemma 5\(Closed\-form Lipschitz constant of the canonical loss\)\.

IfAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}for allt,it,ialong the trajectory,ftcanf\_\{t\}^\{\\rm can\}isGcanG\_\{\\rm can\}\-Lipschitz onΔN\\Delta\_\{N\}with

Gcan=supt‖Ct⊤​\(At⊙w\)‖2≤N​∑i=1Nwi​Di,G\_\{\\rm can\}=\\sup\_\{t\}\\\|C\_\{t\}^\{\\top\}\(A\_\{t\}\\odot w\)\\\|\_\{2\}\\leq\\sqrt\{N\}\\sum\_\{i=1\}^\{N\}w\_\{i\}D\_\{i\},\(18\)and, withDmax=maxi⁡DiD\_\{\\max\}=\\max\_\{i\}D\_\{i\},W=∑iwiW=\\sum\_\{i\}w\_\{i\},

Gcan≤min⁡\{N​Dmax​‖w‖2,N​Dmax​W\}\.G\_\{\\rm can\}\\leq\\min\\\{ND\_\{\\max\}\\\|w\\\|\_\{2\},\\;\\sqrt\{N\}\\,D\_\{\\max\}W\\\}\.\(19\)

###### Proof\.

∇ftcan=−Ct⊤​\(At⊙w\)\\nabla f\_\{t\}^\{\\rm can\}=\-C\_\{t\}^\{\\top\}\(A\_\{t\}\\odot w\)is constant inxx, so by Cauchy–Schwarzftcanf\_\{t\}^\{\\rm can\}is Lipschitz with constantsupt‖Ct⊤​\(At⊙w\)‖2\\sup\_\{t\}\\\|C\_\{t\}^\{\\top\}\(A\_\{t\}\\odot w\)\\\|\_\{2\}\. Each entry∑iCt,i​j​Ati​wi\\sum\_\{i\}C\_\{t,ij\}A\_\{t\}^\{i\}w\_\{i\}is in\[0,∑iwi​Di\]\[0,\\sum\_\{i\}w\_\{i\}D\_\{i\}\]sinceCt,i​j∈\[0,1\]C\_\{t,ij\}\\in\[0,1\]andAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}, giving \([18](https://arxiv.org/html/2607.27626#S5.E18)\)\. For \([19](https://arxiv.org/html/2607.27626#S5.E19)\),‖Ct‖F≤N\\\|C\_\{t\}\\\|\_\{F\}\\leq Nand‖At⊙w‖2≤Dmax​‖w‖2\\\|A\_\{t\}\\odot w\\\|\_\{2\}\\leq D\_\{\\max\}\\\|w\\\|\_\{2\}yield the first bound, and∑iwi​Di≤Dmax​W\\sum\_\{i\}w\_\{i\}D\_\{i\}\\leq D\_\{\\max\}Wyields the second\. ∎

###### Lemma 6\(Stage\-wise safety and well\-posedness\)\.

Under Assumptions[1](https://arxiv.org/html/2607.27626#Thmassumption1)–[3](https://arxiv.org/html/2607.27626#Thmassumption3), Algorithm[1](https://arxiv.org/html/2607.27626#alg1)produces a uniquext=Π𝒦t​\(zt\)∈𝒦tx\_\{t\}=\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\(z\_\{t\}\)\\in\\mathcal\{K\}\_\{t\}at every slot, and

1≤Ati≤Di,t=1,…,T\+1,i∈\[N\]\.1\\leq A\_\{t\}^\{i\}\\leq D\_\{i\},\\qquad t=1,\\dots,T\+1,\\ i\\in\[N\]\.\(20\)

###### Proof\.

We induct ontt\.

*Base case*\(t=1t=1\)\. Assumption[1](https://arxiv.org/html/2607.27626#Thmassumption1)gives1≤A1i≤Di1\\leq A\_\{1\}^\{i\}\\leq D\_\{i\}for everyi∈\[N\]i\\in\[N\], so \([20](https://arxiv.org/html/2607.27626#S5.E20)\) holds att=1t=1\.

*Inductive step\.*Suppose \([20](https://arxiv.org/html/2607.27626#S5.E20)\) holds at slottt\. ThenAti≥1A\_\{t\}^\{i\}\\geq 1for allii, which activates the affine description𝒦t=\{x∈ΔN:Ct​x≥θt\}\\mathcal\{K\}\_\{t\}=\\\{x\\in\\Delta\_\{N\}:C\_\{t\}x\\geq\\theta\_\{t\}\\\}in Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)\. By Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3),𝒦t≠∅\\mathcal\{K\}\_\{t\}\\neq\\varnothing, and by Lemma[2](https://arxiv.org/html/2607.27626#Thmlemma2)the set𝒦t\\mathcal\{K\}\_\{t\}is closed and convex\. Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)therefore guarantees the existence of the unique projectionxt=Π𝒦t​\(zt\)∈𝒦tx\_\{t\}=\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\(z\_\{t\}\)\\in\\mathcal\{K\}\_\{t\}, so the algorithm is well\-posed\. Sincext∈𝒦tx\_\{t\}\\in\\mathcal\{K\}\_\{t\}, Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)givesgt,i​\(xt\)≤0g\_\{t,i\}\(x\_\{t\}\)\\leq 0for everyii, equivalentlyAt\+1i=1\+\(1−\(Ct​xt\)i\)​Ati≤DiA\_\{t\+1\}^\{i\}=1\+\(1\-\(C\_\{t\}x\_\{t\}\)\_\{i\}\)A\_\{t\}^\{i\}\\leq D\_\{i\}by \([2](https://arxiv.org/html/2607.27626#S3.E2)\)\. For the lower bound,0≤\(Ct​xt\)i≤10\\leq\(C\_\{t\}x\_\{t\}\)\_\{i\}\\leq 1becauseCt∈\[0,1\]N×NC\_\{t\}\\in\[0,1\]^\{N\\times N\}andxt∈ΔNx\_\{t\}\\in\\Delta\_\{N\}, andAti≥1A\_\{t\}^\{i\}\\geq 1by the inductive hypothesis, soAt\+1i≥1\+0⋅Ati=1A\_\{t\+1\}^\{i\}\\geq 1\+0\\cdot A\_\{t\}^\{i\}=1\. Hence \([20](https://arxiv.org/html/2607.27626#S5.E20)\) holds att\+1t\+1, completing the induction\. ∎

###### Lemma 7\(Virtual queue stays at zero\)\.

WithQ1=𝟎Q\_\{1\}=\\mathbf\{0\},Qt,i=0Q\_\{t,i\}=0and∑τ=1t\[gτ,i​\(xτ\)\]\+=0\\sum\_\{\\tau=1\}^\{t\}\[g\_\{\\tau,i\}\(x\_\{\\tau\}\)\]\_\{\+\}=0for allt∈\[T\+1\]t\\in\[T\+1\],i∈\[N\]i\\in\[N\]\.

###### Proof\.

We induct ontt\. The base caseQ1,i=0Q\_\{1,i\}=0holds by initialization\. SupposeQt,i=0Q\_\{t,i\}=0for somet∈\[T\]t\\in\[T\]\. Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)givesxt∈𝒦tx\_\{t\}\\in\\mathcal\{K\}\_\{t\}, sogt,i​\(xt\)≤0g\_\{t,i\}\(x\_\{t\}\)\\leq 0by Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)\. The line\-9 update of Algorithm[1](https://arxiv.org/html/2607.27626#alg1)then yieldsQt\+1,i=\[Qt,i\+gt,i​\(xt\)\]\+=\[0\+non\-positive\]\+=0Q\_\{t\+1,i\}=\[Q\_\{t,i\}\+g\_\{t,i\}\(x\_\{t\}\)\]\_\{\+\}=\[0\+\\text\{non\-positive\}\]\_\{\+\}=0, completing the induction\. The cumulative\-violation identity follows from\[gτ,i​\(xτ\)\]\+=0\[g\_\{\\tau,i\}\(x\_\{\\tau\}\)\]\_\{\+\}=0at everyτ\\tau\. ∎

### V\-DOne\-Step OCO Inequality and the Main Theorem

###### Lemma 8\(One\-step OCO inequality after the safety shield\)\.

Under Assumptions[1](https://arxiv.org/html/2607.27626#Thmassumption1)–[3](https://arxiv.org/html/2607.27626#Thmassumption3), for anyu∈𝒦tu\\in\\mathcal\{K\}\_\{t\},

ft​\(xt\)−ft​\(u\)≤‖zt−u‖22−‖zt\+1−u‖222​ηt\+ηt2​‖st‖22\.f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\)\\leq\\dfrac\{\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\\\|\_\{2\}^\{2\}\}\{2\\eta\_\{t\}\}\+\\dfrac\{\\eta\_\{t\}\}\{2\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.\(21\)

###### Proof\.

Convexity givesft​\(xt\)−ft​\(u\)≤⟨st,xt−u⟩f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\)\\leq\\langle s\_\{t\},x\_\{t\}\-u\\rangle\. Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)on𝒞=𝒦t\\mathcal\{C\}=\\mathcal\{K\}\_\{t\}gives‖xt−u‖22≤‖zt−u‖22\\\|x\_\{t\}\-u\\\|\_\{2\}^\{2\}\\leq\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}, and on𝒞=ΔN\\mathcal\{C\}=\\Delta\_\{N\}withzt\+1=ΠΔN​\(xt−ηt​st\)z\_\{t\+1\}=\\Pi\_\{\\Delta\_\{N\}\}\(x\_\{t\}\-\\eta\_\{t\}s\_\{t\}\)gives‖zt\+1−u‖22≤‖xt−ηt​st−u‖22\\\|z\_\{t\+1\}\-u\\\|\_\{2\}^\{2\}\\leq\\\|x\_\{t\}\-\\eta\_\{t\}s\_\{t\}\-u\\\|\_\{2\}^\{2\}\. Expanding,

‖zt\+1−u‖22≤‖zt−u‖22−2​ηt​⟨st,xt−u⟩\+ηt2​‖st‖22\.\\\|z\_\{t\+1\}\-u\\\|\_\{2\}^\{2\}\\leq\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}\-2\\eta\_\{t\}\\langle s\_\{t\},x\_\{t\}\-u\\rangle\+\\eta\_\{t\}^\{2\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.Solving for the inner product, dividing by2​ηt2\\eta\_\{t\}, and combining yields \([21](https://arxiv.org/html/2607.27626#S5.E21)\)\. ∎

###### Theorem 1\(OCO\-PAoI\-Hard: hard safety, zero violation,O​\(T\)O\(\\sqrt\{T\}\)regret\)\.

Under Assumptions[1](https://arxiv.org/html/2607.27626#Thmassumption1)–[3](https://arxiv.org/html/2607.27626#Thmassumption3)and‖st‖2≤G\\\|s\_\{t\}\\\|\_\{2\}\\leq G, with non\-increasingη1≥⋯≥ηT\>0\\eta\_\{1\}\\geq\\cdots\\geq\\eta\_\{T\}\>0, for every adversarial sequence\(Ct,ft\)t=1T\(C\_\{t\},f\_\{t\}\)\_\{t=1\}^\{T\}Algorithm[1](https://arxiv.org/html/2607.27626#alg1)pathwise satisfiesAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}for allt,it,iandQt,i=0Q\_\{t,i\}=0,∑τ=1t\[gτ,i​\(xτ\)\]\+=0\\sum\_\{\\tau=1\}^\{t\}\[g\_\{\\tau,i\}\(x\_\{\\tau\}\)\]\_\{\+\}=0\. If𝒦1:T=⋂t=1T𝒦t≠∅\\mathcal\{K\}\_\{1:T\}=\\bigcap\_\{t=1\}^\{T\}\\mathcal\{K\}\_\{t\}\\neq\\varnothing, then for everyu∈𝒦1:Tu\\in\\mathcal\{K\}\_\{1:T\},

RegT⁡\(u\)≤R22​ηT\+12​∑t=1Tηt​‖st‖22\.\\operatorname\{Reg\}\_\{T\}\(u\)\\leq\\dfrac\{R^\{2\}\}\{2\\eta\_\{T\}\}\+\\dfrac\{1\}\{2\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.\(22\)With known horizonTTandη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\),

RegT⁡\(u\)≤R​G​T≤2​G​T\.\\operatorname\{Reg\}\_\{T\}\(u\)\\leq RG\\sqrt\{T\}\\leq\\sqrt\{2\}\\,G\\sqrt\{T\}\.\(23\)With unknown horizon andηt=R/\(G​t\)\\eta\_\{t\}=R/\(G\\sqrt\{t\}\),

RegT⁡\(u\)≤32​R​G​T\.\\operatorname\{Reg\}\_\{T\}\(u\)\\leq\\tfrac\{3\}\{2\}\\,RG\\sqrt\{T\}\.\(24\)

###### Proof\.

The hard\-safety statement is Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)and the zero\-violation certificate is Lemma[7](https://arxiv.org/html/2607.27626#Thmlemma7)\. Fix anyu∈𝒦1:Tu\\in\\mathcal\{K\}\_\{1:T\}, sou∈𝒦tu\\in\\mathcal\{K\}\_\{t\}for everyttand Lemma[8](https://arxiv.org/html/2607.27626#Thmlemma8)gives, withat:=‖zt−u‖22∈\[0,R2\]a\_\{t\}:=\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}\\in\[0,R^\{2\}\],

ft​\(xt\)−ft​\(u\)≤at−at\+12​ηt\+ηt2​‖st‖22\.f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\)\\leq\\dfrac\{a\_\{t\}\-a\_\{t\+1\}\}\{2\\eta\_\{t\}\}\+\\dfrac\{\\eta\_\{t\}\}\{2\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.\(25\)Summing overt∈\[T\]t\\in\[T\],

RegT⁡\(u\)≤∑t=1Tat−at\+12​ηt\+12​∑t=1Tηt​‖st‖22\.\\operatorname\{Reg\}\_\{T\}\(u\)\\leq\\sum\_\{t=1\}^\{T\}\\dfrac\{a\_\{t\}\-a\_\{t\+1\}\}\{2\\eta\_\{t\}\}\+\\dfrac\{1\}\{2\}\\sum\_\{t=1\}^\{T\}\\eta\_\{t\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.\(26\)Apply Abel summation to the first term,

∑t=1Tat−at\+12​ηt=a12​η1−aT\+12​ηT\+∑t=2Tat​\(12​ηt−12​ηt−1\),\\sum\_\{t=1\}^\{T\}\\dfrac\{a\_\{t\}\-a\_\{t\+1\}\}\{2\\eta\_\{t\}\}=\\dfrac\{a\_\{1\}\}\{2\\eta\_\{1\}\}\-\\dfrac\{a\_\{T\+1\}\}\{2\\eta\_\{T\}\}\+\\sum\_\{t=2\}^\{T\}a\_\{t\}\\Big\(\\dfrac\{1\}\{2\\eta\_\{t\}\}\-\\dfrac\{1\}\{2\\eta\_\{t\-1\}\}\\Big\),\(27\)where the brackets are nonnegative sinceηt\\eta\_\{t\}is non\-increasing\. Usingat≤R2a\_\{t\}\\leq R^\{2\}and−aT\+1/\(2​ηT\)≤0\-a\_\{T\+1\}/\(2\\eta\_\{T\}\)\\leq 0,

∑t=1Tat−at\+12​ηt≤R22​ηT,\\sum\_\{t=1\}^\{T\}\\dfrac\{a\_\{t\}\-a\_\{t\+1\}\}\{2\\eta\_\{t\}\}\\leq\\dfrac\{R^\{2\}\}\{2\\eta\_\{T\}\},\(28\)which combined with \([26](https://arxiv.org/html/2607.27626#S5.E26)\) yields \([22](https://arxiv.org/html/2607.27626#S5.E22)\)\. Withη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\), the right\-hand side of \([22](https://arxiv.org/html/2607.27626#S5.E22)\) becomesR​G​TRG\\sqrt\{T\}, giving \([23](https://arxiv.org/html/2607.27626#S5.E23)\); withηt=R/\(G​t\)\\eta\_\{t\}=R/\(G\\sqrt\{t\}\)the second term isR​G2​∑t=1Tt−1/2≤R​G​T\\frac\{RG\}\{2\}\\sum\_\{t=1\}^\{T\}t^\{\-1/2\}\\leq RG\\sqrt\{T\}via∑t−1/2≤2​T\\sum t^\{\-1/2\}\\leq 2\\sqrt\{T\}, totaling \([24](https://arxiv.org/html/2607.27626#S5.E24)\)\. ∎

Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)is trajectory\-wise for deterministic fluid service and slotwise in conditional expected AoI whenCtC\_\{t\}contains success probabilities; the latter is not a Bernoulli packet sample\-path claim\.The zero\-violation certificateQt,i=0Q\_\{t,i\}=0needs no knowledge of𝒦1:T\\mathcal\{K\}\_\{1:T\}, and the regret bound matches unconstrained OCO up toR/ηR/\\eta\. The known\-horizon constant2​G​T\\sqrt\{2\}\\,G\\sqrt\{T\}is independent ofNN; the anytime schedule pays only a3/23/2factor and is used in experiments\.

### V\-EDynamic Regret without a Static Comparator

When𝒦1:T=∅\\mathcal\{K\}\_\{1:T\}=\\varnothing, no fixed safe comparator exists\. Algorithm[1](https://arxiv.org/html/2607.27626#alg1)still attains a path\-length dynamic\-regret bound for any safe comparator sequence\.

###### Theorem 2\(Path\-length dynamic regret\)\.

Under Assumptions[1](https://arxiv.org/html/2607.27626#Thmassumption1)–[3](https://arxiv.org/html/2607.27626#Thmassumption3)and‖st‖2≤G\\\|s\_\{t\}\\\|\_\{2\}\\leq G, with constant step sizeη\>0\\eta\>0, for anyut∈𝒦tu\_\{t\}\\in\\mathcal\{K\}\_\{t\},

DRegT⁡\(u1:T\)≤R2\+2​R​PT​\(u1:T\)2​η\+η​G2​T2\.\\operatorname\{DReg\}\_\{T\}\(u\_\{1:T\}\)\\leq\\dfrac\{R^\{2\}\+2RP\_\{T\}\(u\_\{1:T\}\)\}\{2\\eta\}\+\\dfrac\{\\eta G^\{2\}T\}\{2\}\.\(29\)Withη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\),

DRegT⁡\(u1:T\)≤R​G​T\+G​T​PT​\(u1:T\)\.\\operatorname\{DReg\}\_\{T\}\(u\_\{1:T\}\)\\leq RG\\sqrt\{T\}\+G\\sqrt\{T\}\\,P\_\{T\}\(u\_\{1:T\}\)\.\(30\)

###### Proof\.

For eachtt,ut∈𝒦tu\_\{t\}\\in\\mathcal\{K\}\_\{t\}, so Lemma[8](https://arxiv.org/html/2607.27626#Thmlemma8)gives

ft​\(xt\)−ft​\(ut\)≤‖zt−ut‖22−‖zt\+1−ut‖222​η\+η2​‖st‖22\.f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\_\{t\}\)\\leq\\dfrac\{\\\|z\_\{t\}\-u\_\{t\}\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}^\{2\}\}\{2\\eta\}\+\\dfrac\{\\eta\}\{2\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\.Summing overt∈\[T\]t\\in\[T\],

DRegT⁡\(u1:T\)≤S2​η\+η2​∑t=1T‖st‖22,\\operatorname\{DReg\}\_\{T\}\(u\_\{1:T\}\)\\leq\\dfrac\{S\}\{2\\eta\}\+\\dfrac\{\\eta\}\{2\}\\sum\_\{t=1\}^\{T\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\},\(31\)withS=∑t=1T\(‖zt−ut‖22−‖zt\+1−ut‖22\)S=\\sum\_\{t=1\}^\{T\}\\bigl\(\\\|z\_\{t\}\-u\_\{t\}\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}^\{2\}\\bigr\)\. Inserting telescoping terms in‖zt\+1−ut\+1‖22\\\|z\_\{t\+1\}\-u\_\{t\+1\}\\\|\_\{2\}^\{2\},

S\\displaystyle S=‖z1−u1‖22−‖zT\+1−uT‖22\\displaystyle=\\\|z\_\{1\}\-u\_\{1\}\\\|\_\{2\}^\{2\}\-\\\|z\_\{T\+1\}\-u\_\{T\}\\\|\_\{2\}^\{2\}\+∑t=1T−1\(‖zt\+1−ut\+1‖22−‖zt\+1−ut‖22\)\.\\displaystyle\\quad\+\\sum\_\{t=1\}^\{T\-1\}\\bigl\(\\\|z\_\{t\+1\}\-u\_\{t\+1\}\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}^\{2\}\\bigr\)\.\(32\)The first two terms contribute at mostR2R^\{2\}sincezt,ut∈ΔNz\_\{t\},u\_\{t\}\\in\\Delta\_\{N\}\. For each summand in the third term, the identity‖a−b‖22−‖a−c‖22=⟨c−b,2​a−b−c⟩\\\|a\-b\\\|\_\{2\}^\{2\}\-\\\|a\-c\\\|\_\{2\}^\{2\}=\\langle c\-b,2a\-b\-c\\ranglewitha=zt\+1a=z\_\{t\+1\},b=ut\+1b=u\_\{t\+1\},c=utc=u\_\{t\}, and Cauchy–Schwarz, give

‖zt\+1−ut\+1‖22−‖zt\+1−ut‖22\\displaystyle\\\|z\_\{t\+1\}\-u\_\{t\+1\}\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}^\{2\}≤‖ut−ut\+1‖2⋅‖2​zt\+1−ut\+1−ut‖2,\\displaystyle\\quad\\leq\\\|u\_\{t\}\-u\_\{t\+1\}\\\|\_\{2\}\\cdot\\\|2z\_\{t\+1\}\-u\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\},\(33\)and the triangle inequality bounds the second factor by2​R2R\. Therefore

S≤R2\+2​R​∑t=1T−1‖ut\+1−ut‖2=R2\+2​R​PT​\(u1:T\)\.S\\leq R^\{2\}\+2R\\sum\_\{t=1\}^\{T\-1\}\\\|u\_\{t\+1\}\-u\_\{t\}\\\|\_\{2\}=R^\{2\}\+2RP\_\{T\}\(u\_\{1:T\}\)\.\(34\)Combining \([34](https://arxiv.org/html/2607.27626#S5.E34)\) with \([31](https://arxiv.org/html/2607.27626#S5.E31)\) and∑t‖st‖22≤G2​T\\sum\_\{t\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\\leq G^\{2\}Tyields \([29](https://arxiv.org/html/2607.27626#S5.E29)\), and substitutingη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\)gives \([30](https://arxiv.org/html/2607.27626#S5.E30)\)\. ∎

The path\-length termG​T​PTG\\sqrt\{T\}\\,P\_\{T\}in \([30](https://arxiv.org/html/2607.27626#S5.E30)\) is unavoidable in adversarial OCO and degenerates to the static bound whenu1:Tu\_\{1:T\}is constant\. Theorem[2](https://arxiv.org/html/2607.27626#Thmtheorem2)therefore says the algorithm tracks any drifting safe target with regret that scales linearly in how much the target moves, while the safety conclusions of Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)are unaffected: even when𝒦1:T=∅\\mathcal\{K\}\_\{1:T\}=\\varnothingand a static comparator does not exist, every realizedxtx\_\{t\}stays in𝒦t\\mathcal\{K\}\_\{t\}and meets every per\-slot peak\-AoI deadline\.

### V\-FMatching Minimax Lower Bound

###### Theorem 3\(Ω​\(T\)\\Omega\(\\sqrt\{T\}\)minimax lower bound\)\.

There exist instances of OCO\-PAoI\-Hard, withN=2N=2,Di≥T\+2D\_\{i\}\\geq T\+2\(so𝒦t=ΔN\\mathcal\{K\}\_\{t\}=\\Delta\_\{N\}for alltt\), and convex losses satisfying Assumption[2](https://arxiv.org/html/2607.27626#Thmassumption2), on which any \(possibly randomized\) online algorithm incurs expected static regretΩ​\(T\)\\Omega\(\\sqrt\{T\}\)\.

###### Proof\.

SetN=2N=2,Di≥T\+2D\_\{i\}\\geq T\+2, andA1i=1A\_\{1\}^\{i\}=1\. Thenθt,i≤0\\theta\_\{t,i\}\\leq 0and𝒦t=Δ2\\mathcal\{K\}\_\{t\}=\\Delta\_\{2\}for everyt∈\[T\]t\\in\[T\], so the safety constraint is inactive and the problem reduces to standard OCO overΔ2\\Delta\_\{2\}with bounded subgradients\. Letσt∈\{−1,\+1\}\\sigma\_\{t\}\\in\\\{\-1,\+1\\\}be i\.i\.d\. Rademacher random variables, and consider the convex losses

ft​\(x\)=σt​x1\.f\_\{t\}\(x\)=\\sigma\_\{t\}x\_\{1\}\.\(35\)Each∇ft=σt​e1\\nabla f\_\{t\}=\\sigma\_\{t\}e\_\{1\}has norm11, so Assumption[2](https://arxiv.org/html/2607.27626#Thmassumption2)holds withG=1G=1\. For any deterministic algorithm,xtx\_\{t\}is a function ofσ1,…,σt−1\\sigma\_\{1\},\\dots,\\sigma\_\{t\-1\}and is therefore independent ofσt\\sigma\_\{t\}, so

𝔼​\[σt​xt,1\]=𝔼​\[xt,1\]​𝔼​\[σt\]=0,𝔼​\[∑t=1Tft​\(xt\)\]=0\.\\mathbb\{E\}\[\\sigma\_\{t\}x\_\{t,1\}\]=\\mathbb\{E\}\[x\_\{t,1\}\]\\,\\mathbb\{E\}\[\\sigma\_\{t\}\]=0,\\quad\\mathbb\{E\}\\Big\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\\Big\]=0\.\(36\)SetST=∑t=1TσtS\_\{T\}=\\sum\_\{t=1\}^\{T\}\\sigma\_\{t\}\. The static comparator’s loss is∑t=1Tft​\(u\)=u1​ST\\sum\_\{t=1\}^\{T\}f\_\{t\}\(u\)=u\_\{1\}S\_\{T\}, and minimizing overu∈Δ2u\\in\\Delta\_\{2\}gives

minu∈Δ2​∑t=1Tft​\(u\)=min⁡\{0,ST\}\.\\min\_\{u\\in\\Delta\_\{2\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(u\)=\\min\\\{0,S\_\{T\}\\\}\.\(37\)Combining \([36](https://arxiv.org/html/2607.27626#S5.E36)\)–\([37](https://arxiv.org/html/2607.27626#S5.E37)\) and using the symmetry ofSTS\_\{T\},

𝔼​\[RegT\]=−𝔼​\[min⁡\{0,ST\}\]=12​𝔼​\|ST\|\.\\mathbb\{E\}\[\\operatorname\{Reg\}\_\{T\}\]=\-\\mathbb\{E\}\[\\min\\\{0,S\_\{T\}\\\}\]=\\tfrac\{1\}\{2\}\\mathbb\{E\}\|S\_\{T\}\|\.\(38\)Independence and𝔼​\[σt\]=0\\mathbb\{E\}\[\\sigma\_\{t\}\]=0,𝔼​\[σt2\]=1\\mathbb\{E\}\[\\sigma\_\{t\}^\{2\}\]=1give

𝔼​\[ST2\]=∑t=1T𝔼​\[σt2\]\+∑t≠s𝔼​\[σt\]​𝔼​\[σs\]=T\.\\mathbb\{E\}\[S\_\{T\}^\{2\}\]=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\sigma\_\{t\}^\{2\}\]\+\\sum\_\{t\\neq s\}\\mathbb\{E\}\[\\sigma\_\{t\}\]\\mathbb\{E\}\[\\sigma\_\{s\}\]=T\.\(39\)For the fourth moment,𝔼​\[σt1​σt2​σt3​σt4\]≠0\\mathbb\{E\}\[\\sigma\_\{t\_\{1\}\}\\sigma\_\{t\_\{2\}\}\\sigma\_\{t\_\{3\}\}\\sigma\_\{t\_\{4\}\}\]\\neq 0only if every index appears an even number of times: all four indices equal contributeTTterms, and two distinct pairs contribute3​T​\(T−1\)3T\(T\-1\)ordered quadruples each with expectation11, hence

𝔼​\[ST4\]=T\+3​T​\(T−1\)=3​T2−2​T≤3​T2\.\\mathbb\{E\}\[S\_\{T\}^\{4\}\]=T\+3T\(T\-1\)=3T^\{2\}\-2T\\leq 3T^\{2\}\.\(40\)Apply the Paley–Zygmund inequality toY=ST2≥0Y=S\_\{T\}^\{2\}\\geq 0withϑ=1/2\\vartheta=1/2,

ℙ​\(Y≥12​𝔼​Y\)≥\(1−ϑ\)2​\(𝔼​Y\)2𝔼​\[Y2\]≥14⋅T23​T2=112,\\mathbb\{P\}\\Big\(Y\\geq\\tfrac\{1\}\{2\}\\mathbb\{E\}Y\\Big\)\\geq\(1\-\\vartheta\)^\{2\}\\dfrac\{\(\\mathbb\{E\}Y\)^\{2\}\}\{\\mathbb\{E\}\[Y^\{2\}\]\}\\geq\\dfrac\{1\}\{4\}\\cdot\\dfrac\{T^\{2\}\}\{3T^\{2\}\}=\\dfrac\{1\}\{12\},\(41\)equivalent toℙ​\(\|ST\|≥T/2\)≥1/12\\mathbb\{P\}\(\|S\_\{T\}\|\\geq\\sqrt\{T/2\}\)\\geq 1/12\. Hence𝔼​\|ST\|≥T/2/12=T/\(12​2\)\\mathbb\{E\}\|S\_\{T\}\|\\geq\\sqrt\{T/2\}/12=\\sqrt\{T\}/\(12\\sqrt\{2\}\), and \([38](https://arxiv.org/html/2607.27626#S5.E38)\) gives𝔼​\[RegT\]≥T/\(24​2\)\\mathbb\{E\}\[\\operatorname\{Reg\}\_\{T\}\]\\geq\\sqrt\{T\}/\(24\\sqrt\{2\}\)\. Yao’s principle extends the bound to randomized algorithms\. ∎

The lower bound holds in a regime where Assumption[3](https://arxiv.org/html/2607.27626#Thmassumption3)is trivially satisfied, so the difficulty is purely from online learning, not from constraints; adding the affine safe\-set machinery costs nothing in regret order\. Together with the upper bound32​R​G​T\\frac\{3\}\{2\}RG\\sqrt\{T\}of Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1), this matches up to constants and shows that no online algorithm with the same observation set can achieve a better\-than\-T\\sqrt\{T\}rate, even with a hard real\-time deadline structure layered on top of the OCO problem\.

### V\-GMargin and Approximate Projection

Forξ∈ℝ\+N\\xi\\in\\mathbb\{R\}\_\{\+\}^\{N\}, define

θt,iξ\\displaystyle\\theta\_\{t,i\}^\{\\xi\}=Ati\+1−Di\+ξiAti,\\displaystyle=\\dfrac\{A\_\{t\}^\{i\}\+1\-D\_\{i\}\+\\xi\_\{i\}\}\{A\_\{t\}^\{i\}\},\(42\)𝒦tξ\\displaystyle\\mathcal\{K\}\_\{t\}^\{\\xi\}=\{x∈ΔN:gt,i​\(x\)≤−ξi,∀i\}\\displaystyle=\\\{x\\in\\Delta\_\{N\}:g\_\{t,i\}\(x\)\\leq\-\\xi\_\{i\},\\,\\forall i\\\}=\{x∈ΔN:Ct​x≥θtξ\}\.\\displaystyle=\\\{x\\in\\Delta\_\{N\}:C\_\{t\}x\\geq\\theta\_\{t\}^\{\\xi\}\\\}\.\(43\)
###### Theorem 4\(Margin\-safe variant\)\.

Supposeξ∈ℝ\+N\\xi\\in\\mathbb\{R\}\_\{\+\}^\{N\}satisfies

0≤ξi≤Di−1,1≤A1i≤Di−ξi,i∈\[N\],0\\leq\\xi\_\{i\}\\leq D\_\{i\}\-1,\\quad 1\\leq A\_\{1\}^\{i\}\\leq D\_\{i\}\-\\xi\_\{i\},\\quad i\\in\[N\],\(44\)and𝒦tξ≠∅\\mathcal\{K\}\_\{t\}^\{\\xi\}\\neq\\varnothingfor everytt\. If Algorithm[1](https://arxiv.org/html/2607.27626#alg1)replaces𝒦t\\mathcal\{K\}\_\{t\}by𝒦tξ\\mathcal\{K\}\_\{t\}^\{\\xi\}, then all conclusions of Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)continue to hold and the safety bound strengthens to

1≤Ati≤Di−ξi,t=1,…,T\+1\.1\\leq A\_\{t\}^\{i\}\\leq D\_\{i\}\-\\xi\_\{i\},\\qquad t=1,\\dots,T\+1\.\(45\)The regret bound applies for anyu∈⋂t=1T𝒦tξu\\in\\bigcap\_\{t=1\}^\{T\}\\mathcal\{K\}\_\{t\}^\{\\xi\}\.

###### Proof\.

The proof of Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)carries over verbatim with𝒦t\\mathcal\{K\}\_\{t\}replaced by𝒦tξ\\mathcal\{K\}\_\{t\}^\{\\xi\}, givinggt,i​\(xt\)≤−ξig\_\{t,i\}\(x\_\{t\}\)\\leq\-\\xi\_\{i\}and henceAt\+1i≤Di−ξiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}\-\\xi\_\{i\}\. The interval\[1,Di−ξi\]\[1,D\_\{i\}\-\\xi\_\{i\}\]is non\-empty sinceξi≤Di−1\\xi\_\{i\}\\leq D\_\{i\}\-1\. The proof of Lemma[8](https://arxiv.org/html/2607.27626#Thmlemma8), and hence of \([22](https://arxiv.org/html/2607.27626#S5.E22)\), is unchanged when𝒞=𝒦tξ\\mathcal\{C\}=\\mathcal\{K\}\_\{t\}^\{\\xi\}in Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)\. ∎

The margin variant inflates the affine threshold byξi/Ati\\xi\_\{i\}/A\_\{t\}^\{i\}, shrinking𝒦tξ⊆𝒦t\\mathcal\{K\}\_\{t\}^\{\\xi\}\\subseteq\\mathcal\{K\}\_\{t\}so that every executed action sits at distance at leastξi\\xi\_\{i\}from each deadline face\. The same regret bound applies because the polyhedral projection geometry depends only on closed convexity, not on the specific affine offsets\.

###### Theorem 5\(Margin shields against execution perturbations\)\.

Suppose Algorithm[1](https://arxiv.org/html/2607.27626#alg1)computesxt∈𝒦tξx\_\{t\}\\in\\mathcal\{K\}\_\{t\}^\{\\xi\}but executesx^t∈ΔN\\widehat\{x\}\_\{t\}\\in\\Delta\_\{N\}with‖x^t−xt‖2≤εt\\\|\\widehat\{x\}\_\{t\}\-x\_\{t\}\\\|\_\{2\}\\leq\\varepsilon\_\{t\}\. Define

Lt,i=‖∇gt,i‖2=Ati​‖Ct,i:‖2\.L\_\{t,i\}=\\\|\\nabla g\_\{t,i\}\\\|\_\{2\}=A\_\{t\}^\{i\}\\\|C\_\{t,i:\}\\\|\_\{2\}\.\(46\)Ifξi≥Lt,i​εt\\xi\_\{i\}\\geq L\_\{t,i\}\\varepsilon\_\{t\}for everyi∈\[N\]i\\in\[N\]andt∈\[T\]t\\in\[T\], thengt,i​\(x^t\)≤0g\_\{t,i\}\(\\widehat\{x\}\_\{t\}\)\\leq 0, and in particularAt\+1i≤DiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}along the executed trajectory\.

###### Proof\.

gt,ig\_\{t,i\}is affine with∇gt,i=−Ati​Ct,i:⊤\\nabla g\_\{t,i\}=\-A\_\{t\}^\{i\}C\_\{t,i:\}^\{\\top\}, so‖∇gt,i‖2=Lt,i\\\|\\nabla g\_\{t,i\}\\\|\_\{2\}=L\_\{t,i\}\. By Cauchy–Schwarz,gt,i​\(x^t\)≤gt,i​\(xt\)\+Lt,i​‖x^t−xt‖2≤−ξi\+Lt,i​εt≤0g\_\{t,i\}\(\\widehat\{x\}\_\{t\}\)\\leq g\_\{t,i\}\(x\_\{t\}\)\+L\_\{t,i\}\\\|\\widehat\{x\}\_\{t\}\-x\_\{t\}\\\|\_\{2\}\\leq\-\\xi\_\{i\}\+L\_\{t,i\}\\varepsilon\_\{t\}\\leq 0\. ∎

The conditionξ≥L​ε\\xi\\geq L\\varepsilonconverts an analytic margin into resilience against arbitrary execution noise of magnitudeεt\\varepsilon\_\{t\}, including quantization, integral rounding, and physical actuation error\. BecauseLt,i≤N​DiL\_\{t,i\}\\leq\\sqrt\{N\}D\_\{i\}for the canonical loss, a margin scaling asN​Dmax​ε\\sqrt\{N\}D\_\{\\max\}\\varepsilonis enough; the cost is only anO​\(ξ\)O\(\\xi\)shrinkage of the safe set, not a change in regret rate\.

###### Theorem 6\(Feasible approximate projection\)\.

If at every slot the oracle returns a feasiblex~t∈𝒦t\\widetilde\{x\}\_\{t\}\\in\\mathcal\{K\}\_\{t\}with‖x~t−Π𝒦t​\(zt\)‖2≤εt\\\|\\widetilde\{x\}\_\{t\}\-\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\(z\_\{t\}\)\\\|\_\{2\}\\leq\\varepsilon\_\{t\}, and the proposal updates byzt\+1=ΠΔN​\(x~t−η​st\)z\_\{t\+1\}=\\Pi\_\{\\Delta\_\{N\}\}\(\\widetilde\{x\}\_\{t\}\-\\eta s\_\{t\}\), then hard safety still holds and for anyu∈𝒦1:Tu\\in\\mathcal\{K\}\_\{1:T\},

RegT⁡\(u\)≤R22​η\+η​G2​T2\+12​η​∑t=1T\(2​R​εt\+εt2\)\.\\operatorname\{Reg\}\_\{T\}\(u\)\\leq\\dfrac\{R^\{2\}\}\{2\\eta\}\+\\dfrac\{\\eta G^\{2\}T\}\{2\}\+\\dfrac\{1\}\{2\\eta\}\\sum\_\{t=1\}^\{T\}\(2R\\varepsilon\_\{t\}\+\\varepsilon\_\{t\}^\{2\}\)\.\(47\)

###### Proof\.

Sincex~t∈𝒦t\\widetilde\{x\}\_\{t\}\\in\\mathcal\{K\}\_\{t\}, Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)givesgt,i​\(x~t\)≤0g\_\{t,i\}\(\\widetilde\{x\}\_\{t\}\)\\leq 0, soAt\+1i≤DiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}by \([2](https://arxiv.org/html/2607.27626#S3.E2)\); the lower boundAt\+1i≥1A\_\{t\+1\}^\{i\}\\geq 1and the queue\-zero certificate follow verbatim from Lemmas[6](https://arxiv.org/html/2607.27626#Thmlemma6)and[7](https://arxiv.org/html/2607.27626#Thmlemma7)applied withx~t\\widetilde\{x\}\_\{t\}in place ofxtx\_\{t\}\.

For the regret, letpt=Π𝒦t​\(zt\)p\_\{t\}=\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\(z\_\{t\}\)\. Foru∈𝒦tu\\in\\mathcal\{K\}\_\{t\}, Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)gives‖pt−u‖2≤‖zt−u‖2\\\|p\_\{t\}\-u\\\|\_\{2\}\\leq\\\|z\_\{t\}\-u\\\|\_\{2\}\. By the triangle inequality and‖x~t−pt‖2≤εt\\\|\\widetilde\{x\}\_\{t\}\-p\_\{t\}\\\|\_\{2\}\\leq\\varepsilon\_\{t\},

‖x~t−u‖2≤‖pt−u‖2\+εt≤‖zt−u‖2\+εt\.\\\|\\widetilde\{x\}\_\{t\}\-u\\\|\_\{2\}\\leq\\\|p\_\{t\}\-u\\\|\_\{2\}\+\\varepsilon\_\{t\}\\leq\\\|z\_\{t\}\-u\\\|\_\{2\}\+\\varepsilon\_\{t\}\.\(48\)Squaring and using‖zt−u‖2≤R\\\|z\_\{t\}\-u\\\|\_\{2\}\\leq R,

‖x~t−u‖22≤‖zt−u‖22\+2​R​εt\+εt2\.\\\|\\widetilde\{x\}\_\{t\}\-u\\\|\_\{2\}^\{2\}\\leq\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}\+2R\\varepsilon\_\{t\}\+\\varepsilon\_\{t\}^\{2\}\.\(49\)The proposal\-update projection together withu∈𝒦t⊆ΔNu\\in\\mathcal\{K\}\_\{t\}\\subseteq\\Delta\_\{N\}and Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)on𝒞=ΔN\\mathcal\{C\}=\\Delta\_\{N\}give‖zt\+1−u‖22≤‖x~t−η​st−u‖22\\\|z\_\{t\+1\}\-u\\\|\_\{2\}^\{2\}\\leq\\\|\\widetilde\{x\}\_\{t\}\-\\eta s\_\{t\}\-u\\\|\_\{2\}^\{2\}\. Expanding and substituting \([49](https://arxiv.org/html/2607.27626#S5.E49)\),

⟨st,x~t−u⟩\\displaystyle\\langle s\_\{t\},\\widetilde\{x\}\_\{t\}\-u\\rangle≤‖zt−u‖22−‖zt\+1−u‖222​η\+η2​‖st‖22\\displaystyle\\leq\\dfrac\{\\\|z\_\{t\}\-u\\\|\_\{2\}^\{2\}\-\\\|z\_\{t\+1\}\-u\\\|\_\{2\}^\{2\}\}\{2\\eta\}\+\\dfrac\{\\eta\}\{2\}\\\|s\_\{t\}\\\|\_\{2\}^\{2\}\+2​R​εt\+εt22​η\.\\displaystyle\\quad\+\\dfrac\{2R\\varepsilon\_\{t\}\+\\varepsilon\_\{t\}^\{2\}\}\{2\\eta\}\.\(50\)Convexity atx~t\\widetilde\{x\}\_\{t\}givesft​\(x~t\)−ft​\(u\)≤⟨st,x~t−u⟩f\_\{t\}\(\\widetilde\{x\}\_\{t\}\)\-f\_\{t\}\(u\)\\leq\\langle s\_\{t\},\\widetilde\{x\}\_\{t\}\-u\\rangle\. Summing \([50](https://arxiv.org/html/2607.27626#S5.E50)\) overtt, the first term telescopes to at mostR2/\(2​η\)R^\{2\}/\(2\\eta\), the second toη​G2​T/2\\eta G^\{2\}T/2, and the third to12​η​∑t\(2​R​εt\+εt2\)\\frac\{1\}\{2\\eta\}\\sum\_\{t\}\(2R\\varepsilon\_\{t\}\+\\varepsilon\_\{t\}^\{2\}\)\. Combining yields \([47](https://arxiv.org/html/2607.27626#S5.E47)\)\. ∎

A marginξ≥L​ε\\xi\\geq L\\varepsilonbuysmodeled\-state safetyagainst execution noise, and a feasible projection oracle accurate toεt=O​\(1/T\)\\varepsilon\_\{t\}=O\(1/\\sqrt\{T\}\)preserves theO​\(T\)O\(\\sqrt\{T\}\)regret order\. Both together let the system designer trade a small amount of slack for resilience to numerical and physical noise without changing the rate\.

### V\-HWeakly\-Hard Real\-Time Implications

###### Definition 1\(AoI\-domain\(m,k\)\(m,k\)\-firm semantics\)\.

With miss indicatorvti=𝟏​\{Ati\>Di\}v\_\{t\}^\{i\}=\\mathbf\{1\}\\\{A\_\{t\}^\{i\}\>D\_\{i\}\\\}, sensoriiis\(mi,ki\)\(m\_\{i\},k\_\{i\}\)\-firm if∑τ=tt\+ki−1\(1−vτi\)≥mi\\sum\_\{\\tau=t\}^\{t\+k\_\{i\}\-1\}\(1\-v\_\{\\tau\}^\{i\}\)\\geq m\_\{i\}fort=1,…,T−ki\+1t=1,\\dots,T\-k\_\{i\}\+1\.

###### Corollary 1\(PAoI safety implies all\(m,k\)\(m,k\)\-firm requirements\)\.

Under Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1), every sensoriiis\(mi,ki\)\(m\_\{i\},k\_\{i\}\)\-firm for everyki∈ℕk\_\{i\}\\in\\mathbb\{N\}andmi≤kim\_\{i\}\\leq k\_\{i\}\. Conversely,\(1,1\)\(1,1\)\-firm at every slot is equivalent toAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}everywhere\.

###### Proof\.

By Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1),Ati≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}at every slotttalong the trajectory of Algorithm[1](https://arxiv.org/html/2607.27626#alg1), hencevti=𝟏​\{Ati\>Di\}=0v\_\{t\}^\{i\}=\\mathbf\{1\}\\\{A\_\{t\}^\{i\}\>D\_\{i\}\\\}=0for alltt\. For any window\[t,t\+ki−1\]\[t,t\+k\_\{i\}\-1\],∑τ=tt\+ki−1\(1−vτi\)=ki≥mi\\sum\_\{\\tau=t\}^\{t\+k\_\{i\}\-1\}\(1\-v\_\{\\tau\}^\{i\}\)=k\_\{i\}\\geq m\_\{i\}whenevermi≤kim\_\{i\}\\leq k\_\{i\}, so sensoriiis\(mi,ki\)\(m\_\{i\},k\_\{i\}\)\-firm by Definition[1](https://arxiv.org/html/2607.27626#Thmdefinition1)\. The converse direction follows by definition:\(1,1\)\(1,1\)\-firm requires1−vti≥11\-v\_\{t\}^\{i\}\\geq 1, i\.e\.,vti=0v\_\{t\}^\{i\}=0, equivalentlyAti≤DiA\_\{t\}^\{i\}\\leq D\_\{i\}at every slot, which is exactly peak\-AoI safety\. ∎

Corollary[1](https://arxiv.org/html/2607.27626#Thmcorollary1)shows that hard peak\-AoI safety is the strongest weakly\-hard guarantee on the AoI\-firm hierarchy: it implies\(m,k\)\(m,k\)\-firm for every admissible pair, and the strictest case\(1,1\)\(1,1\)\-firm coincides with peak\-AoI safety\. Algorithms that achieve only sublinear cumulative violation cannot certify\(1,1\)\(1,1\)\-firm, which is precisely the failure mode flagged by Proposition[1](https://arxiv.org/html/2607.27626#Thmproposition1)\.

### V\-IFractional\-to\-Integral Safety Interface

###### Theorem 7\(Necessary and sufficient condition for safe single\-packet action\)\.

Define𝒥t=\{j∈\[N\]:ej∈𝒦t\}\\mathcal\{J\}\_\{t\}=\\\{j\\in\[N\]:e\_\{j\}\\in\\mathcal\{K\}\_\{t\}\\\}\. A safe integral action exists at slotttiff∃j\\exists jwithCt,i​j≥θt,iC\_\{t,ij\}\\geq\\theta\_\{t,i\}for allii, equivalently𝒥t≠∅\\mathcal\{J\}\_\{t\}\\neq\\varnothing\. A randomized integral implementation has sample\-path PAoI safety iff its support is contained in𝒥t\\mathcal\{J\}\_\{t\}\.

###### Proof\.

For anyj∈\[N\]j\\in\[N\],Ct​ejC\_\{t\}e\_\{j\}is thejj\-th column ofCtC\_\{t\}, so itsii\-th coordinate isCt,i​jC\_\{t,ij\}\. By Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1),ej∈𝒦te\_\{j\}\\in\\mathcal\{K\}\_\{t\}if and only ifCt,i​j≥θt,iC\_\{t,ij\}\\geq\\theta\_\{t,i\}for everyi∈\[N\]i\\in\[N\], which establishes the first equivalence\.

For the randomized statement, letIt∼νI\_\{t\}\\sim\\nube a random integral action with distributionν\\nuon\[N\]\[N\]\. Ifsupp​\(ν\)⊆𝒥t\\mathrm\{supp\}\(\\nu\)\\subseteq\\mathcal\{J\}\_\{t\}, then every realizationIt=jI\_\{t\}=jsatisfiesej∈𝒦te\_\{j\}\\in\\mathcal\{K\}\_\{t\}and hencegt,i​\(ej\)≤0g\_\{t,i\}\(e\_\{j\}\)\\leq 0, so the executed AoI satisfiesAt\+1i≤DiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}on every sample path\. Conversely, supposesupp​\(ν\)⊈𝒥t\\mathrm\{supp\}\(\\nu\)\\not\\subseteq\\mathcal\{J\}\_\{t\}and pickj0∈supp​\(ν\)∖𝒥tj\_\{0\}\\in\\mathrm\{supp\}\(\\nu\)\\setminus\\mathcal\{J\}\_\{t\}\. Thenν​\(\{j0\}\)\>0\\nu\(\\\{j\_\{0\}\\\}\)\>0,ej0∉𝒦te\_\{j\_\{0\}\}\\notin\\mathcal\{K\}\_\{t\}, and there existsi0i\_\{0\}withgt,i0​\(ej0\)\>0g\_\{t,i\_\{0\}\}\(e\_\{j\_\{0\}\}\)\>0, so the eventIt=j0I\_\{t\}=j\_\{0\}has positive probability and producesAt\+1i0\>Di0A\_\{t\+1\}^\{i\_\{0\}\}\>D\_\{i\_\{0\}\}, breaking sample\-path safety\. ∎

IfCtC\_\{t\}contains expected success coefficients instead,ej∈𝒦te\_\{j\}\\in\\mathcal\{K\}\_\{t\}certifies only conditional expected AoI\. Let𝒪t\\mathcal\{O\}\_\{t\}be the set of possible realized outcome matrices\. Packet\-level sample\-path safety requires the stronger outcome\-wise set

𝒥tout=\{j∈\[N\]:C​ej≥θt,∀C∈𝒪t\}\\mathcal\{J\}\_\{t\}^\{\\rm out\}=\\\{j\\in\[N\]:Ce\_\{j\}\\geq\\theta\_\{t\},\\ \\forall C\\in\\mathcal\{O\}\_\{t\}\\\}to be non\-empty, and any randomized implementation must be supported on𝒥tout\\mathcal\{J\}\_\{t\}^\{\\rm out\}\. Deterministic service, worst\-case service envelopes, or sufficient redundancy can make this condition hold; an expectation\-based safe set alone cannot\.

A fractional safe action does not in general imply randomized integral safety\. As a one\-slot two\-sensor counterexample, takeN=2N=2,At1=At2=2A\_\{t\}^\{1\}=A\_\{t\}^\{2\}=2,D1=D2=2D\_\{1\}=D\_\{2\}=2,Ct=I2C\_\{t\}=I\_\{2\}: thenθt=\(1/2,1/2\)\\theta\_\{t\}=\(1/2,1/2\)and the fractional actionx=\(1/2,1/2\)∈𝒦tx=\(1/2,1/2\)\\in\\mathcal\{K\}\_\{t\}, sinceCt​x=\(1/2,1/2\)=θtC\_\{t\}x=\(1/2,1/2\)=\\theta\_\{t\}, but the only two integral actionsCt​e1=\(1,0\)C\_\{t\}e\_\{1\}=\(1,0\)andCt​e2=\(0,1\)C\_\{t\}e\_\{2\}=\(0,1\)each leave one sensor unrefreshed and yieldAt\+1i=3\>DiA\_\{t\+1\}^\{i\}=3\>D\_\{i\}for that sensor\. Hence𝒥t=∅\\mathcal\{J\}\_\{t\}=\\varnothingeven though𝒦t≠∅\\mathcal\{K\}\_\{t\}\\neq\\varnothing, so any randomized rounding produces a deadline miss with probability one\.Thus support\-restricted rounding is safe only if𝒥t\\mathcal\{J\}\_\{t\}\(or𝒥tout\\mathcal\{J\}\_\{t\}^\{\\rm out\}under outcome uncertainty\) is non\-empty; increasing the safety margin cannot create integral feasibility\.

### V\-JRobust Safe Projection Under Partial Channel Observability

###### Definition 2\(Robust safe set\)\.

If only𝒰t⊆\[0,1\]N×N\\mathcal\{U\}\_\{t\}\\subseteq\[0,1\]^\{N\\times N\}withCt∈𝒰tC\_\{t\}\\in\\mathcal\{U\}\_\{t\}is known at slottt,

𝒦t,rob=\{x∈ΔN:C​x≥θt,∀C∈𝒰t\}\.\\mathcal\{K\}\_\{t,\\rm rob\}=\\\{x\\in\\Delta\_\{N\}:Cx\\geq\\theta\_\{t\},\\,\\forall C\\in\\mathcal\{U\}\_\{t\}\\\}\.\(51\)

###### Theorem 8\(Robust safety and regret\)\.

If𝒦t,rob≠∅\\mathcal\{K\}\_\{t,\\rm rob\}\\neq\\varnothingfor everyttand Algorithm[1](https://arxiv.org/html/2607.27626#alg1)uses𝒦t,rob\\mathcal\{K\}\_\{t,\\rm rob\}in place of𝒦t\\mathcal\{K\}\_\{t\}, then for every realized sequenceCt∈𝒰tC\_\{t\}\\in\\mathcal\{U\}\_\{t\}all conclusions of Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)continue to hold; the static\-regret bound applies for anyu∈⋂t𝒦t,robu\\in\\bigcap\_\{t\}\\mathcal\{K\}\_\{t,\\rm rob\}\.

###### Proof\.

𝒦t,rob\\mathcal\{K\}\_\{t,\\rm rob\}is non\-empty closed convex \(intersection ofΔN\\Delta\_\{N\}with closed half\-spaces\), so Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)applies andxt∈𝒦t,robx\_\{t\}\\in\\mathcal\{K\}\_\{t,\\rm rob\}impliesCt​xt≥θtC\_\{t\}x\_\{t\}\\geq\\theta\_\{t\}sinceCt∈𝒰tC\_\{t\}\\in\\mathcal\{U\}\_\{t\}\. Lemma[1](https://arxiv.org/html/2607.27626#Thmlemma1)givesgt,i​\(xt\)≤0g\_\{t,i\}\(x\_\{t\}\)\\leq 0, so the safety induction of Lemma[6](https://arxiv.org/html/2607.27626#Thmlemma6)carries through\. The regret proof is identical to Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)with𝒞=𝒦t,rob\\mathcal\{C\}=\\mathcal\{K\}\_\{t,\\rm rob\}in Lemma[4](https://arxiv.org/html/2607.27626#Thmlemma4)\. ∎

###### Corollary 2\(Rectangular lower\-bound uncertainty\)\.

If𝒰t=\{C∈\[0,1\]N×N:C≥C¯t\}\\mathcal\{U\}\_\{t\}=\\\{C\\in\[0,1\]^\{N\\times N\}:C\\geq\\underline\{C\}\_\{t\}\\\}, then𝒦t,rob=\{x∈ΔN:C¯t​x≥θt\}\\mathcal\{K\}\_\{t,\\rm rob\}=\\\{x\\in\\Delta\_\{N\}:\\underline\{C\}\_\{t\}x\\geq\\theta\_\{t\}\\\}\.

###### Proof\.

C¯t​x≥θt\\underline\{C\}\_\{t\}x\\geq\\theta\_\{t\}withC≥C¯tC\\geq\\underline\{C\}\_\{t\}andx≥0x\\geq 0givesC​x≥θtCx\\geq\\theta\_\{t\}, sox∈𝒦t,robx\\in\\mathcal\{K\}\_\{t,\\rm rob\}\. The converse follows sinceC¯t∈𝒰t\\underline\{C\}\_\{t\}\\in\\mathcal\{U\}\_\{t\}\. ∎

Theorem[8](https://arxiv.org/html/2607.27626#Thmtheorem8)closes the gap between idealized analysis and practical deployment, where the controller often only has access to channel state estimates\. Lemma[3](https://arxiv.org/html/2607.27626#Thmlemma3)guarantees that any coordinatewise lower envelopeC¯t≤Ct\\underline\{C\}\_\{t\}\\leq C\_\{t\}produces a tighter, safer polyhedron, and Corollary[2](https://arxiv.org/html/2607.27626#Thmcorollary2)singles out the rectangular case in which the robust projection collapses to a standard QP withC¯t\\underline\{C\}\_\{t\}in place ofCtC\_\{t\}, so the robust algorithm has the same per\-slot complexity as the nominal one\.

### V\-KClosed Competitive\-Ratio Statements

In the canonical\-loss regime, the cumulative algorithmic cost equals the weighted AoI:

JTalg=∑t=1T∑i=1Nwi​At\+1i=∑t=1Tftcan​\(xt\)\.J\_\{T\}^\{\\rm alg\}=\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{N\}w\_\{i\}A\_\{t\+1\}^\{i\}=\\sum\_\{t=1\}^\{T\}f\_\{t\}^\{\\rm can\}\(x\_\{t\}\)\.\(52\)LetJToffJ\_\{T\}^\{\\rm off\}denote the cumulative weighted AoI of the offline dynamic optimum, the policy that knows\(Ct\)t=1T\(C\_\{t\}\)\_\{t=1\}^\{T\}in advance and minimizesJTJ\_\{T\}subject to the same fluid AoI dynamics\.

###### Theorem 9\(Deadline\-induced competitive ratio\)\.

Under Assumptions[1](https://arxiv.org/html/2607.27626#Thmassumption1)–[3](https://arxiv.org/html/2607.27626#Thmassumption3)and the canonical loss,

JToff≥T​W,JTalg≤T​∑i=1Nwi​Di,J\_\{T\}^\{\\rm off\}\\geq TW,\\qquad J\_\{T\}^\{\\rm alg\}\\leq T\\sum\_\{i=1\}^\{N\}w\_\{i\}D\_\{i\},\(53\)hence

JTalgJToff≤ρD:=∑iwi​DiW\.\\dfrac\{J\_\{T\}^\{\\rm alg\}\}\{J\_\{T\}^\{\\rm off\}\}\\leq\\rho\_\{D\}:=\\dfrac\{\\sum\_\{i\}w\_\{i\}D\_\{i\}\}\{W\}\.\(54\)With marginξ\\xi,DiD\_\{i\}may be replaced byDi−ξiD\_\{i\}\-\\xi\_\{i\}\.

###### Proof\.

For any policyπ\\piand slottt,0≤\(Ct​xtπ\)i≤10\\leq\(C\_\{t\}x\_\{t\}^\{\\pi\}\)\_\{i\}\\leq 1, so by inductionAt\+1i,π≥1A\_\{t\+1\}^\{i,\\pi\}\\geq 1and∑iwi​At\+1i,π≥W\\sum\_\{i\}w\_\{i\}A\_\{t\+1\}^\{i,\\pi\}\\geq W, henceJToff≥T​WJ\_\{T\}^\{\\rm off\}\\geq TW\. Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)givesAt\+1i≤DiA\_\{t\+1\}^\{i\}\\leq D\_\{i\}, soJTalg≤T​∑iwi​DiJ\_\{T\}^\{\\rm alg\}\\leq T\\sum\_\{i\}w\_\{i\}D\_\{i\}\. Dividing yields \([54](https://arxiv.org/html/2607.27626#S5.E54)\)\. ∎

The ratioρD\\rho\_\{D\}is data\-only, in the sense that it is computable fromwwandDDalone, without any knowledge of the channel realization or the loss sequence; this is exactly the regime in which classical adversarial AoI competitive ratios are usually stated, butρD\\rho\_\{D\}additionally respects the modeled\-state feasibility scope of Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1), which is unavailable to soft\-cost competitive analyses such as\[[5](https://arxiv.org/html/2607.27626#bib.bib12),[9](https://arxiv.org/html/2607.27626#bib.bib13)\]\.

###### Theorem 10\(Regret\-refined trace\-wise ratio\)\.

Suppose the canonical loss is used and𝒦1:T≠∅\\mathcal\{K\}\_\{1:T\}\\neq\\varnothing\. Define the trace\-wise static safe benchmark

JTstat=minu∈𝒦1:T​∑t=1Tftcan​\(u\),J\_\{T\}^\{\\rm stat\}=\\min\_\{u\\in\\mathcal\{K\}\_\{1:T\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}^\{\\rm can\}\(u\),\(55\)and letαT:=JTstat/JToff\\alpha\_\{T\}:=J\_\{T\}^\{\\rm stat\}/J\_\{T\}^\{\\rm off\}\. Withη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\), Algorithm[1](https://arxiv.org/html/2607.27626#alg1)satisfies

JTalg≤JTstat\+R​G​T,J\_\{T\}^\{\\rm alg\}\\leq J\_\{T\}^\{\\rm stat\}\+RG\\sqrt\{T\},\(56\)JTalgJToff≤αT\+R​GW​T\.\\dfrac\{J\_\{T\}^\{\\rm alg\}\}\{J\_\{T\}^\{\\rm off\}\}\\leq\\alpha\_\{T\}\+\\dfrac\{RG\}\{W\\sqrt\{T\}\}\.\(57\)

###### Proof\.

LetuT⋆∈arg⁡minu∈𝒦1:T​∑tftcan​\(u\)u\_\{T\}^\{\\star\}\\in\\arg\\min\_\{u\\in\\mathcal\{K\}\_\{1:T\}\}\\sum\_\{t\}f\_\{t\}^\{\\rm can\}\(u\)\. Theorem[1](https://arxiv.org/html/2607.27626#Thmtheorem1)withη=R/\(G​T\)\\eta=R/\(G\\sqrt\{T\}\)givesJTalg−JTstat≤R​G​TJ\_\{T\}^\{\\rm alg\}\-J\_\{T\}^\{\\rm stat\}\\leq RG\\sqrt\{T\}, the first inequality\. Dividing byJToff≥T​WJ\_\{T\}^\{\\rm off\}\\geq TWfrom Theorem[9](https://arxiv.org/html/2607.27626#Thmtheorem9)gives the second\. ∎

The deadline\-induced ratioρD\\rho\_\{D\}depends only on weights and deadlines, which is the tightest data\-only ratio achievable for a hard\-safety algorithm\. The trace\-wise ratio sharpens this whenever a single safe action does well across the trace, with an additiveO​\(1/T\)O\(1/\\sqrt\{T\}\)deviation fromαT\\alpha\_\{T\}, and it is the only competitive bound we are aware of that is simultaneously refined by no\-regret learning, certified for adversarial channels, and tight against the offline dynamic optimum on traces whereαT\\alpha\_\{T\}approaches one\.

### V\-LWhy Long\-Term Virtual Queues Cannot Replace the Hard Shield

###### Proposition 1\(Sublinear cumulative violation⇏\\not\\Rightarrowzero stage\-wise violation\)\.

There exist trajectories of a long\-term\-constraint OCO algorithm with∑t=1T\[gt​\(xt\)\]\+=O​\(1\)\\sum\_\{t=1\}^\{T\}\[g\_\{t\}\(x\_\{t\}\)\]\_\{\+\}=O\(1\)and yet\[gt0​\(xt0\)\]\+\>0\[g\_\{t\_\{0\}\}\(x\_\{t\_\{0\}\}\)\]\_\{\+\}\>0for somet0∈\[T\]t\_\{0\}\\in\[T\]\. In particular, sublinear or even bounded cumulative violation does not imply\(1,1\)\(1,1\)\-firm peak\-AoI safety\.

###### Proof\.

Consider any trajectory with\[g1​\(x1\)\]\+=1\[g\_\{1\}\(x\_\{1\}\)\]\_\{\+\}=1and\[gt​\(xt\)\]\+=0\[g\_\{t\}\(x\_\{t\}\)\]\_\{\+\}=0for allt≥2t\\geq 2\. Then∑t=1T\[gt​\(xt\)\]\+=1=O​\(1\)\\sum\_\{t=1\}^\{T\}\[g\_\{t\}\(x\_\{t\}\)\]\_\{\+\}=1=O\(1\)for everyTT, satisfying any sublinear cumulative\-violation guarantee, but the slot\-1 violation\[g1​\(x1\)\]\+\>0\[g\_\{1\}\(x\_\{1\}\)\]\_\{\+\}\>0producesA2i\>DiA\_\{2\}^\{i\}\>D\_\{i\}for some sensorii, breaking peak\-AoI safety and the corresponding\(1,1\)\(1,1\)\-firm requirement\. Such trajectories are realized by drift\-plus\-penalty schedulers operating with an empty initial queue under an adversarialC1C\_\{1\}that makes𝒦1\\mathcal\{K\}\_\{1\}a tight singleton: the unconstrained gradient step lands outside𝒦1\\mathcal\{K\}\_\{1\}, the queue absorbs the violation in subsequent slots, and the cumulative sum staysO​\(1\)O\(1\)even though the deadline is missed att=1t=1\. ∎

A single missed deadline can already trip a circuit breaker, destabilize a closed\-loop controller, or violate a\(1,1\)\(1,1\)\-firm requirement, so the hard projection in Algorithm[1](https://arxiv.org/html/2607.27626#alg1)is a structural necessity rather than a convenience: the queueQtQ\_\{t\}is repurposed as an a\-posteriori certificate, while safety itself is conferred by the per\-slot shieldΠ𝒦t\\Pi\_\{\\mathcal\{K\}\_\{t\}\}\. This shield\-and\-dual decomposition loses nothing in regret order while gaining everything in real\-time semantics\.

## VIExperiments

We evaluate OCO\-PAoI\-Hard on an adversarial shared\-channel testbed targeting the three guarantees:modeled fluid\-state PAoI safety\(Thm\.[1](https://arxiv.org/html/2607.27626#Thmtheorem1)\),O​\(T\)O\(\\sqrt\{T\}\)regret \(Thms\.[1](https://arxiv.org/html/2607.27626#Thmtheorem1),[2](https://arxiv.org/html/2607.27626#Thmtheorem2)\), and margin\-safe robustness \(Thm\.[5](https://arxiv.org/html/2607.27626#Thmtheorem5)\)\. Default settings:N=4N=4,D=\(6,7,8,9\)D=\(6,7,8,9\),w=𝟏w=\\mathbf\{1\},A1=𝟏A\_\{1\}=\\mathbf\{1\},ηt=R/\(G​t\)\\eta\_\{t\}=R/\(G\\sqrt\{t\}\)withR=2R=\\sqrt\{2\}andGGfrom Lemma[5](https://arxiv.org/html/2607.27626#Thmlemma5); each number is averaged over1010seeds\. Baselines:*Vanilla OGD*\(simplex\-projected gradient without shield, same step size, so any safety gap is attributable to the missing shield\);*Long\-term VQ*\(drift\-plus\-penaltyarg⁡minx⁡V​ft​\(x\)\+∑iQt,i​gt,i​\(x\)\\arg\\min\_\{x\}Vf\_\{t\}\(x\)\+\\sum\_\{i\}Q\_\{t,i\}g\_\{t,i\}\(x\)withV=TV=\\sqrt\{T\}, the standard parameter achievingO​\(T\)O\(\\sqrt\{T\}\)regret andO​\(T\)O\(\\sqrt\{T\}\)cumulative violation\);*Greedy max\-deficit*\(arg⁡mini⁡\(Di−Ati\)\\arg\\min\_\{i\}\(D\_\{i\}\-A\_\{t\}^\{i\}\)\); and*Round\-robin*\. The trap channel fixes a safe column ofCtC\_\{t\}with entries0\.220\.22and a trap column in\{0,1\}\\\{0,1\\\}aligned with the canonical gradient, then biases the gradient by∑iwi​Di\\sum\_\{i\}w\_\{i\}D\_\{i\}toward the trap, pulling any gradient\-follower off the safe column;𝒦t\\mathcal\{K\}\_\{t\}remains non\-empty at every slot\.

![Refer to caption](https://arxiv.org/html/2607.27626v1/x1.png)Figure 2:Modeled fluid\-state peak\-AoI safetyon the adversarial trap channel \(N=4N\\\!=\\\!4,T=1000T\\\!=\\\!1000,1010seeds,D=\(6,7,8,9\)D=\(6,7,8,9\)\)\. \(a\) AoI trajectory of sensor 1 during the first200200slots, with deadlineD1=6D\_\{1\}\\\!=\\\!6\(dotted\); only OCO\-PAoI\-Hard \(red\) stays at or below it\. \(b\) Running\-max excessmaxτ≤t,i\[Aτi−Di\]\+\\max\_\{\\tau\\leq t,\\,i\}\[A\_\{\\tau\}^\{i\}\-D\_\{i\}\]\_\{\+\}\(log scale; visible red floor is a plotting offset, true value0\)\. \(c\) Cumulative deadline violation∑τ≤t,i\[gτ,i​\(xτ\)\]\+\\sum\_\{\\tau\\leq t,\\,i\}\[g\_\{\\tau,i\}\(x\_\{\\tau\}\)\]\_\{\+\}\(log scale\)\. \(d\) Per\-seed slot\-wise miss rate\.TABLE III:Fluid\-state PAoI safetyon the four\-sensor adversarial trap channel \(T=1000T\\\!=\\\!1000,1010seeds\)\. “Miss” is the per\-slot miss rate; “Excess” ismaxt,i\[Ati−Di\]\+\\max\_\{t,i\}\[A\_\{t\}^\{i\}\-D\_\{i\}\]\_\{\+\}; “CumViol” is∑t,i\[gt,i​\(xt\)\]\+\\sum\_\{t,i\}\[g\_\{t,i\}\(x\_\{t\}\)\]\_\{\+\}; “Cost” is∑tftcan​\(xt\)\\sum\_\{t\}f\_\{t\}^\{\\rm can\}\(x\_\{t\}\)\. Bold marks the only zero\-violation entry\. Long\-term VQ reaches the lowest cost only by accepting per\-slot violations\.OnT=1000T=1000\(Fig\.[2](https://arxiv.org/html/2607.27626#S6.F2), Table[III](https://arxiv.org/html/2607.27626#S6.T3)\), OCO\-PAoI\-Hard recordszero modeled fluid\-state deadline violationsacross all1010seeds, with maximum AoI excess1\.3×10−151\.3\\\!\\times\\\!10^\{\-15\}\(round\-off\) and exactly zero cumulative violation\. The four baselines miss1\.651\.65–64\.0%64\.0\\%of slots with overshoots up to12\.9612\.96\. Long\-term VQ achieves a lower weighted\-AoI cost \(7,9507\{,\}950vs\.20,07520\{,\}075\) only by accepting per\-slot violations \(Prop\.[1](https://arxiv.org/html/2607.27626#Thmproposition1)\); among violation\-free methods, ours has the lowest cost, beating Vanilla OGD, Greedy max\-deficit, and Round\-robin by33to3\.6%3\.6\\%\.

![Refer to caption](https://arxiv.org/html/2607.27626v1/x2.png)Figure 3:Sublinear regret scaling under both inactive and active safe sets \(N=4N\\\!=\\\!4,1010seeds perTT\)\. \(a\) Static regretRegT\\operatorname\{Reg\}\_\{T\}vs\.TT\(log\-log\) againstR​G​TRG\\sqrt\{T\}\(gray dashed\); empirical slopes0\.4840\.484\(inactive\) and0\.3240\.324\(active\)\. \(b\) Normalized ratioRegT/\(R​G​T\)\\operatorname\{Reg\}\_\{T\}/\(RG\\sqrt\{T\}\)stays below the theoretical ceiling11at everyTT\.*Sublinear regret\.*We sweepT∈\{200,500,103,2×103,5×103,104,2×104\}T\\in\\\{200,500,10^\{3\},2\\\!\\times\\\!10^\{3\},5\\\!\\times\\\!10^\{3\},10^\{4\},2\\\!\\times\\\!10^\{4\}\\\}in two regimes\. The*inactive*regime \(Di=T\+10D\_\{i\}=T\+10, so𝒦t=ΔN\\mathcal\{K\}\_\{t\}=\\Delta\_\{N\}\) reduces the algorithm to OGD against adversarial Rademacher linear losses, isolating unconstrained\-OCO behavior\. The*active*regime keepsD=\(6,7,8,9\)D=\(6,7,8,9\)and uses the static safe comparatoru⋆∈arg⁡minu∈𝒦1:T​∑tftcan​\(u\)u^\{\\star\}\\in\\arg\\min\_\{u\\in\\mathcal\{K\}\_\{1:T\}\}\\sum\_\{t\}f\_\{t\}^\{\\rm can\}\(u\)computed by LP \(linprog/HiGHS\) on𝒦1:T\\mathcal\{K\}\_\{1:T\}\. Fig\.[3](https://arxiv.org/html/2607.27626#S6.F3)confirms theT\\sqrt\{T\}rate: empirical log\-log slopes are0\.4840\.484\(inactive\) and0\.3240\.324\(active\), both below the0\.50\.5ceiling of Thm\.[1](https://arxiv.org/html/2607.27626#Thmtheorem1)\. The normalized ratioRegT/\(R​G​T\)\\operatorname\{Reg\}\_\{T\}/\(RG\\sqrt\{T\}\)stays strictly below11, near0\.400\.40in the inactive regime and decaying from0\.360\.36to0\.150\.15in the active regime, indicating the shield acts as an implicit regularizer; this matches the trace\-wise refinement of Thm\.[10](https://arxiv.org/html/2607.27626#Thmtheorem10): when a single safe actionu⋆u^\{\\star\}already does well, the additiveR​G/\(W​T\)RG/\(W\\sqrt\{T\}\)term vanishes faster than the worst\-caseO​\(1/T\)O\(1/\\sqrt\{T\}\)\.

![Refer to caption](https://arxiv.org/html/2607.27626v1/x3.png)Figure 4:Margin\-safe robustness to execution noise \(N=4N\\\!=\\\!4,T=400T\\\!=\\\!400,55seeds per cell,8×88\\\!\\times\\\!8grid\)\. \(a\) Empirical miss rate over\(ξ,ε\)\(\\xi,\\varepsilon\); cyan line isξ=L¯​ε\\xi=\\bar\{L\}\\,\\varepsilonwithL¯≈1\.49\\bar\{L\}\\approx 1\.49\. Every\(ξ,ε\)\(\\xi,\\varepsilon\)above the line has miss rate exactly zero\. \(b\) Slices over margin; \(c\) slices over noise\.*Margin\-safe robustness\.*We computext∈𝒦tξx\_\{t\}\\in\\mathcal\{K\}\_\{t\}^\{\\xi\}but executex^t=ΠΔN​\(xt\+ε​nt\)\\hat\{x\}\_\{t\}=\\Pi\_\{\\Delta\_\{N\}\}\(x\_\{t\}\+\\varepsilon n\_\{t\}\)withntn\_\{t\}unit\-norm Gaussian, on a tight\-channel construction \(safe\-column0\.150\.15,D=\(10,10,10,10\)D=\(10,10,10,10\)\)\. Sweeping\(ξ,ε\)\(\\xi,\\varepsilon\)on an8×88\\\!\\times\\\!8grid \(6464cells,55seeds,T=400T=400\), Fig\.[4](https://arxiv.org/html/2607.27626#S6.F4)\(a\) reveals a sharp zero\-miss region right ofξ=L¯​ε\\xi=\\bar\{L\}\\varepsilonwithL¯≈1\.49\\bar\{L\}\\approx 1\.49the trace\-averaged Lipschitz constant of Thm\.[5](https://arxiv.org/html/2607.27626#Thmtheorem5)\. Without margin, evenε=0\.005\\varepsilon=0\.005drives miss rate to47%47\\%; withξ≥L¯​ε\\xi\\geq\\bar\{L\}\\varepsilonevery cell achieves zero miss rate, matching the theoretical boundary to within one grid cell\.

Three takeaways: \(i\) the hard projection is the only mechanism tested thateliminates modeled fluid\-state misses on every simulated trace, while long\-term VQ still violates1\.65%1\.65\\%of slots \(Prop\.[1](https://arxiv.org/html/2607.27626#Thmproposition1)\); \(ii\) the empirical regret slope sits well below1/21/2, suggesting the shield is an implicit regularizer in the active regime and that the constants in Thm\.[1](https://arxiv.org/html/2607.27626#Thmtheorem1)are not tight on benign traces; \(iii\)ξ≥L​ε\\xi\\geq L\\varepsilonaligns with the empirical phase boundary to within one grid cell, validating Thm\.[5](https://arxiv.org/html/2607.27626#Thmtheorem5)as a deployable design rule that converts numerical and physical noise budgets directly into a margin shrinkage\. The cost gap20,075/7,950≈2\.5320\{,\}075/7\{,\}950\\approx 2\.53is the price offluid\-trajectory safety, well within the deadline\-induced boundρD=∑iwi​Di/W=7\.5\\rho\_\{D\}=\\sum\_\{i\}w\_\{i\}D\_\{i\}/W=7\.5of Thm\.[9](https://arxiv.org/html/2607.27626#Thmtheorem9)\.

## VIIConclusion

We presented OCO\-PAoI\-Hard, a causal online scheduler that deliverszero modeled\-state peak\-AoI violationandO​\(T\)O\(\\sqrt\{T\}\)regret against adversarial channel and arrival sequences,conditional on the encountered safe sets remaining non\-empty\.This guarantee concerns the modeled AoI state; packet\-level safety requires stronger service assumptions\.The framework rests on a structural reduction that recasts the per\-sensor peak\-AoI deadline as an affine half\-space constraintCt​x≥θtC\_\{t\}x\\geq\\theta\_\{t\}on the fractionalresource\-allocation vector: one Euclidean projection onto the current\-slot safe set acts as amodeled\-statesafety shield, while the gradient step preserves theT\\sqrt\{T\}no\-regret rate\. Closed\-form static and dynamic regret bounds, a matching minimax lower bound, margin and approximate\-projection theorems, and two competitive\-ratio statements together cover every operating mode, and experiments on a multi\-sensor adversarial trap channel confirmzero modeled fluid\-state deadline violations, sublinear empirical regret, and a margin\-noise phase boundary matching the closed\-form prediction to within one grid cell\. Packet\-level rounding, multi\-cell coordination, and downstream control\-loop stability are natural next directions\.

## References

- \[1\]3GPP\(2025\-10\)Study on scenarios and requirements for next generation access technologies\.Technical reportTechnical ReportTR 38\.913 V19\.0\.0,3rd Generation Partnership Project\.External Links:[Link](https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2996)Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p1.3),[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[2\]M\. A\. Abd\-Elmagid, N\. Pappas, and H\. S\. Dhillon\(2019\)On the role of age of information in the internet of things\.IEEE Communications Magazine57\(12\),pp\. 72–77\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[3\]J\. Achiam, D\. Held, A\. Tamar, and P\. Abbeel\(2017\)Constrained policy optimization\.InInternational conference on machine learning,pp\. 22–31\.Cited by:[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[4\]M\. Alshiekh, R\. Bloem, R\. Ehlers, B\. Könighofer, S\. Niekum, and U\. Topcu\(2018\)Safe reinforcement learning via shielding\.InProceedings of the AAAI conference on artificial intelligence,Vol\.32\.Cited by:[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[5\]S\. Banerjee, R\. Bhattacharjee, and A\. Sinha\(2020\)Fundamental limits of age\-of\-information in stationary and non\-stationary environments\.In2020 IEEE International Symposium on Information Theory \(ISIT\),pp\. 1741–1746\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.7.4.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1),[§V\-K](https://arxiv.org/html/2607.27626#S5.SS11.p2.4)\.
- \[6\]A\. M\. Bedewy, Y\. Sun, S\. Kompella, and N\. B\. Shroff\(2021\)Optimal sampling and scheduling for timely status updates in multi\-source networks\.IEEE Transactions on Information Theory67\(6\),pp\. 4019–4034\.Cited by:[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[7\]M\. Bennis, M\. Debbah, and H\. V\. Poor\(2018\)Ultrareliable and low\-latency wireless communication: tail, risk, and scale\.Proceedings of the IEEE106\(10\),pp\. 1834–1853\.Cited by:[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[8\]G\. Bernat, A\. Burns, and A\. Llamosí\(2001\)Weakly hard real\-time systems\.IEEE transactions on Computers50\(4\),pp\. 308–321\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[9\]R\. Bhattacharjee and A\. Sinha\(2020\)Competitive algorithms for minimizing the maximum age\-of\-information\.ACM SIGMETRICS Performance Evaluation Review48\(2\),pp\. 6–8\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.7.4.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1),[§V\-K](https://arxiv.org/html/2607.27626#S5.SS11.p2.4)\.
- \[10\]X\. Cao and K\. R\. Liu\(2019\)Online convex optimization with time\-varying constraints and bandit feedback\.IEEE Transactions on automatic control64\(7\),pp\. 2665–2680\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[11\]E\. T\. Ceran, D\. Gündüz, and A\. György\(2021\)A reinforcement learning approach to age of information in multi\-user networks with harq\.IEEE Journal on Selected Areas in Communications39\(5\),pp\. 1412–1426\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.6.3.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[12\]T\. Chen, Q\. Ling, and G\. B\. Giannakis\(2017\)An online convex optimization approach to proactive network resource allocation\.IEEE Transactions on Signal Processing65\(24\),pp\. 6350–6364\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[13\]Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p1.3)\.
- \[14\]R\. I\. Davis and A\. Burns\(2011\)A survey of hard real\-time scheduling for multiprocessor systems\.ACM computing surveys \(CSUR\)43\(4\),pp\. 35:1–35:44\.Cited by:[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[15\]Z\. A\. Hammadeh, S\. Quinton, and R\. Ernst\(2019\)Weakly\-hard real\-time guarantees for earliest deadline first scheduling of independent tasks\.ACM Transactions on Embedded Computing Systems \(TECS\)18\(6\),pp\. 1–25\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[16\]E\. Hazan\(2016\)Introduction to online convex optimization\.Foundations and Trends in Optimization2\(3\-4\),pp\. 157–325\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[17\]Y\. Hsu\(2018\)Age of information: whittle index for scheduling stochastic arrivals\.In2018 IEEE International Symposium on Information Theory \(ISIT\),pp\. 2634–2638\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.5.2.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[18\]R\. Jenatton, J\. Huang, and C\. Archambeau\(2016\)Adaptive algorithms for online convex optimization with long\-term constraints\.InInternational Conference on Machine Learning,pp\. 402–411\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.4.2.3),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[19\]I\. Kadota, A\. Sinha, E\. Uysal\-Biyikoglu, R\. Singh, and E\. Modiano\(2019\)Scheduling policies for minimizing age of information in broadcast wireless networks\.IEEE/ACM Transactions on Networking26\(6\),pp\. 2637–2650\.Cited by:[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[20\]S\. Kaul, R\. Yates, and M\. Gruteser\(2012\)Real\-time status: how often should one update?\.In2012 Proceedings IEEE INFOCOM,pp\. 2731–2735\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p1.3),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[21\]S\. Leng and A\. Yener\(2019\)Age of information minimization for wireless ad hoc networks: a deep reinforcement learning approach\.In2019 IEEE Global Communications Conference \(GLOBECOM\),pp\. 1–6\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.6.3.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[22\]A\. Maatouk, S\. Kriouile, M\. Assaad, and A\. Ephremides\(2021\)On the optimality of the whittle’s index policy for minimizing the age of information\.IEEE Transactions on Wireless Communications20\(2\),pp\. 1263–1277\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.5.5.2.1),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[23\]M\. Mahdavi, R\. Jin, and T\. Yang\(2012\)Trading regret for efficiency: online convex optimization with long term constraints\.The Journal of Machine Learning Research13\(81\),pp\. 2503–2528\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[24\]S\. Paternain, L\. Chamon, M\. Calvo\-Fullana, and A\. Ribeiro\(2019\)Constrained reinforcement learning has zero duality gap\.Advances in Neural Information Processing Systems32\.Cited by:[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[25\]K\. Salamun, I\. Pavić, H\. Džapo, and I\. Čuljak\(2023\)Weakly hard real\-time model for control systems: a survey\.Sensors23\(10\),pp\. 4652\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-C](https://arxiv.org/html/2607.27626#S2.SS3.p1.5)\.
- \[26\]A\. Sinha and R\. Bhattacharjee\(2022\)Optimizing age\-of\-information in adversarial and stochastic environments\.IEEE Transactions on Information Theory68\(10\),pp\. 6860–6880\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[27\]Y\. Sun, E\. Uysal\-Biyikoglu, R\. D\. Yates, C\. E\. Koksal, and N\. B\. Shroff\(2017\)Update or wait: how to keep your data fresh\.IEEE Transactions on Information Theory63\(11\),pp\. 7492–7508\.Cited by:[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[28\]V\. Tripathi and E\. Modiano\(2024\)A whittle index approach to minimizing functions of age of information\.IEEE/ACM Transactions on Networking32\(6\),pp\. 5144–5158\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[29\]V\. Valls, G\. Iosifidis, D\. Leith, and L\. Tassiulas\(2020\)Online convex optimization with perturbed constraints: optimal rates against stronger benchmarks\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 2885–2895\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[30\]R\. D\. Yates, Y\. Sun, D\. R\. Brown, S\. K\. Kaul, E\. Modiano, and S\. Ulukus\(2021\)Age of information: an introduction and survey\.IEEE Journal on Selected Areas in Communications39\(5\),pp\. 1183–1210\.Cited by:[§I](https://arxiv.org/html/2607.27626#S1.p1.3),[§II\-A](https://arxiv.org/html/2607.27626#S2.SS1.p1.1)\.
- \[31\]X\. Yi, X\. Li, T\. Yang, L\. Xie, T\. Chai, and K\. Johansson\(2021\)Regret and cumulative constraint violation analysis for online convex optimization with long term constraints\.InInternational conference on machine learning,pp\. 11998–12008\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[32\]H\. Yu, M\. Neely, and X\. Wei\(2017\)Online convex optimization with stochastic constraints\.Advances in Neural Information Processing Systems30\.Cited by:[TABLE I](https://arxiv.org/html/2607.27626#S1.T1.4.2.3),[§I](https://arxiv.org/html/2607.27626#S1.p2.5),[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.
- \[33\]W\. Zhang, Y\. Zhang, and W\. Mo\(2026\)Noise\-adaptive high\-probability regret bounds for online convex optimization\.arXiv preprint arXiv:2606\.08028\.Note:Accepted to ECML\-PKDD 2026External Links:[Link](https://arxiv.org/abs/2606.08028)Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4.1)\.
- \[34\]W\. Zhang\(2026\)Dynamic regret with untrusted decision predictions via heterogeneous expert aggregation\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=LWsEyfdnp9)Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4.1)\.
- \[35\]W\. Zhang\(2026\)Multi\-constraint online convex optimization with adversarial constraints\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=3sLjLHCGzS)Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4.1)\.
- \[36\]M\. Zinkevich\(2003\)Online convex programming and generalized infinitesimal gradient ascent\.InProceedings of the 20th international conference on machine learning \(icml\-03\),pp\. 928–936\.Cited by:[§II\-B](https://arxiv.org/html/2607.27626#S2.SS2.p1.4)\.