PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure-Aware Online Optimization of the Age of Information with Unknown System Statistics

Yoshiaki Inoue, Michel Mandjes, Liron Ravner

arXiv:2610.13142v1cs.ITmath.OC

TL;DR

Selecting an update rate requires balancing freshness against congestion, yet the relevant system statistics may be unknown. The paper estimates finite-dimensional quantities in an analytical AoI-gradient representation and uses them to optimize online; across four incomplete-information settings, the algorithm converges to the optimal operating point and has smaller optimization error than the Kiefer–Wolfowitz benchmark at the same observation budget.

  • Problem

    Update-rate selection must balance stale information from infrequent updates against congestion and queueing delays from overly frequent updates, while system statistics may be unknown.

    Source: §I · p. 3

  • Method

    An online stochastic-approximation framework jointly estimates the finite-dimensional unknown quantities in an analytical AoI-gradient representation and optimizes the update rate from observations.

    Source: §I · p. 3, §III · p. 13

  • Results

    Across four incomplete-information settings, the algorithm converges to the optimal operating point and achieves substantially smaller optimization error than the Kiefer–Wolfowitz benchmark at the same observation budget.

    Source: §VI · p. 36

  • Takeaways & Limitations

    The results show that exploiting queueing structure can improve the efficiency of online optimization in the considered settings.

    Source: §VI · p. 36

    The approach is scoped to systems with an analytical AoI-gradient representation whose finite-dimensional unknown quantities can be estimated from operational observations.

    Source: §I · p. 3

Abstract

from arXiv · show

Timely information dissemination is essential in modern communication systems, where low informational latency is critical for networked control, monitoring, and real-time decision-making. The Age of Information (AoI) has emerged as a fundamental metric for quantifying information freshness at the receiver. A key challenge in AoI optimization is selecting the update generation rate: infrequent updates lead to stale information, whereas overly frequent updates increase queueing delays. We develop a structure-aware, data-driven framework for adaptive AoI optimization modeled as single-server queues with unknown system statistics. Our key idea is to exploit analytical representations of the AoI gradient, which depend on a finite-dimensional collection of system quantities that can be estimated from observations collected during system operation. This reduces the online learning problem to estimating the quantities required by the gradient, rather than learning the AoI objective as a black box. We propose an online stochastic approximation algorithm that jointly estimates these quantities and optimizes the update generation rate. We prove almost sure convergence of the algorithm to the optimal update generation rate under mild regularity and moment conditions, despite the temporal dependence induced by the underlying queueing process. We demonstrate the framework in four representative incomplete-information settings, including FCFS queues with unknown service characteristics or hidden background traffic, a preemptive LCFS system with partial observations, and a generate-at-will system with threshold waiting.

I. INTRODUCTION

AoI optimization must balance stale information from infrequent updates against congestion and queueing delays from overly frequent updates. The paper uses analytical AoI-gradient structure to optimize update rates from observations despite unknown system statistics.

I. INTRODUCTION

  • Known system statistics are often unavailable, complicating model-based selection of an update rate that balances freshness against congestion and queueing delays.The average AoI is typically minimized at an intermediate operating point.Source: §I · p. 2
  • The framework estimates finite-dimensional quantities in an analytical AoI-gradient representation instead of learning the objective or system dynamics as a black box.These quantities can be estimated from operational observations.Source: §I · pp. 3–4
  • An online stochastic-approximation algorithm jointly estimates gradient quantities and optimizes the update generation rate without prior knowledge of system parameters.It is designed for single-server queues with unknown parameters.Source: §I · p. 3
  • The analysis establishes almost-sure convergence to the optimal update rate while accounting for endogenous temporal dependence from the evolving queue.The queue state is coupled to the rate being optimized.Source: §I · pp. 3–4
  • Four incomplete-information settings illustrate the framework, including unknown service characteristics, hidden background traffic, partial observations, and threshold-based update policies.The examples span different queueing and observation structures.Source: §I · p. 4

II. MODEL, PROBLEM STATEMENT, LEADING EXAMPLES

The section introduces the general information-update system, formulates the structure-aware, data-driven AoI optimization problem, and gives four representative examples.

II. MODEL, PROBLEM STATEMENT, LEADING EXAMPLES

  • The section proceeds from the system model and optimization problem to four examples of the framework's application across queueing and observation settings.The passage identifies this section's contents without specifying the examples.Source: §II · p. 4

A. Information Update System

The information-update system consists of a sender, a server, and a receiver; packets are generated intermittently and forwarded to the monitor after service. The model tracks generation intervals and packet delays, distinguishing informative packets from those overtaken before delivery.

A. Information Update System

  • The system comprises a sensor, a communication channel or processor, and a monitor, with the server forwarding packets upon service completion.The sensor intermittently generates and transmits packets.Source: A. Information Update System · p. 5
  • Generation intervals G_n measure time between consecutive packet generations, while delays D_n measure each packet's time from generation to reception.Generation and reception times are defined recursively by α_n = α_(n−1) + G_n and β_n = α_n + D_n.Source: A. Information Update System · p. 5
  • A packet is informative only if it is received before every later-generated packet; packets overtaken by newer ones do not trigger monitor updates.The informative-packet set is defined by this reception-order condition.Source: A. Information Update System · p. 5

B. Problem Statement

The problem is to choose a controllable update-generation parameter to minimize long-run average AoI despite unknown delay dynamics. The framework assumes a known gradient structure whose finite-dimensional unknown quantities can be estimated from informative observations.

B. Problem Statement

  • The update intervals follow a parametric family indexed by λ, which serves as a control parameter that can vary more slowly than packet-generation and service dynamics.The delay distribution also depends on λ, but its exact dependence is not fully known.Source: B. Problem Statement · pp. 6–7
  • The objective is to minimize time-average AoI when the controller has limited information about how λ affects system delays.The receiver's available information includes monitor-side observations.Source: B. Problem Statement · p. 7
  • The AoI gradient is assumed to have a known functional form g with unknown system characteristics confined to a finite-dimensional, λ-dependent vector θ_λ.The vector is assumed consistently estimable from informative-packet observations.Source: B. Problem Statement · p. 7
  • The long-run objective combines average AoI with a generation-rate cost κ(λ), assumed non-decreasing and convex.A linear cost κ(λ) = Cλ is given as an example.Source: B. Problem Statement · p. 8
  • When κ is differentiable, the gradient contribution from the generation cost is known, leaving the unknown component confined to θ_λ.The structural representation yields the gradient of the stationary long-run objective.Source: B. Problem Statement · p. 8

C. Examples

The examples show how an analytical AoI-gradient representation can remain usable when service statistics or traffic are unknown and observations are incomplete. Across the settings, the required gradient inputs can be estimated from operational observations.

Example 1: FCFS dedicated channel with unknown service-time distribution

  • In the dedicated FCFS queue, service times are recoverable from arrival and departure observations, allowing the gradient’s finite-dimensional inputs to be estimated despite an unknown service-time distribution.The example assumes E[H2] < ∞ and establishes convergence under stronger stated moment and stability conditions.Source: C. Examples · p. 9

Example 2: FCFS with background sources of unknown generation rate

  • With hidden Poisson background traffic and known service distribution, PASTA makes tagged-packet delays informative about the combined arrival rate, yielding an estimating equation for the unknown background rate.The background stream’s arrivals and departures are not observed.Source: C. Examples · p. 10

Example 3: Preemptive LCFS system with unknown service-time distribution

  • In the preemptive LCFS queue, successful-packet service times are generally biased observations, yet the relevant AoI-gradient quantities remain estimable from informative observations.The model discards an older packet when a new one arrives during service.Source: C. Examples · p. 11

Example 4: Generate-at-will system with threshold waiting

  • For generate-at-will with threshold waiting, the gradient’s finite-dimensional parameter vector is estimable from observed inter-generation times and delays of informative packets.The source uses ACK signals to access server idle/busy state and generates only after the previous packet is delivered.Source: C. Examples · pp. 11–12

III. PROPOSED METHOD AND ITS CONVERGENCE

The method estimates the finite-dimensional quantities in an analytical AoI-gradient representation from informative packets, then uses that estimate to update the generation rate. Despite queue-induced temporal dependence, the algorithm converges almost surely to the optimal rate under the stated assumptions.

Algorithm

  • The algorithm holds the rate fixed during each decision interval, estimates the gradient’s structural parameter vector from informative packets, and updates the rate using the resulting gradient estimate.Projection keeps iterates feasible; diminishing step sizes and increasing sample sizes control estimation error.Source: §III · pp. 13–14

Convergence analysis

  • Queue-generated observations are temporally dependent and coupled to the current rate, so the analysis requires a uniform mean squared error condition for the parameter estimator.Applying the nonlinear gradient function to an estimated parameter can also make the gradient estimate biased.Source: §III · pp. 14–15

Convergence result

  • Under Assumption 1 and the specified step-size and sample-size sequences with β > 2(1 − α), the update rates converge almost surely to the minimizer of the objective.The proof uses the estimator’s mean squared error bound to control bias and variance in the stochastic approximation.Source: §III · pp. 15–16

IV. APPLICATION OF THE FRAMEWORK TO EXAMPLES 1–4

The section details implementations of the framework for Examples 1–4, addressing practical and theoretical aspects and verifying the assumptions needed for convergence.

Application of the framework

  • The framework is implemented across Examples 1–4, with the section emphasizing practical and theoretical implementation details.The discussion focuses particularly on checking the assumptions required for the preceding convergence result.Source: §IV · p. 18
  • For the four settings, the section’s stated task is to verify the convergence assumptions required by the proposed procedure.The passage describes the section’s scope rather than reporting numerical outcomes.Source: §IV · p. 18
  • The applications cover both practical implementation and theoretical considerations across the four examples.The supplied passage does not specify individual implementation procedures or results.Source: §IV · p. 18

A. Example 1: FCFS dedicated channel with unknown service-time distribution

The applications instantiate the framework across four incomplete-information queueing settings and state conditions under which its convergence result applies. The numerical-study section outlines experiments and a model-free benchmark comparison.

A. Example 1: FCFS dedicated channel with unknown service-time distribution

  • In the dedicated FCFS example, service times are directly observable from arrival and departure processes, enabling estimation of the gradient inputs despite unknown service statistics.The section assumes a finite second moment for the mean AoI and introduces a truncated estimation step for convergence analysis.Source: Appendix A · p. 18, A. Example 1: FCFS dedicated channel… · p. 18

Appendix A.

  • Under the stated stability and fourth-moment conditions, the dedicated FCFS example’s online update rates converge almost surely to the optimal rate.The service-time distribution is unknown, but service times can be reconstructed from observed arrivals and departures.Source: Appendix A · pp. 18–19

B. Example 2: FCFS with background sources of unknown generation rate

  • For FCFS with hidden background arrivals, tagged-packet delays provide an estimating equation for the background rate; convergence is stated under a load margin and finite second service-time moment.The delay identity follows because a Poisson-arriving tagged packet sees stationary workload by PASTA.Source: B. Example 2: FCFS with background… · pp. 21, 23

C. Example 3: Preemptive LCFS System with unknown service-time distribution

  • In the preemptive LCFS example, observations of successfully received packets support the required gradient quantities, and convergence follows under the stated parameter-space and moment conditions.The passage notes continuous differentiability in the parameter when its first component is bounded away from zero.Source: C. Example 3: Preemptive LCFS System… · p. 24

D. Example 4: Generate-at-will system with threshold waiting

  • For generate-at-will with threshold waiting, the parameter vector is estimated from empirical means, and the convergence result applies when the objective has a unique minimizer and the stated regularity conditions hold.The service-time distribution is assumed absolutely continuous for the displayed gradient representation.Source: D. Example 4: Generate-at-will system… · pp. 24–25

V. NUMERICAL STUDY

  • The numerical study evaluates the framework on Examples 1–4 and plans a comparison against a model-free Kiefer–Wolfowitz benchmark, alongside analyses of variability, stability, uncertainty, and stopping.The supplied passage outlines the study but reports no numerical outcomes.Source: §V · p. 25

A. Experimental setup

The experiments assess rate trajectories and estimation error, objective gap, realized time-average cost, and consumed budget. They use normalized service-time families and specified step-size, projection, and cost settings.

A. Experimental setup

  • Performance is tracked through rate trajectories and mean squared error, objective gap, realized time-average cost, and consumed budget measured by informative packets or elapsed time.Methods are compared against budget rather than iteration count because they may consume different numbers of samples per iteration.Source: A. Experimental setup · p. 25
  • Service-time families are normalized to E[H] = 1, making the stability condition in Examples 1 and 2 λtot < 1.The squared coefficient of variation determines the relevant shape parameter within each family.Source: A. Experimental setup · pp. 25–26, Table I · p. 26
  • The proposed method uses a diminishing step size scaled by local objective curvature, with the step-size constant calibrated using the unknown-parameter optimum.The calibration quantity is unavailable to the algorithm and is used only in the numerical experiments.Source: A. Experimental setup · p. 26
  • Examples 1, 2, and 4 use zero generation cost, while Example 3 uses κ(λ) = 0.25 λ because its AoI otherwise decreases monotonically with λ.Example-specific projection intervals contain the optima while avoiding steep gradients near stability boundaries; Example 2's burn packets count toward both budget and realized cost.Source: A. Experimental setup · pp. 26–27

B. Convergence across the four examples

Across four distinct examples, the proposed algorithm converges near the optimal rate under a common tuning rule. The optimal rates differ by model, while the normalized trajectories have comparable shapes.

B. Convergence across the four examples

  • The optimal rates range from approximately 0.28 in Example 2 to 2.07 in Example 3, reflecting differences between the underlying models rather than the optimization procedure.The normalized trajectories have comparable shapes despite substantial differences in objective curvature.Source: B. Convergence across the four examples · pp. 27–28
  • In Example 2, the background-rate estimate converges to its true value as the generation rate approaches λ∗, although the estimate can remain noisy after optimization has essentially converged.The feasible upper rate limit is learned implicitly, and accurate pointwise estimation of λbg is not necessary for effective optimization.Source: B. Convergence across the four examples · pp. 27–28
  • All four terminal iterates are within 1.9% of λ∗, and the common tuning rule yields accurate solutions across substantially different queueing models and objective scales.Figure 2 places the estimated rates, normalized by λ∗, on a common axis.Source: B. Convergence across the four examples · p. 27, Figure 2 · p. 28

C. Effect of service-time variability

Service-time variability changes the optimal operating rate, while the algorithm remains effective across tested service distributions. The stability experiments show that data-driven safeguards can restore convergence in an illustrative case and that the background-rate estimator can signal instability.

C. Effect of service-time variability

  • Across four service-time families, iterates reach the vicinity of λ∗ within a few iterations; for six distributions with E[H] = 1 and c2 = 4, λ∗ varies by less than 1% while the optimal objective varies by about 7%.Figure 4 shows the convergence behavior across service-time families; the two c2 = 4 distributions with different shapes have nearly identical optimal rates.Source: Figure 4 · p. 29, C. Effect of service-time variability · p. 30
  • The optimal rate decreases from λ∗≈0.629 for deterministic service to λ∗≈0.531 for exponential service and λ∗≈0.404 for distributions with c2 = 4.In the deterministic case, timestamps recover service times exactly, so the method reduces to exact projected gradient descent; other cases include estimation error.Source: C. Effect of service-time variability · p. 30

D. Stability and incomplete-information safeguards

  • With an unobserved background rate, Z-estimator saturation signals instability, but a larger stability margin may trigger unnecessarily close to the stability boundary.Beyond the boundary, the empirical transform tends toward zero over increasingly long observations, pushing the estimated root toward its parameter-space endpoint.Source: D. Stability and… · pp. 31–32
  • When λmaxE[H] = 1.5 > 1, fixed truncation converges to a perturbed stationary point, while either data-driven safeguard restores convergence to λ∗.Both safeguards are triggered only a small number of times; these results are illustrative and do not establish a convergence proof for the safeguarded variants.Source: D. Stability and… · p. 31, Figure 5 · p. 32

E. Statistical uncertainty and stopping

The section uses delta-method confidence intervals to quantify gradient uncertainty and approximate optimality, then examines their coverage and the cost of certified stopping. The intervals shrink at the parametric rate, but their coverage depends on service-time moment conditions.

Statistical uncertainty and stopping

  • For service-time families with E[H^4] < ∞, the confidence bands have close to nominal 95% coverage and contract at the parametric rate; coverage deteriorates for P2.5, where E[H^4] = ∞.For P2.5, nominal n^-1/2 band widths can substantially understate actual uncertainty when the delta-method moment condition fails.Source: E. Statistical uncertainty and stopping · pp. 32–33
  • Dividing a confidence-interval half-width by local curvature µ gives an approximate confidence region for λ∗, and the iterates settle within the shrinking bands.The intervals use a delta-method construction that requires E[H^4] < ∞.Source: E. Statistical uncertainty and stopping · p. 32, Figure 6 · p. 33
  • Example 3's bounded estimator inputs have finite moments, while Example 1's sample second moment of H has infinite variance; Table II illustrates the scaled-variance difference from censoring.The passage identifies robustness through censoring but does not provide table cell values.Source: E. Statistical uncertainty and stopping · pp. 32–33, Table II · p. 33
  • Stopping when the interval for g + κ′ lies inside [−ηµ, ηµ] approximately certifies |λ⟨k⟩−λ∗| ≲η under the local-curvature approximation.This is a statistical stopping rule based on the gradient-plus-cost derivative interval.Source: E. Statistical uncertainty and stopping · pp. 33–34
  • At one iteration, accuracy η requires O(η^-2) samples, while linearly increasing per-iteration sample sizes make cumulative cost grow substantially faster.Very precise statistical certification can therefore cost substantially more than finding a moderately accurate solution.Source: E. Statistical uncertainty and stopping · p. 34, Table III · p. 34

F. Comparison with a model-free reference method

The section compares the proposed structure-aware optimizer with the Kiefer–Wolfowitz model-free method at equal packet budgets and presents an error bound and delta-method intervals for the background-rate estimator. The intervals rely on exact service-time recovery and asymptotic normality under a fourth-moment condition.

F. Comparison with a model-free reference method

  • Kiefer–Wolfowitz [11] estimates gradients by splitting informative packets between two perturbed rates, whereas both methods use the same step-size and sample-size sequences and cumulative packet budget.The perturbation width is tuned separately for each comparison over a fixed grid; deterministic service is excluded because the structural gradient estimator is exact there.Source: F. Comparison with a model-free… · pp. 34–35
  • Across four qualitatively different incomplete-information settings, the proposed algorithm achieves substantially smaller optimization error than the Kiefer–Wolfowitz benchmark at the same observation budget in the considered numerical settings.Figure 7 plots Example 1’s iterate mean squared error against packet budget over R = 60; Figure 8 plots Examples 2–4 over R = 50.Source: Figure 7 · p. 35, Figure 8 · p. 35, §VI · p. 36
  • The advantage varies with problem structure: it grows with service-time variability in Example 1, while Kiefer–Wolfowitz performs better in Example 3 but remains less accurate.Finite-difference estimation is particularly noisy near Example 2’s stability boundary, and Example 4’s objective is very flat near the optimum.Source: F. Comparison with a model-free… · pp. 34–35

PROOF OF LEMMAS IN SECTION IV

  • The proof bounds the background-rate estimator’s error using concavity and monotonicity, after identifying it as a Z-estimator truncated at zero.The bound applies to the empirical root when it is an interior solution.Source: PROOF OF LEMMAS IN SECTION IV · pp. 46–47

APPENDIX D DELTA-METHOD INTERVAL ESTIMATES FOR EXAMPLE 1

  • Exact service-time recovery by inverting the Lindley recursion makes the informative-packet sample i.i.d., with the parameter estimate formed from sample means.Here λ is fixed and n is the number of informative packets observed.Source: Appendix D · p. 47
  • Under E[H^4] < ∞, the multivariate central limit theorem and delta method yield intervals for the gradient and objective, with truncation asymptotically inactive.The objective interval uses a Jacobian whose last coordinate vanishes because Eλ[A] does not involve f ′.Source: Appendix D · pp. 47–48
Loading 2610.13142v1…