Optimal Sampling and Transmission Policy for Information Freshness in Gossip Networks

1

Optimal Sampling and Transmission Policy for Information Freshness in Gossip Networks

arXiv:2611.10952v1 [cs.IT] 7 Nov 2026

Irtiza Hasan, Graduate Student Member, IEEE, and Ahmed Arafa, Member, IEEE

Abstract—We study the optimal sampling and transmission policies for a transmitter communicating with n gossiping receivers with the objective of tracking a source’s status over time using a semantic freshness metric: Version Age of Information (VAoI). The transmitter observes the version changes in the source, and can acquire a new information version by paying a sampling cost. The receivers gossip, allowing information exchange among each other without direct transmission. Gossiping can save on transmission cost, but it may propagate stale version information, necessitating transmitter intervention. With imperfect communication links, we formulate an infinite horizon average cost Markov Decision Process (MDP) in order to jointly optimize receivers’ VAoIs, sampling and transmission costs in a time slotted fully connected (FC) gossip network. We first solve the MDP using Relative Value Iteration (RVI) algorithm. Then, we prove that the sampling decision has a threshold structure in the transmitter VAoI. Further, under reliable gossiping links, we show that transmission and idling has an VAoI-difference threshold structure with minimum VAoI activation. Numerical results obtained using RVI show that the optimal policy consistently outperforms natural baselines. These results characterize how source sampling, direct transmission, and receiver gossip should be jointly coordinated for cost-aware semantic freshness in gossip networks.

Semantic communication requires freshness metrics that capture meaningful content changes, since elapsed time metrics such as AoI are often insufficient from a semantic perspective. Version Age of Information (VAoI), introduced in [9], provides such a semantic freshness measure by tracking the number of meaningful source versions missed by a receiver. Equivalently, VAoI quantifies freshness through the receiver’s version lag relative to the source [10]. VAoI generalizes the Binary Freshness Metric (BFM) [11] and has been widely used in the freshness analysis of gossip networks.

I

Networked communication and control systems, and statusupdate systems in general, often contain local receiver-toreceiver communication links. These links create gossiping opportunities, allowing receivers to exchange information without requiring every update to pass through a central transmitter. Gossiping reduces dependence on direct transmissions from the transmitter because receivers can spread fresh versions among themselves. However, gossiping can only circulate information already available at the receivers. Thus, when the receiver network becomes stale, transmitter intervention is necessary. The transmitter can directly inject information into the receiver network by paying a transmission cost. If the transmitter itself is stale, it can sample the source to refresh its own version, but this incurs a sampling cost. When both the transmitter and the receiver network are relatively fresh, the transmitter may instead idle and allow receiver gossip to reduce local VAoI disparities without incurring a direct transmission cost.

The authors are with the Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC 28223 USA; e-mails: ihasan@charlotte.edu; aarafa@charlotte.edu. This work was supported by the U.S. National Science Foundation under Grant ECCS 21-46099.

In this work, we study a VAoI-based fully connected (FC) gossip network in which the transmitter observes source version changes but must decide when acquiring the current source version is worth the sampling cost. The transmitter can directly transmit its available version into the receiver network by paying a transmission cost, or it can idle and allow receivers to propagate information among themselves. This creates a coupled control problem in which sampling, direct transmission, and idling cannot be optimized independently. We formulate this problem as an infinite horizon averagecost Markov Decision Process (MDP) [12]. We prove that the optimal sampling decision has a threshold structure in the transmitter VAoI. We characterize the structure of direct transmission and idling under symmetric links, and prove a VAoI-difference threshold structure with minimum-VAoI activation policy. Numerical results validate the structural findings and compare the optimal policy against several baselines. The results show that jointly optimizing sampling, direct transmission, and idling provides significant gains over policies that use these mechanisms in a fixed or decoupled manner.

Index Terms—Information Freshness, Version Age of Information, Gossip Network, Markov Decision Process, Relative Value Iteration.

I. I NTRODUCTION NFORMATION freshness is central to robust and dependable performance in status-update systems such as sensor networks [1], connected and autonomous vehicles (CAVs) [2], and Internet-of-Things (IoT) networks [3], among others. Timely information updates are crucial for control, estimation, and decision making performance [4]. Traditionally, information freshness is measured using Age of Information (AoI) [5], which has become the most widely used metric for tracking timeliness in such systems [6]. However, AoI measures freshness through elapsed time after update generation, and therefore may penalize staleness even when the source content has not changed. This limitation is increasingly important as networked applications move toward goaloriented and semantic communication paradigms [7], with 6G systems expected to connect massive numbers of intelligent devices. Semantic communication calls for freshness metrics that reflect meaningful source changes, motivating a shift from purely time driven freshness measures [8].

2

A. Related Works Before the introduction of VAoI in gossip networks [9], AoI had already been considered in that area [13]. Subsequent works have shown that the topology of how nodes are connected in the network plays a central role in the freshness of any gossip network. Hierarchical organization, such as clustering of nodes, also impacts freshness, as shown in [14], where the grouping of receivers and the hierarchical structure affect the freshness scaling behavior. Further, rate-changing gossip in clustered networks is shown to have an effect on freshness as shown in [15]. Network topology and other topological effects on freshness have been investigated in [16]–[18].The results indicate that network structure and connectivity among the nodes impact the dissemination of fresh information, and can be considered key aspects of freshness. Recent studies have considered other viewpoints of gossiping. Coded update dissemination is analyzed in [19], where memory and memoryless coding schemes were shown to influence the age of updates. Push-pull gossip protocols are investigated in [20], providing an additional alternative mechanism through which nodes can exchange information. Mobility of nodes has been studied in [21], [22], where node mobility and contact opportunities affect the flow of fresh updates. A survey of closely related works can be found in [23]. These works offer insight into information freshness in gossip networks. They primarily analyze systems with specific topologies, gossiping dynamics, and processes. They do not directly address how to optimally control freshness in the network. Policy optimization for freshness in gossip networks has only recently begun to receive attention. In [24], age-aware multiple access is studied, showing that update scheduling can be designed with freshness considerations. Opportunistic gossiping in dense networks is investigated in [25], where the update process is adapted to exploit favorable dissemination opportunities. A learning based approach for improving fairness in sparse gossip networks is proposed in [26], highlighting the role of adaptive policies. More closely related to our setting, [27] formulates a VAoI optimization problem in a unidirectional ring network with an energy-harvesting sensor and an aggregator, and shows that the optimal update policy has a threshold structure. Our prior works [28], [29] study versions of the problem for two gossiping receivers. These works show that freshness in gossip networks can be improved not only by changing topology or gossip rates, but also by formulating and optimizing a control policy. Outside the context of gossip networks, the structure of optimal policies for status updating has been well studied. Prior works have characterized policy structures in routing, energy harvesting, wireless broadcasting, and federated learning [30]– [42]. These results show that optimal freshness control often has exploitable structure. Such structural characterizations provide analytical insight into why certain update actions are optimal in different regions of the state space. Additionally, structural results help reduce the effective complexity of policy search by replacing the full search space with a smaller family of structured policies. Beyond the analytical simplification that structural analy-

sis can offer, these properties are useful for learning-based control. Reinforcement learning methods for large MDPs can suffer from high sample complexity. Structure-aware learning methods address this issue by embedding structure into the learning architecture and policy class [43]–[49], thereby ensuring faster and more accurate learning. These works motivate the study of structural optimality as a practical tool for scalable policy computation, which can speed up learning and make online and real-time implementation more practical. B. Contributions Gossiping can significantly improve freshness by allowing receivers to exchange locally available information. However, gossiping alone cannot create new source versions. It can only redistribute versions that are already present in the receiver network. Thus, when the receiver network becomes stale, transmitter intervention is necessary. The transmitter must decide whether to sample the source (with a sampling cost), transmit its available version to a receiver (with a transmission cost), or idle and allow receiver gossip to reduce local VAoI disparities. This creates a fundamental control tradeoff between semantic freshness and operation costs. In this paper, we study this tradeoff under the Version Age of Information (VAoI) metric. Unlike models in which the transmitter always has the freshest source version, we explicitly account for transmitter staleness and costly source sampling. The resulting problem asks: When to sample the source, whom to serve directly, and when to idle so that gossip can improve freshness in a cost-effective manner? The main contributions are summarized as follows. • We formulate a VAoI-based freshness control problem for a general n-receiver fully connected (FC) gossip network with costly source sampling and lossy direct transmission. • We cast the problem as an infinite-horizon average-cost Markov Decision Process (MDP), where the objective is to minimize the long-term receiver VAoI together with sampling and transmission costs. We compute the optimal policy using Relative Value Iteration (RVI). • We prove that the optimal sampling decision has a threshold structure in the transmitter VAoI. • We characterize the structure of the transmission and idling actions under symmetric links. We prove that an optimal direct transmission targets a receiver with the largest VAoI, and we establish a VAoI-difference threshold structure for the transmission versus idling decision. • We numerically evaluate the optimal policy against natural baseline policies to illustrate the threshold structures and show the benefit of jointly optimizing sampling, direct transmission, and idling. II. S YSTEM M ODEL We consider a time-slotted system indexed by t ∈ {0, 1, 2, . . .}, consisting of n fully connected (FC) gossiping receivers, denoted by RX1 , . . . , RXn . The source evolves over time and generates new information. A system with n = 6 is

3

shown in Fig. 1. Let X(t) denote the source information at slot t. The source content, which we denote as the version of the information, remains unchanged from one slot to the next with probability 1 − α and changes with probability α, independently across slots. Let δ ∈ {0, 1} denote the source version increment in a slot, where P(δ = 1) = α,

P(δ = 0) = 1 − α.

A. System State Let Ns (t) denote the source version at the beginning of slot t, let Ntx (t) denote the source version at the transmitter, and let Ni (t) denote the source version at receiver i. The version age of x ∈ {tx, 1, . . . , n} is defined as (2)

Accordingly, vx (t) = 0 means that node x has the current source version, while vx (t) > 0 means that node x is behind the current source information version by vx (t) versions. The system state is the VAoI of the transmitter and the n receiver nodes:
s(t) = vtx (t), v1 (t), . . . , vn (t) . (3) Since every receiver information version comes from the transmitter or from another receiver that received information from the transmitter, the transmitter cannot be “older” than any receiver. Hence, the state space satisfies 0 ≤ vtx (t) ≤ vi (t), ∀i ∈ {1, . . . , n}. For numerical computation, we use a finite truncation parameter Vmax and define the state space as: S = {(vtx , v1 , . . . , vn ) : 0 ≤ vtx ≤ vi ≤ Vmax , i = 1, . . . , n}.

Transmitter

(1)

Here, δ = 1 corresponds to the generation of a new source version, while δ = 0 corresponds to no source version generation at the beginning of a slot. The transmitter is aware of source version changes, and can therefore track the version ages of all nodes [27]. However, observing that the source version has changed, does not give the transmitter the current source content. To obtain the current information version, the transmitter has to sample and pay a sampling cost. The transmitter can transmit its available version to one receiver, or remain idle and allow receivers to exchange their available versions through gossiping. We assume that receivers in the FC gossip network send ACK/NACK feedback after each direct transmission attempt from the transmitter or any successful gossiping between them. If a receiver obtains multiple successful gossip updates in the same slot, it keeps the freshest received version, i.e., the one with the minimum VAoI, and gives feedback using ACK to the transmitter about its change in VAoI. Therefore, the transmitter can track the receiver VAoIs, and has perfect knowledge of the system state, which we describe in the following section.

vx (t) ≜ Ns (t) − Nx (t).

Source

(4)

At the beginning of each slot, when the system is in state s(t) = (vtx , v1 , . . . , vn ), the transmitter chooses an action based on the state. During the slot, the source may generate

Receivers

Fig. 1. System model showing a source, transmitter and a fully connected (FC) gossip network with n = 6.

a new information version. After the action is selected, the source evolution is realized, producing the intermediate VAoIs: ṽtx = (vtx + δ) ∧ Vmax , ṽi = (vi + δ) ∧ Vmax ,

(5)

i = 1, . . . , n,

(6)

where a ∧ b = min{a, b}. The system state after the source evolution becomes
s̃(t) = ṽtx , ṽ1 , . . . , ṽn . (7) The chosen action is applied to this intermediate state. Each time slot t proceeds as follows. First, the transmitter observes the current state s(t) and selects an action u(t) ∈ A. Next, the source evolution δ(t) ∈ {0, 1} is realized, producing the intermediate VAoIs (ṽtx , ṽ1 , . . . , ṽn ). The chosen action u(t) is then applied to this intermediate state. Finally, communication links’ reliability outcomes determine the next state s(t+1) and ACK/NACK feedbacks are sent. B. Actions and Transitions The transmitter chooses one action from the action set at the beginning of each time slot: A = {0, 1, . . . , n, n + 1}. The actions are defined as follows:   0, idle,   u(t) = i, transmit to receiver i,    n + 1, sample source.

(8)

i ∈ {1, . . . , n}, (9)

If the transmitter chooses action u(t) = i, where i ∈ {1, . . . , n}, then it attempts to send its currently available version to receiver i. The direct link to receiver i succeeds with probability pi and fails with probability 1 − pi . If the transmission succeeds, receiver i adopts the transmitter’s version. Therefore, its VAoI after the current slot becomes vi (t+1) = ṽtx . All other receivers remain at their intermediate VAoIs. Thus, under action u(t) = i, ( (ṽtx , ṽ1 , . . . , ṽi−1 , ṽtx , ṽi+1 , . . . , ṽn ), w.p. pi , s(t + 1) = (ṽtx , ṽ1 , . . . , ṽn ), w.p. 1 − pi . (10) A successful transmission to receiver i resets it to the transmitter VAoI ṽtx . Receiver i becomes fully fresh only when the

4

transmitter itself is fresh, i.e., when ṽtx = 0. We assume that direct transmission and RX gossip share the same communication resources. Hence, gossip occurs only in slots without a direct transmission. Only when the transmitter idles or samples, the receivers can gossip. When this is the case, in those time slots, each receiver can transmit to one other receiver. However, a receiver may receive gossip from multiple other receivers in the same slot. Let rj (t) ∈ {1, . . . , n} \ {j} denote the receiver selected by receiver j as its gossip destination. Each receiver selects its target uniformly at random: 1 , i ̸= j. (11) P(rj (t) = i) = n−1 The gossip attempt from j to i succeeds with probability pv,ji , where 0 < pv,ji < 1, ∀ j. Let Gji (t) denote the event that receiver j successfully gossips its version to receiver i in slot t. For each receiver i, the set of successful incoming gossip senders is Gi (t) = {j ̸= i : rj (t) = i and Gji (t) occurs}.

(12)

Receiver i keeps the freshest version among all successfully received gossip versions and its own information version. Since smaller VAoI means fresher information, the receiver update rule is:   vi (t + 1) = min ṽi , min ṽj , i = 1, . . . , n, (13) j∈Gi (t)

Therefore, if receiver i receives no successful gossip packet, then vi (t + 1) = ṽi . Under the idle action u(t) = 0, the transmitter does not sample, and hence vtx (t+1) = ṽtx . The receiver VAoIs change based on gossiping. Therefore,using (13), the state becomes:  s(t + 1) = ṽtx , min{ṽ1 , min ṽj }, . . . , j∈G1 (t)  min{ṽn , min ṽj } . (14) j∈Gn (t)

If the transmitter chooses the sampling action u(t) = n + 1, the transmitter VAoI resets to zero, vtx (t + 1) = 0. As stated previously, during the same slot, receivers are allowed to gossip. Thus, under sampling using (13), the next state is  s(t + 1) = 0, min{ṽ1 , min ṽj }, . . . , j∈G1 (t)  min{ṽn , min ṽj } . (15)

There is no cost incurred when idling (u = 0). The transmitter uses the channel statistics knowledge (i.e., pi ’s, and pij ’s) and defines the system cost at a given time slot as the expected sum of all RXs’ VAoIs at the next time slot plus the action dependent cost (if any). Therefore, for state s and action u, the immediate cost is: " n # X c(s, u) = E vi (t + 1) s(t) = s, u(t) = u + C(u). i=1

(17)

D. Problem Formulation We now formulate the infinite-horizon average cost MDP. Our objective is to find a stationary policy π : S → A that maps each state to an action and optimizes the long term average system cost. For a given policy π, the long-term average cost starting from s(0) = s is "T −1 # 1 π X c(s(t), π(s(t))) s(0) = s . ρ (s) = lim sup E T →∞ T t=0 (18) π

The objective is to find a stationary policy minimizing this cost, i.e., to evaluate: π ⋆ ∈ arg min ρπ (s). π

(19)

In subsequent sections, we show that the feasible state space is closed and that, under 0 < α < 1, 0 < pi < 1, ∀i, and 0 < pv,ji < 1, ∀i and ∀j ̸= i, the MDP is communicating. Therefore, by standard finite-state averagecost MDP results, the optimal average cost is independent of the initial feasible state and the average-cost optimality equation admits a solution [50]. Let ρ⋆ denote the optimal average cost and let U (s) denote the relative value function. The average-cost Bellman optimality equation is ( ) ρ⋆ + U (s) = min c(s, u) + E [U (s′ ) | s, u] , u∈A

s ∈ S, (20)

j∈Gn (t)

Receivers benefit from sampling in later time slots, after the transmitter subsequently transmits its newly sampled version, or through gossiping after that information version enters the network. C. Costs The costs partly depend on the transmitter action. Let Cs ≥ 0 denote the sampling cost and Ctx ≥ 0 denote the cost of transmission. The action-dependent part of the cost is   u = 0, 0, C(u) = Ctx , u ∈ {1, . . . , n}, (16)   Cs , u = n + 1.

where s′ denotes the next state induced by the source evolution, transmission outcome, and gossiping outcome under the state-action pair (s, u). We define the action value as Q(s, u) ≜ c(s, u) + E [U (s′ ) | s, u] .

(21)

Thus, an optimal stationary deterministic policy is obtained by π ⋆ (s) ∈ arg min Q(s, u). u∈A

(22)

We compute the optimal policy numerically using relative value iteration (RVI) [51], according to the steps detailed in Algorithm 1 and analyze its structural properties in the following sections.

5

Algorithm 1 Relative Value Iteration

Lemma 2 (Cost monotonicity). If s ⪯ s′ , then for every action u ∈ A, c(s, u) ≤ c(s′ , u).

1: Initialize: sref , ϵ, k = 0, and U (0) (s) = 0 for all s ∈ S. 2: repeat 3: for s ∈ S do " # P (k+1) ′ (k) ′ 4: Ū (s) = min c(s, u) + P (s |s, u)U (s ) . u∈A s′ ∈S U (k+1) (s) = Ū (k+1) (s) − Ū (k+1) (s

5: 6: end for 7: k ← k + 1. 8: until max U (k) (s) − U (k−1) (s) < ϵ

■

Proof. See Appendix D.

Proposition 3 (Relative Value Function Monotonicity). The relative value function U (s) is nondecreasing with respect to the state:

ref ).

s∈S

9: Set ρ(k) = Ū (k) (sref ). 10: Generate the deterministic policy " # P 11: π ⋆ (s) ∈ arg min c(s, u) + P (s′ |s, u)U (k) (s′ ) , u∈A

s ⪯ s′

12: Output: π ⋆ , U (k) , and ρ(k) .

U (k+1) (s) = T U (k) (s) − T U (k) (sref ),

III. P ROPERTIES OF THE M ARKOV D ECISION P ROCESS We first establish basic properties of the MDP for completeness. The first property shows that the state space is closed under all transition outcomes. The second property shows that the MDP is communicating. For two states s = (vtx , v1 , . . . , vn ) ′ , v1′ , . . . , vn′ ), we write s ⪯ s′ if and s′ = (vtx vi ≤ vi′ ,

i = 1, . . . , n.

(23)

Proposition 1 (Closure). If s(t) ∈ S, then s(t + 1) ∈ S, ∀u ∈ A and for all transition outcomes. Hence, the state space S is closed. ■

Proof. See Appendix A.

Proposition 2 (Communication). Assume 0 < α < 1, 0 < pi < 1, ∀i ∈ {1, . . . , n}, and 0 < pv,ji < 1, ∀j ̸= i. Then the MDP on S is communicating. ■

Proof. See Appendix B.

We next establish the properties of the relative value function that are used to prove the structure. IV. M ONOTONICITY OF THE R ELATIVE VALUE F UNCTION We establish monotonicity property of the relative value function. For a fixed action u, source increment δ, and transition outcome ω, let Fu,ω,δ (s),

Fu,ω,δ (s′ )

(24)

denote the next states generated from s and s′ under the same realization where s ⪯ s′ according to (23). Lemma 1 (Order preservation). For every fixed u ∈ A, δ ∈ {0, 1}, and transition outcome ω, the next-state map is orderpreserving, which means: s ⪯ s′

=⇒

Proof. See Appendix C.

Fu,ω,δ (s) ⪯ Fu,ω,δ (s′ ).

U (s) ≤ U (s′ ).

(26)

Proof. We prove the result using inductive hypothesis. Let U (k) denote the k-th RVI iterate and initialize U (0) (s) = 0, ∀s ∈ S. Thus, U (0) is nondecreasing. Assume U (k) is nondecreasing. The RVI update is

∀s ∈ S.

s′ ∈S

′ vtx ≤ vtx ,

=⇒

where sref is fixed and io n h T U (k) (s) = min c(s, u) + E U (k) (S) s, u . u∈A

(27)

(28)

The term T U (k) (sref ) is independent of s, so it does not affect monotonicity. Now let s ⪯ s′ and fix an action u ∈ A. For a fixed source increment δ and transition outcome ω, define S = Fu,ω,δ (s) and S ′ = Fu,ω,δ (s′ ). By Lemma 1, S ⪯ S′.

(29)

Since U (k) is nondecreasing, we have U (k) (S) ≤ U (k) (S ′ ).

(30)

This holds for every realization of δ and ω. Therefore, taking expectation over all transition outcomes gives h i h i E U (k) (S) s, u ≤ E U (k) (S ′ ) s′ , u . (31) By Lemma 2, c(s, u) ≤ c(s′ , u). Combining this with the previous inequality gives h i c(s, u) + E U (k) (S) s, u h i ≤ c(s′ , u) + E U (k) (S ′ ) s′ , u . (32) Since this inequality holds for every u ∈ A, taking the minimum over actions gives using (28), T U (k) (s) ≤ T U (k) (s′ ).

(33)

Therefore, by (27), U (k+1) (s) = T U (k) (s) − T U (k) (sref ) ≤ T U (k) (s′ ) − T U (k) (sref )

(25)

= U (k+1) (s′ ).

■

Thus, U (k+1) is nondecreasing. By induction, every RVI iterate is nondecreasing. Letting k → ∞, the normalized RVI iterates converge to the relative value function U . Hence,

Remark 1. The mapping Fu,ω,δ (·) denotes the next state under a fixed action u, fixed source evolution δ, and fixed realization of all link outcomes and gossip target selections, denoted by ω.

U (s) = lim U (k) (s) ≤ lim U (k) (s′ ) = U (s′ ). k→∞

k→∞

Therefore, s ⪯ s′ implies U (s) ≤ U (s′ ).

(34)

(35) ■

6

V. S AMPLING T HRESHOLD OF THE O PTIMAL P OLICY We first establish that the optimal sampling decision has a threshold structure in the transmitter VAoI vtx . For fixed receiver VAoIs, sampling becomes more attractive as the transmitter becomes more stale. In particular, once sampling is optimal at some vtx , it remains optimal for all larger feasible transmitter VAoIs. Theorem 1 (Sampling Threshold). For fixed receiver VAoIs, the optimal sampling decision is threshold-based in the transmitter VAoI vtx . Equivalently, if sampling is optimal at some feasible vtx , then it is also optimal for every larger feasible transmitter VAoI with the same receiver VAoIs. Proof. Fix receiver VAoIs (v1 , . . . , vn ) and consider two fea′ sible states s = (vtx , v1 , . . . , vn ) and s′ = (vtx , v1 , . . . , vn ) ′ ′ with vtx ≤ vtx , which gives s ⪯ s . First, we consider the sampling action u = n + 1. Under sampling, the transmitter VAoI is reset to zero (vtx = 0 and vtx′ = 0). Since the receiver VAoIs are identical in s and s′ (vi = vi′ for all i ∈ {1, 2, . . . , n}), the same source evolution and gossip outcome produce identical next states. Thus, Fn+1,ω,δ (s) = Fn+1,ω,δ (s′ ),

∀δ, ω.

By the preceding arguments in (40), the first term in ∆(vtx ) is independent of vtx , while by (43) the second term is nondecreasing in vtx . Therefore, ∆(vtx ) is nonincreasing in vtx . ′ If sampling is optimal at s, then ∆(vtx ) ≤ 0. Since vtx ≥ vtx and ∆(·) is nonincreasing in vtx , ′ ∆(vtx ) ≤ ∆(vtx ) ≤ 0.

(46)

Thus, Q(s′ , n + 1) ≤

min

Q(s′ , u),

u∈{0,1,...,n}

(47)

so sampling is optimal at s′ . This proves the threshold property. ■ Remark 2. Theorem 1 shows that, for every fixed receiver-VAoI vector (v1 , . . . , vn ), there exists a threshold τ (v1 , . . . , vn ) such that sampling is optimal for all feasible vtx ≥ τ (v1 , . . . , vn ). In states below the sampling threshold, the relevant decision is between direct transmission and idling. We study these decisions next.

(36) VI. O PTIMAL P OLICY FOR T RANSMISSION AND I DLING

Hence,

We now turn to the structure of the actions in the states below the sampling threshold. Once sampling is not selected, the transmitter has to decide whether to idle and allow gossip, Taking expectation over all transition outcomes gives or transmit its available versions to receivers. To obtain clean ′ ′ E [U (Fn+1,ω,δ (s)) | s, n + 1] = E [U (Fn+1,ω,δ (s )) | s , n + 1] . structural comparisons, we focus on the symmetric setting, (38) where all direct transmission links have same success probaMoreover, the immediate costs are identical because the ex- bility and all gossip links have the same success probability. pected next receiver VAoI sum is the same in both states and With these assumptions, for the rest of the paper, we assume the sampling cost is Cs in both cases. Hence by (17) , pi = p, ∀i and pv,ji = pv , ∀j ̸= i. Under symmetric links, receivers are statistically identical ′ c(s, n + 1) = c(s , n + 1). (39) apart from their VAoIs. If two states have the same transmitter Using the definition of Q(s, u) from (21), we obtain VAoI vtx and differ only because some receivers have exchanged their VAoI values, then the two states should have the ′ Q(s, n + 1) = Q(s , n + 1). (40) same relative value function. Mathematically, this exchange Now consider any non-sampling action u ∈ {0, 1, . . . , n}. is represented by a permutation of the receiver VAoIs. If By Lemma 2, c(s, u) ≤ c(s′ , u). Also, by Lemma 1 and s = (vtx , v1 , . . . , vn ) and σ is a permutation of {1, . . . , n}, Proposition 3, then the permuted state is defined as U (Fn+1,ω,δ (s)) = U (Fn+1,ω,δ (s′ )) ,

∀δ, ω.

(37)

U (Fu,ω,δ (s)) ≤ U (Fu,ω,δ (s′ )) ,

∀δ, ω.

(41)

σ(s) ≜ (vtx , vσ−1 (1) , . . . , vσ−1 (n) ).

(42)

Thus, in σ(s), the receiver in position i has the VAoI that belonged to receiver σ −1 (i) in s. Equivalently, the VAoI of receiver j in s is moved to receiver σ(j) in σ(s). We formalize this property next.

Taking expectation over all transition outcomes gives ′

′

E [U (Fu,ω,δ (s)) | s, u] ≤ E [U (Fu,ω,δ (s )) | s , u] .

Combining this with c(s, u) ≤ c(s′ , u) and using (21) gives: Q(s, u) ≤ Q(s′ , u),

u ∈ {0, 1, . . . , n}.

(43)

Q(s′ , u).

(44)

Hence, Q(s, u) ≤

min u∈{0,1,...,n}

min u∈{0,1,...,n}

For fixed receiver VAoIs, we define the sampling gap as a function of the transmitter VAoI, vtx :
∆(vtx ) ≜ Q (vtx , v1 , . . . , vn ), n + 1
(45) − min Q (v , v , . . . , v ), u . u∈{0,1,...,n}

tx

1

n

(48)

Proposition 4 (Permutation Invariance). Under symmetric direct and gossip links, the relative value function is invariant under any permutation of receiver VAoIs. That is, for any feasible state s ∈ S and any permutation σ of {1, . . . , n}, U (s) = U (σ(s)).

(49)

Proof. Let σ be any permutation of {1, . . . , n}. Since σ only permutes receiver VAoIs, σ(s) ∈ S where s ∈ S. The corresponding action permutation is σA (0) = 0, σA (n+1) = n+1, and σA (i) = σ(i) for i ∈ {1, . . . , n}. Thus, idling and

7

Therefore,

α = 0.2, p = 0.4, pv = 0.8, Ctx = 5.0, Cs = 10.0

U (k+1) (σ(s)) = T U (k) (σ(s)) − T U (k) (sref )

Idle Tx RX1 Tx RX2 Sample

= T U (k) (s) − T U (k) (sref ) =U

20.0 17.5

(57)

(s).

Thus, U (k+1) is permutation invariant. By induction, every RVI iterate is permutation invariant. Taking k → ∞ gives

15.0

vtx

12.5 10.0

U (σ(s)) = U (s),

7.5 5.0

for every feasible state s and every receiver permutation σ.

2.5 0.0 20.0 17.5 15.0 12.5 10.0 7.5 v 1

5.0

2.5

0.0 0.0

2.5

5.0

v2

sampling are unchanged, while a direct transmission to RXi is mapped to a direct transmission to RXσ(i) . We prove the result by induction on the RVI iterates. Initialize U (0) (s) = 0 for all s ∈ S. Then U (0) is permutation invariant. Assume that U (k) is permutation invariant, i.e., U (k) (s) = U (k) (σ(s)),

∀s ∈ S.

(50)

Similar to (21) we have, (k)

h i (s, u) ≜ c(s, u) + E U (k) (s′ ) s, u ,

(51)

where s′ denotes the next state generated from state s under action u. Under symmetric direct and gossip links, permuting receiver VAoIs does not change the immediate cost. Hence, for every s ∈ S and u ∈ A, c(s, u) = c(σ(s), σA (u)).

(52)

Moreover, if s′ is the next state generated from (s, u), then σ(s′ ) has the same distribution as the next state generated from (σ(s), σA (u)). Therefore, using the induction hypothesis, h i h i E U (k) (s′ ) s, u = E U (k) (σ(s′ )) s, u h i = E U (k) (s′ ) σ(s), σA (u) . (53) Combining this with (52) gives, Q(k) (s, u) = Q(k) (σ(s), σA (u)).

(54)

Since σA is a permutation of A, using the definition from (28), T U (k) (σ(s)) = min Q(k) (σ(s), σA (u)) u∈A (k)

= TU

(55)

Q(s, j) < Q(s, i).

(59)

Consequently, among direct transmissions, an optimal direct transmission targets a receiver in arg maxℓ∈{1,...,n} vℓ . Proof. Fix a state s = (vtx , v1 , . . . , vi , . . . , vj , . . . , vn ),

(60)

with receivers i and j satisfying vi < vj , where WLOG, we assume i < j. For a fixed source evolution δ, the intermediate state is s̃ = (ṽtx , ṽ1 , . . . , ṽi , . . . , ṽj , . . . , ṽn ).

(61)

Transmissions to RXi and RXj succeed with the same probability p. If the transmission fails, both actions lead to the same next state sfail (δ) = s̃. If RXi is served successfully, the next state is ssucc (δ) = (ṽtx , ṽ1 , . . . , ṽtx , . . . , ṽj , . . . , ṽn ). i If RXj is served successfully, the next state is ssucc (δ) = j (ṽtx , ṽ1 , . . . , ṽi , . . . , ṽtx , . . . , ṽn ). Let σ be the permutation that swaps receivers i and j and leaves all other receivers unchanged. Applying σ to ssucc (δ) gives, i σ(ssucc (δ)) = (ṽtx , ṽ1 , . . . , ṽj , . . . , ṽtx , . . . , ṽn ). i

(62)

Thus, ssucc (δ) and σ(ssucc (δ)) are identical in every coorj i dinate except RXi . In ssucc (δ), RXi has VAoI ṽi , whereas j in σ(ssucc (δ)), RX has VAoI ṽj . Since vi < vj , we have i i ṽi ≤ ṽj , and hence ssucc (δ) ⪯ σ(ssucc (δ)). j i

(63)

Using Proposition 3 and then Proposition 4, (64)

For transmission to RXi , we have, E [U (s′ ) | s, i, δ] = pU (ssucc (δ)) + (1 − p)U (sfail (δ)), (65) i

(s).

From (27), the RVI update is U (k+1) (s) = T U (k) (s) − T U (k) (sref ).

■

Proposition 5 (Serve-Oldest Receiver). For any state s = (vtx , v1 , . . . , vn ) ∈ S and any two receivers i, j such that vi < vj , transmitting to RXj is strictly better than transmitting to RXi , i.e.,

U (ssucc (δ)) ≤ U (σ(ssucc (δ))) = U (ssucc (δ)). j i i

u∈A

= min Q(k) (s, u)

(58)

We next use this result together with the monotonicity of U , to compare direct transmissions. It shows that if one receiver has a larger VAoI than others, then transmitting to the larger VAoI is the optimal action.

20.0 17.5 15.0 12.5 10.0 7.5

Fig. 2. Optimal policy over the three-dimensional VAoI state space (vtx , v1 , v2 ) for the two-receiver case (n = 2), obtained using RVI.

Q

(k+1)

and for RXj , we have, (56)

E [U (s′ ) | s, j, δ] = pU (ssucc (δ)) + (1 − p)U (sfail (δ)). (66) j

8

α = 0.2, p = 0.4, pv = 0.8, Ctx = 5.0, Cs = 10.0 Idle

10

5

5

0 10

20

15

10 5

0 0

v2

10

20

10 5

0 0

vtx = 15

20

15

v1

10

Sample

vtx = 10

20

15

v1

v1

vtx = 5

20

15

Tx RX2

v1

vtx = 0

20

Tx RX1

0 0

v2

10

20

0

v2

10

20

v2

Fig. 3. Fixed-vtx slices of the optimal RVI policy over (v1 , v2 ) for the two-receiver case (n = 2).On the vtx = 0 slice for the two-receiver case (n = 2). The policy is symmetric around v1 = v2 , and away from the diagonal the decision switches from serving the larger-VAoI receiver to idling as the receiver-VAoI difference grows.

The failure contribution is identical under both actions, and (64) shows that the success contribution under serving RXj is no larger than that under serving RXi . Hence, E [U (s′ ) | s, j, δ] ≤ E [U (s′ ) | s, i, δ] .

(67)

Both actions are direct transmissions and therefore incur the same transmission cost Ctx . Hence, by the cost definition in (17), the comparison depends only on the expected VAoI sum. For a fixed δ, if the transmission to RXi succeeds, the VAoI sum is, X ṽtx + ṽr . (68) r̸=i

If the transmission to RXj succeeds, the VAoI sum is, ṽtx +

X

ṽr .

(69)

r̸=j

The difference between them is,     X X ṽtx + ṽr  − ṽtx + ṽr  = ṽi − ṽj ≤ 0. r̸=j

sd = (vtx , m, . . . , m, m + d),

d ≥ 0.

(73)

The relevant comparison is between idling, u = 0, and directly transmitting to RXn , u = n. Under idling, each of the n − 1 receivers selects one gossip target uniformly among the other n − 1 receivers. Hence, a given receiver successfully updates RXn with probability pv /(n − 1). Therefore, the probability that RXn receives at least one successful gossip update is  n−1 pv p̃v ≜ 1 − 1 − . (74) n−1 We define (75)

Thus, direct transmission to RXn is preferred when ∆(d) ≤ 0, while idling is preferred when ∆(d) > 0. (70)

Thus, conditional on success, serving RXj gives a VAoI sum no larger than serving RXi . Moreover, when δ = 0, we have ṽi = vi < vj = ṽj , so the inequality is strict. Since both actions also have the same failure state, the expected VAoI sum, and hence the cost, is strictly smaller under serving RXj : (71)

Combining with (67)gives, Q(s, j) < Q(s, i).

The remaining decision is whether to transmit directly to an oldest receiver or to idle and rely on receiver gossip. By permutation invariance and Proposition 5, we assume WLOG that RXn is the oldest receiver and write

∆(d) ≜ Q(sd , n) − Q(sd , 0).

r̸=i

c(s, j) < c(s, i).

VII. VAO I-D IFFERENCE T HRESHOLD S TRUCTURE WITH M INIMUM VAO I- ACTIVATION

(72)

Therefore, among direct transmissions, an optimal action targets a receiver with maximum VAoI. ■

Proposition 6 (VAoI-Difference Monotonicity). Assume symmetric direct and gossip links. If p̃v > p, then for fixed vtx and m, ∆(d) is nondecreasing in d. Proof. Fix vtx , m, and d. For a fixed realization of δ ∈ {0, 1}, let the intermediate VAoIs be given by (5)–(6). For the state sd = (vtx , m, . . . , m, m + d), the first n − 1 receivers we have, m̃ = (m + δ) ∧ Vmax while for RXn we have, ṽn (d) = (m+d+δ)∧Vmax . Thus, ṽn is nondecreasing in d. We define, xn (δ) ≜ (ṽtx , m̃, . . . , m̃, ṽtx ),

(76)

xg (δ) ≜ (ṽtx , m̃, . . . , m̃, m̃),

(77)

xs (δ) ≜ (ṽtx , m̃, . . . , m̃, ṽn ).

(78)

Here, xn (δ) is the state after a successful direct transmission to RXn , xg (δ) is the state where RXn is refreshed by gossip, and xs (δ) is the state where RXn is not refreshed.

9

′

E [U (s ) | sd , n, δ] = pU (xn (δ)) + (1 − p)U (xs (δ)).

(79)

Under idling, RXn receives at least one successful gossip update with probability p̃v . Therefore, we have E [U (s′ ) | sd , 0, δ] = p̃v U (xg (δ)) + (1 − p̃v )U (xs (δ)). (80) Hence, the difference between them is ′

α = 0.2, pv = 0.8, Ctx = 5.0, Cs = 10.0 Long-term Average Cost, ρ

Under direct transmission to RXn , success occurs with probability p. Therefore, for fixed δ, under direct transmission we have

Optimal RVI Sample and Transmit Sample and Transmit with Threshold Round Robin Round Robin with Threshold Random

16 14 12 10 8 6 4 0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Direct Transmission Reliability p

′

E [U (s ) | sd , n, δ] − E [U (s ) | sd , 0, δ] = pU (xn (δ)) − p̃v U (xg (δ)) + (p̃v − p)U (xs (δ)).

(81)

Next, we compare the expected VAoI sums. Under direct transmission to RXn , the first n − 1 receiver VAoIs remain equal to m̃, while RXn becomes ṽtx with probability p and remains ṽn with probability 1 − p. Hence, " n # X E vr (t + 1) sd , n, δ = (n − 1)m̃ + pṽtx + (1 − p)ṽn . r=1

(82) Under idling, RXn becomes m̃ with probability p̃v and remains ṽn (d) with probability 1 − p̃v . Hence, # " n X E vr (t + 1) sd , 0, δ r=1

= (n − 1)m̃ + p̃v m̃ + (1 − p̃v )ṽn (d).

(83)

Therefore, the expected VAoI sum difference between direct transmission and idling is # # " n " n X X vr (t + 1) sd , 0, δ E vr (t + 1) sd , n, δ − E r=1

r=1

= pṽtx − p̃v m̃ + (p̃v − p)ṽn .

(84)

The direct transmission has additional constant Ctx , while the idling action cost is zero. This does not affect monotonicity in d. Now in (81) and (84), for fixed vtx , m, and δ, the terms involving xn (δ), xg (δ), ṽtx , and m̃ do not depend on d. The only d-dependent terms depending on ṽn are (p̃v − p)ṽn

and

(p̃v − p)U (xs (δ)).

(85)

Since p̃v > p and ṽn is nondecreasing in d, the first term is nondecreasing in d. Also, xs (δ) is componentwise nondecreasing in d, and by Proposition 3, U (xs (δ)) is nondecreasing in d. Hence, the second term is also nondecreasing in d. Thus, for each realization of δ, the difference Q(sd , n) − Q(sd , 0) is nondecreasing in d. Taking expectation over δ preserves monotonicity. Therefore, ∆(d) is nondecreasing in d. ■ Theorem 2 (VAoI-Difference Threshold). Consider the symmetric network and suppose p̃v > p. Fix vtx and m. As d increases along sd = (vtx , m, . . . , m, m + d),

d ≥ 0,

(86)

Fig. 4. Long-term average cost versus direct-link reliability p.

the decision switches at most once from direct transmission to RXn to idling. Proof. In sd , RXn has the largest VAoI. Therefore, by Proposition 5, if direct transmission is selected, it is optimal to serve RXn . Hence, the relevant comparison is between direct transmission to RXn and idling. Recall that ∆(d) = Q(sd , n) − Q(sd , 0),

(87)

so direct transmission to RXn is preferred when ∆(d) ≤ 0, while idling is preferred when ∆(d) > 0. By Proposition 6, ∆(d) is nondecreasing in d. Therefore, once ∆(d) > 0, it remains positive for all larger d. Hence, the decision switches at most once from direct transmission to RXn to idling as d increases. ■ Corollary 1 (Minimum-VAoI Activation). Let m⋆ (vtx ) denote the minimum diagonal receiver VAoI above which direct transmission is preferred to idling. Then   Ctx m⋆ (vtx ) ≤ vtx + + 1. (88) p Proof. At s0 = (vtx , m, . . . , m), gossip cannot reduce any receiver VAoI because all receivers have the same VAoI. Hence, idling leads to xm (δ) = (ṽtx , m̃, . . . , m̃). Under direct transmission to any receiver, say RXn , failure gives the same state xm (δ). On the other hand, successful transmission gives xn (δ) = (ṽtx , m̃, . . . , m̃, ṽtx ).

(89)

For fixed δ ∈ {0, 1}, m + 1 ≤ Vmax and vtx ≤ m imply that ṽtx = vtx + δ, m̃ = m + δ, and therefore ṽtx − m̃ = vtx − m. The expected VAoI sum difference between direct transmission and idling is 
 (1 − p)nm̃ + p (n − 1)m̃ + ṽtx − nm̃ = p(ṽtx − m̃).

(90)

Therefore, by (17), c(s0 , n) − c(s0 , 0) = Ctx + p(ṽtx − m̃).

(91)

To complete the comparison in (21), we now consider the expectation term. Under idling, the next state is xm (δ). Under

10

α = 0.2, p = 0.4, pv = 0.8, Cs = 10.0 Long-term Average Cost, ρ

Long-term Average Cost, ρ

α = 0.2, p = 0.4, Ctx = 5.0, Cs = 10.0 9

8 Optimal RVI Sample and Transmit Sample and Transmit with Threshold Round Robin Round Robin with Threshold Random

7

6

5

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

20.0 17.5

Optimal RVI Sample and Transmit Sample and Transmit with Threshold Round Robin Round Robin with Threshold Random

15.0 12.5 10.0 7.5 5.0 2.5

Gossip Reliability pv

5.0

7.5

10.0

12.5

15.0

Transmission Cost Ctx

17.5

20.0

Fig. 5. Long-term average cost versus gossip reliability pv .

Fig. 6. Long-term average cost versus transmission cost Ctx .

direct transmission, success gives xn (δ) with probability p, and failure gives xm (δ) with probability 1 − p. Hence,

p1 = p2 = p and pv,12 = pv,21 = pv . Unless otherwise stated, we use α = 0.2, p = 0.4, pv = 0.8, Ctx = 5, Cs = 10. We compare the optimal RVI policy with five baselines. The Sample and Transmit policy samples whenever the transmitter VAoI vtx is positive and otherwise transmits to the older receiver. The Sample and Transmit with Threshold policy uses thresholds for both sampling and transmission, which naturally incorporates idling. The Round Robin policy cycles through sampling, direct transmission to the older receiver, and idling, while Round Robin with Threshold executes the same cycle subject to sampling and transmission thresholds, thereby enabling more idling slots. The Random policy chooses uniformly among idling, transmission to RX1 , transmission to RX2 , and sampling. For the threshold based baselines, the thresholds are selected to provide the best observed performance, which is observed with thresholds of 1. The policy geometry in Fig. 2 and Fig. 3 shows three operating regimes. When vtx is large, sampling dominates because direct transmission would only propagate a stale transmitter version into the gossip network, matching Theorem 1. When vtx is small, the transmitter has a useful version, and direct transmission may become attractive as well as idling is another option. The transmission regions are symmetric around v1 = v2 , and the policy serves RX1 when v1 > v2 and RX2 when v2 > v1 , as analyzed in Proposition 5. Idling appears where receiver gossip can improve freshness without paying the transmission cost. We focus on Fig. 3 on the vtx = 0 slice. Along the diagonal v1 = v2 , direct transmission eventually activates as the common receiver VAoI grows, consistent with Corollary 1. Away from the diagonal, the policy first serves the larger VAoI receiver and then switches to idling when the VAoI difference becomes large enough for gossip to be more valuable, consistent with Theorem 2. The reliability sweeps in Fig. 4 and Fig. 5 show that direct links and gossip links affect the policy in different ways. Increasing p makes direct transmission effective and makes the performance of all the policies better. Increasing pv changes the role of idling. When gossip is reliable, idling becomes an active freshness action. The optimal policy exploits both effects by adapting when to sample, transmit, and rely on gossip, which explains its consistent advantage over less adaptive baselines. The cost sweeps in Fig. 6 and Fig. 7 highlight the economic value

E[U (s′ ) | s0 , n, δ] − E[U (s′ ) | s0 , 0, δ] = p [U (xn (δ)) − U (xm (δ))] .

(92)

Since vtx ≤ m, we have xn (δ) ⪯ xm (δ). By Proposition 3, U (xn (δ)) ≤ U (xm (δ)), so the difference in (92) is nonpositive. Combining (21), (91), and (92), and using ṽtx − m̃ = vtx − m, we obtain Q(s0 , n) − Q(s0 , 0) ≤ Ctx + p(ṽtx − m̃) = Ctx − p(m − vtx ).

(93)

Thus, direct transmission is strictly preferred to idling whenever Ctx − p(m − vtx ) < 0,

(94)

or equivalently, m − vtx >

Ctx . p

(95)

Since VAoI is integer valued, m−vtx is integer valued. Hence, the above strict inequality is guaranteed when,   Ctx m ≥ vtx + + 1. (96) p Therefore,  Ctx m (vtx ) ≤ vtx + + 1. p ⋆



(97) ■

VIII. N UMERICAL R ESULTS We evaluate the optimal policy using relative value iteration (RVI) with Vmax = 20. We focus on a two receiver case n = 2. Although the analytical results are stated for general n, the case n = 2 allows the full state (vtx , v1 , v2 ) to be visualized through 3-D policy plots and fixed-vtx slices. This makes it possible to directly inspect and get the intuition of structures. For larger n, the same RVI method applies, but the policy lies in an (n + 1)-dimensional state space and is not directly visualizable. The symmetric setting is used throughout, so

11

10 9

p = 0.4, pv = 0.8, Ctx = 5.0, Cs = 10.0

Optimal RVI Sample and Transmit Sample and Transmit with Threshold Round Robin Round Robin with Threshold Random

Long-term Average Cost, ρ

Long-term Average Cost, ρ

α = 0.2, p = 0.4, pv = 0.8, Ctx = 5.0 11

8 7 6 5 4

Optimal RVI Sample and Transmit Sample and Transmit with Threshold Round Robin Round Robin with Threshold Random

20.0 17.5 15.0 12.5 10.0 7.5 5.0 2.5

2.5

5.0

7.5

10.0

12.5

15.0

17.5

20.0

Sampling Cost Cs

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Source Evolution Probability α

Fig. 7. Long-term average cost versus sampling cost Cs .

Fig. 8. Long-term average cost versus source evolution probability α.

of structure. As Ctx increases, baselines degrade because they continue to pay for direct updates even when gossip or sampling is the smarter cost-effective choice. As Cs increases, the optimal policy delays sampling until transmitter staleness justifies the cost, which is the operational meaning of the sampling threshold structure. Fig. 8 shows that larger α increases the long-term average cost because new source versions are generated more frequently and stale information accumulates faster. The optimal policy remains lowest by balancing the actions available in the system. Overall, the numerical results show that the optimal policy exploits the geometry of the VAoI state space rather than following a fixed update pattern. Sampling is driven by transmitter staleness, direct transmission is activated when receiver VAoIs are sufficiently large or when one receiver is the best direct target, and idling becomes valuable when gossip can exploit VAoI differences between receivers. This explains the consistent performance gain of the optimal policy across reliability, cost, and source dynamics.

can make idling valuable because the fresher receivers can repair the stale receiver through gossip. We further derived a minimum-VAoI activation condition showing that, on the receiver-VAoI diagonal, direct transmission eventually dominates idling once the common receiver VAoI is sufficiently large. The numerical results show that these structural properties are visible principles of the optimal policy. The policy visualizations confirm the sampling threshold, diagonal activation of direct transmission, and the switch from direct transmission to idling as receiver VAoI imbalance grows. Parameter sweeps demonstrate that the optimal RVI policy consistently outperforms natural baselines by adapting sampling, transmission, and idling decisions to link reliabilities, operation costs, and source dynamics. Overall, the results show that freshness in gossip networks should be managed by coordinated use of source sampling, direct injection, and gossip. These structural insights open several directions for future work. The threshold and monotonicity properties can be used to design lowcomplexity heuristics for larger networks where exact dynamic programming is infeasible. They can guide structure-aware reinforcement learning by reducing the effective policy search space. Important extensions include heterogeneous direct and gossip links, multiple sources, time-varying gossip graphs and energy-constrained transmitters.

IX. C ONCLUSION We studied optimal freshness control in a fully connected gossip network under the Version Age of Information (VAoI) metric. Unlike conventional models that assume the transmitter always has the freshest source version, our model captures transmitter staleness and costly source sampling. This leads to a problem in which the transmitter must decide when to sample, when to inject its available version through direct transmission, and when to idle so that receiver gossip can improve freshness at no direct transmission cost. The main contribution of this work is a structural characterization of the optimal policy. We formulated the problem as an infinite-horizon average-cost MDP and proved monotonicity of the relative value function. This enabled us to show that sampling has a threshold structure in the transmitter VAoI: for fixed receiver VAoIs, once sampling becomes optimal, it remains optimal for all larger feasible transmitter VAoIs. Under symmetric links, the optimal direct transmission targets a receiver with the largest VAoI. Moreover, when gossip is sufficiently reliable relative to direct transmission, the policy can switch from direct transmission to idling as one receiver becomes much staler than the others. This reveals a key mechanism in gossip networks that a large VAoI imbalance

R EFERENCES [1] Y. Zheng, J. Hu, Y. Zhao, and K. Yang, “Average age of sensing in wireless powered sensor networks,” IEEE Trans. Wireless Commun., vol. 23, no. 8, pp. 9265–9281, Aug. 2024. [2] Z. Chen, T. Yang, S. Fang, L. Zhen, N. Pappas, M. Wang, D. O. Wu, and T. Q. S. Quek, “Age analysis of critical information in internet of vehicle networks with service confluence,” IEEE Open J. Commun. Soc., vol. 6, pp. 2556–2565, Apr. 2025. [3] I. Kahraman, A. Köse, M. Koca, and E. Anarim, “Age of information in internet of things: A survey,” IEEE Internet Things J., vol. 11, no. 6, pp. 9896–9914, Mar. 2024. [4] T. Soleymani, J. S. Baras, and K. H. Johansson, “Relation between value and age of information in feedback control,” in Age of Information: Foundations and Applications. Cambridge University Press, 2023, pp. 286–296. [5] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proc. IEEE INFOCOM, Mar. 2012. [6] R. D. Yates, Y. Sun, R. Brown, S. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, pp. 1183–1210, May 2021.

12

[7] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,” IEEE Commun. Mag., vol. 59, no. 6, pp. 96–102, Jun. 2021. [8] E. Uysal, O. Kaya, A. Ephremides, J. Gross, M. Codreanu, P. Popovski, M. Assaad, G. Liva, A. Munari, B. Soret, T. Soleymani, and K. H. Johansson, “Semantic communications in networked systems: A data significance perspective,” IEEE Network, vol. 36, no. 4, pp. 233–240, Jul. 2022. [9] R. D. Yates, “The age of gossip in networks,” in Proc. IEEE ISIT, Jul. 2021. [10] M. Salimnejad, M. Kountouris, A. Ephremides, and N. Pappas, “Age of information versions: A semantic view of markov source monitoring,” IEEE Trans. Commun., vol. 73, no. 12, pp. 14 486–14 502, Dec. 2025. [11] M. Bastopcu, B. Buyukates, and S. Ulukus, “Gossiping with binary freshness metric,” in Proc. IEEE Globecom Workshops (GC Wkshps), Dec. 2021, pp. 1–6. [12] A. Zakeri, M. Moltafet, and M. Codreanu, “Semantic-aware sampling and transmission in real-time tracking systems: A POMDP approach,” IEEE Trans. Commun., vol. 73, no. 7, pp. 4898–4913, Jul. 2025. [13] J. Selen, Y. Nazarathy, L. L. H. Andrew, and H. L. Vu, “The age of information in gossip networks,” in Analytical and Stochastic Modeling Techniques and Applications, ser. Lecture Notes in Computer Science, A. Dudin and K. De Turck, Eds. Berlin, Heidelberg: Springer, 2013, vol. 7984, pp. 364–379. [14] B. Buyukates, M. Bastopcu, and S. Ulukus, “Version age of information in clustered gossip networks,” IEEE J. Sel. Areas Inf. Theory, vol. 3, no. 1, pp. 85–97, Mar. 2022. [15] I. Hasan and A. Arafa, “RC-gossip: Information freshness in clustered networks with rate-changing gossip,” in Proc. Asilomar, Oct. 2025. [16] A. Srivastava and S. Ulukus, “Network connectivity-information freshness tradeoff in information dissemination over networks,” IEEE Trans. Inf. Theory, vol. 72, no. 5, pp. 2993–3013, May 2026. [17] T. J. Maranzatto, “Age of gossip in random and bipartite networks,” in Proc. IEEE ISIT, Jul. 2024. [18] A. Srivastava, T. J. Maranzatto, and S. Ulukus, “Information freshness in dynamic gossip networks,” in Proc. IEEE ITW, 2025, arXiv:2504.18504. [19] E. Bayram, M. Bastopcu, M. A. Belabbas, and T. Başar, “Age of coded updates in gossip networks under memory and memoryless schemes,” IEEE Trans. Commun., vol. 73, no. 12, pp. 14 562–14 578, 2025. [20] A. Srivastava, T. J. Maranzatto, and S. Ulukus, “Age of gossip with the push-pull protocol,” in Proc. IEEE ICASSP, Hyderabad, India, Apr. 2025. [21] A. Srivastava and S. Ulukus, “Mobility in age-based gossip networks,” in Proc. Allerton, Sept. 2024, pp. 1–8. [22] I. Hasan and A. Arafa, “Version age of information with contact mobility in gossip networks,” in Proc. Allerton, Sept. 2025. [23] P. Kaswan, P. Mitra, A. Srivastava, and S. Ulukus, “Age of information in gossip networks: A friendly introduction and literature survey,” IEEE Trans. Commun., vol. 73, no. 8, pp. 6200–6220, Aug. 2025. [24] P. Mitra and S. Ulukus, “ASUMAN: Age sense updating multiple access in networks,” in Proc. Allerton, Sept. 2022. [25] ——, “Timely opportunistic gossiping in dense networks,” in Proc. IEEE INFOCOM Workshops, May 2023. [26] ——, “A learning based scheme for fair timeliness in sparse gossip networks,” in Proc. IEEE ICMLCN, May 2024. [27] E. Delfani and N. Pappas, “Version age-optimal cached status updates in a gossiping network with energy harvesting sensor,” IEEE Trans. Commun., vol. 73, no. 4, pp. 2344–2360, Apr. 2025. [28] I. Hasan and A. Arafa, “Transmit or idle: Efficient AoI optimal transmission policy for gossiping receivers,” in Proc. IEEE ICC, May 2026. [29] ——, “Semantic freshness optimal sampling and transmission for gossiping receivers,” in Proc. IEEE ITW, Nov. 2026, to appear. [30] A. U. Atasayar, A. Li, Ç. Arı, and E. Uysal, “Fresh data delivery: Joint sampling and routing for minimizing the age of information,” in Proc. ACM MobiHoc, Houston, TX, USA, Oct. 2025. [31] A. Zakeri, M. Moltafet, M. Leinonen, and M. Codreanu, “Minimizing the AoI in resource-constrained multi-source relaying systems: Dynamic and learning-based scheduling,” IEEE Trans. Wireless Commun., vol. 23, no. 1, pp. 450–466, Jan. 2024. [32] T. Soleymani, J. S. Baras, and D. Gündüz, “Transmit or retransmit: A tradeoff in networked control of dynamical processes over lossy channels with ideal feedback,” IEEE Trans. Inf. Theory, vol. 70, no. 11, pp. 7853– 7866, Nov. 2024. [33] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “Aoi-optimal joint sampling and updating policy for wireless powered communication systems,” IEEE Trans. Commun., vol. 68, no. 8, pp. 4808–4822, Aug. 2020.

[34] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: An enabler of semantics-empowered communication,” IEEE Trans. Inf. Theory, vol. 68, no. 10, pp. 6673–6702, Oct. 2022. [35] A. Arafa, J. Yang, and S. Ulukus, “Age-minimal online policies for energy harvesting sensors with random battery recharges,” in Proc. IEEE ICC, May 2018. [36] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 534–556, Jan. 2020. [37] A. Arafa and S. Ulukus, “Timely updates in energy harvesting two-hop networks: Offline and online policies,” IEEE Trans. Wireless Commun., vol. 18, no. 8, pp. 4017–4030, Aug. 2019. [38] H. H. Yang, A. Arafa, T. Q. S. Quek, and H. V. Poor, “Age-based scheduling policy for federated learning in mobile edge networks,” in Proc. IEEE ICASSP, May 2020. [39] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Timely status updating over erasure channels using an energy harvesting sensor: Single and multiple sources,” IEEE Trans. Green Commun. Netw., vol. 6, no. 1, pp. 6–19, Mar. 2022. [40] A. Arafa, K. Banawan, K. G. Seddik, and H. V. Poor, “Sample, quantize, and encode: Timely estimation over noisy channels,” IEEE Trans. Commun., vol. 69, no. 10, pp. 6485–6499, Oct. 2021. [41] Y. P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” IEEE Trans. Mobile Comput., vol. 19, no. 12, pp. 2903–2915, Dec. 2020. [42] B. Zhou and W. Saad, “Joint status sampling and updating for minimizing age of information in the internet of things,” IEEE Trans. Commun., vol. 67, no. 11, pp. 7468–7482, Nov. 2019. [43] K. Nakhleh and I.-H. Hou, “DeepTOP: Deep threshold-optimal policy for MDPs and RMABs,” in Proc. NeurIPS, 2022. [44] A. Bura, S. C. Bobbili, S. Rameshkumar, D. Rengarajan, D. Kalathil, and S. Shakkottai, “Structure-aided reinforcement learning for media streaming over wireless edge networks,” IEEE Trans. Netw., vol. 34, pp. 2605–2620, 2026. [45] A. Roy and N. Biswas, “Robust and low-complexity task scheduling algorithms for a mobile edge computing system,” IEEE Trans. Green Commun. Netw., vol. 9, no. 3, pp. 1340–1353, Sept. 2025. [46] A. Roy, V. Borkar, A. Karandikar, and P. Chaporkar, “Online reinforcement learning of optimal threshold policies for markov decision processes,” IEEE Trans. Automat. Contr., vol. 67, no. 7, pp. 3722–3729, Jul. 2022. [47] J. Wigmore, B. Shrader, and E. Modiano, “A novel switch-type policy network for resource allocation problems,” in Proc. WiOpt, May 2025, pp. 1–8. [48] L. Yang, W. Lv, Y. Xu, J. Tao, and D. E. Quevedo, “Structure-aware reinforcement learning for optimal transmission scheduling over packet length-dependent lossy networks,” IEEE Trans. Automat. Contr., vol. 70, no. 4, pp. 2576–2583, Apr. 2025. [49] A. Jitani, A. Mahajan, Z. Zhu, H. Abou-Zeid, E. T. Fapi, and H. Purmehdi, “Structure-aware reinforcement learning for node-overload protection in mobile edge computing,” IEEE Trans. Cogn. Commun. Netw., vol. 8, no. 4, pp. 1881–1897, Dec. 2022. [50] D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, 3rd ed. Athena Scientific, 2007. [51] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st ed. USA: John Wiley & Sons, Inc., 1994.

A PPENDIX A P ROOF OF P ROPOSITION 1 Let s(t) = (vtx , v1 , . . . , vn ) ∈ S, where 0 ≤ vtx ≤ vi ≤ Vmax , ∀i. It holds that after source evolution in the intermediate state, 0 ≤ ṽtx ≤ ṽi ≤ Vmax , ∀i. If u = i, then upon success RXi is set to ṽtx , while every j ̸= i remains at ṽj . Upon failure, all receivers remain at ṽi , ∀i. In both cases, every receiver VAoI is between ṽtx and Vmax . If u = 0, the transmitter idles and vtx (t + 1) = ṽtx . Receiver i updates as (13). Since ṽi ≥ ṽtx , ∀i. Hence, vi (t + 1) ≥ vtx (t + 1), ∀i. So, every receiver VAoI is between ṽtx and Vmax . If u = n + 1, sampling resets the transmitter VAoI to zero, and the receivers gossip as in (13) which gives

13

0 = vtx (t + 1) ≤ vi (t + 1) ≤ Vmax , ∀i. Thus, for every action and transition outcome, 0 ≤ vtx (t+1) ≤ vi (t+1) ≤ Vmax , ∀i. and therefore s(t + 1) ∈ S. Hence, S is closed. ■ A PPENDIX B P ROOF OF P ROPOSITION 2 ′ Let s = (vtx , v1 , . . . , vn ) and s′ = (vtx , w1 , . . . , wn ) be arbitrary feasible states. Consider a stationary randomized policy with π(u|s) > 0 for all u ∈ A and s ∈ S. First, we show that s0 = (0, 0, . . . , 0) is accessible from s. Choose the sampling action u = n + 1, and realize δ = 0 with no successful receiver gossip. This event has positive probability since 1 − α > 0 and 1 − pv,ji > 0 for all j ̸= i. It resets the transmitter VAoI to zero while leaving the receiver VAoIs unchanged. Then, over the next n slots, transmit once to each receiver RXi , realizing δ = 0 and a successful direct transmission Qn in each slot. These outcomes have probability (1 − α)n i=1 pi > 0. Since the transmitter VAoI remains zero, each receiver is reset to zero. Hence, s0 is reached with positive probability. Next, we show that s′ is accessible from s0 . Define ′ di = wi − vtx ,

i = 1, . . . , n.

(98)

Choose an ordering ℓ1 , . . . , ℓn of the receivers such that dℓ1 ≥ dℓ2 ≥ · · · ≥ dℓn . Starting from s0 , reset RXℓ1 to VAoI zero by choosing a direct transmission to RXℓ1 , realizing δ = 0, and realizing a successful transmission. This event has probability (1 − α)pℓ1 > 0. Then create dℓ1 − dℓ2 slots in which δ = 1 occurs and the chosen direct transmission fails. Each such slot has probability α(1 − pℓ ) > 0 for some chosen receiver ℓ, and increases every VAoI by one without refreshing any receiver. Next, sample with δ = 0 and no successful gossip, so that vtx = 0, and reset RXℓ2 to VAoI zero by a successful direct transmission with δ = 0. Continuing similarly, after resetting RXℓj to VAoI zero, create dℓj − dℓj+1 slots in which δ = 1 occurs and the chosen direct transmission fails, for j = 1, . . . , n − 1. Each receiver reset has probability (1 − α)pℓj > 0, and each such VAoIincrement slot has probability α(1 − pℓ ) > 0. After resetting RXℓn , create dℓn additional such slots. Thus, RXℓj experiences (dℓj −dℓj+1 )+· · ·+(dℓn−1 −dℓn )+dℓn = dℓj VAoI increments after its reset. Hence every receiver RXi ends with VAoI di . At this point the transmitter VAoI may be positive. Choose the sampling action once more with δ = 0 and no successful gossip. This event has positive probability and resets only the transmitter VAoI to zero while leaving the receiver VAoIs unchanged. Hence, (0, d1 , . . . , dn ) is reached with positive ′ probability. Finally, from (0, d1 , . . . , dn ), create vtx slots in which δ = 1 occurs and the chosen direct transmission fails. These slots have positive probability and increase all VAoIs ′ by vtx without refreshing any receiver, yielding ′ ′ ′ ′ (vtx , d1 + vtx , . . . , dn + vtx ) = (vtx , w1 , . . . , wn ) = s′ , (99) ′ since di = wi − vtx . Therefore, s′ is accessible from s0 . Thus every feasible state can reach s0 , and s0 can reach every feasible state. Hence all states in S communicate under the randomized policy, and the MDP is communicating. ■

A PPENDIX C P ROOF OF L EMMA 1 Let s ⪯ s′ , where s = (vtx , v1 , . . . , vn ) and s′ = ∈ {0, 1}, by (5) and (6) the intermediate states satisfy s̃ ⪯ s̃′ . Consider a direct transmission u = i, i ∈ {1, . . . , n}. If the transmission fails, the next states are s̃ and s̃′ , so the order is preserved. If the transmission succeeds, then RXi is set to the transmitter VAoI in both systems. Hence, the i-th receiver coordinates in the ′ ′ two next states are ṽtx and ṽtx , respectively. Since ṽtx ≤ ṽtx , and all other coordinates are unchanged from the intermediate states, therefore s̃ ⪯ s̃′ . Thus, Fi,ω,δ (s) ⪯ Fi,ω,δ (s′ ). Next we consider the idle action u = 0. The transmitter coordinates ′ remain ṽtx and ṽtx . For each receiver, under the fixed gossip outcome ω, by (13) and the monotonicity of the minimum operation, ṽi ≤ ṽi′ holds for i ∈ {1, 2, . . . , n}. Hence, F0,ω,δ (s) ⪯ F0,ω,δ (s′ ). Finally, consider the sampling action u = n + 1. The transmitter VAoI is reset to zero in both ′ systems, so vtx = 0 and vtx = 0. The receiver coordinates follow the same gossip update rule as in (13). Therefore, by the same argument,ṽi ≤ ṽi′ holds for i ∈ {1, 2, . . . , n}. Fn+1,ω,δ (s) ⪯ Fn+1,ω,δ (s′ ). Thus, for every fixed action u, source increment δ, and transition outcome ω, we have: ′ (vtx , v1′ , . . . , vn′ ). For any fixed δ

Fu,ω,δ (s) ⪯ Fu,ω,δ (s′ )

(100) ■

. A PPENDIX D P ROOF OF L EMMA 2

Since the action cost C(u) in the immediate cost (17) is independent of the state, it is enough to compare the expected next receiver VAoI sums. Let s ⪯ s′ and fix an action u ∈ A. For every fixed source increment δ and transition outcome ω, Lemma 1 gives Fu,ω,δ (s) ⪯ Fu,ω,δ (s′ ).

(101)

Therefore, under the same realization (u, δ, ω), each next receiver VAoI starting from s is no larger than the corresponding next receiver VAoI starting from s′ . Hence, n X i=1

vi (t + 1) ≤

n X

vi′ (t + 1),

(102)

i=1

where vi (t + 1) and vi′ (t + 1) denote the next receiver VAoIs generated from s and s′ , respectively, under the same realization. Since this inequality holds for every realization of δ and ω, taking expectation gives " n # " n # X X ′ E vi (t + 1) s, u ≤ E vi (t + 1) s , u . (103) i=1

i=1

Adding the same action cost C(u) to both sides and using (17) gives c(s, u) ≤ c(s′ , u).

(104) ■

Related documents

• Semantic Freshness Optimal Sampling and Transmission for Gossiping Receivers#819160
• Semantic Freshness Optimal Sampling and Transmission for Gossiping Receivers#809168
• Resetting-based designated information distribution#1605191
• Age of Gossip in Ring Networks With Non-Poisson Updates#618057
• Age of Gossip in Ring Networks With Non-Poisson Updates#617557