Lagrange Index based Scheduling for Minimizing Age of Updates from Heterogeneous Sources
arXiv:2604.18077v1 [cs.NI] 20 Apr 2026
Aniket Mukherjee, Joy Kuri and Chandramani Singh A non-preemptive (non-switching) transmission discipline is employed where a scheduled source keeps the channel until it successfully transmits all the packet pertaining to its update. We formulate the problem as a Semi-Markov Decision Process (SMDP). However, this problem suffers from the curse of dimensionality. To address it, we treat the problem as a Restless Multi-Armed Bandit (RMAB) and develop a Lagrange index based heuristic. To the best of our knowledge, this is the first work to study RMAB formulation of weakly coupled SMDPs and to develop scalable index policies for them. Our heuristic scheduling policy substantially outperforms the existing solutions.
Abstract—Modern sensing systems generate heterogeneous updates ranging from small status packets to large data objects. We study a single-hop wireless uplink network where sensors generate updates at will, each consisting of a sensor dependent number of packets. Under a strict medium-access constraint and non-preemptive (no-switching) transmissions, decision stages become action-dependent and stochastic. We formulate the problem as a restless multi-armed bandit (RMAB) with semi-Markov decision process (SMDP) dynamics and develop a Lagrange index based heuristic for minimizing weighted average AoI cost. For the weighted AoI setting, we utilize the structural properties of the heuristic to enable efficient index computation. Numerical results demonstrate consistent performance gains over existing non-preemptive scheduling policies, providing a practical solution for heterogeneous freshness-aware systems. Index Terms—Age of information, Semi-Markov decision process, Restless multiarmed bandit, Lagrange indices.
I. I NTRODUCTION Modern sensing systems consist of spatially distributed sensors that continuously monitor physical processes and transmit status updates to a central controller or edge server [1]. These updates are often heterogeneous in size, ranging from small scalar measurements to large data objects such as images, video frames, or LIDAR scans. In slotted wireless systems (eg., Wi-Fi 6 and 5G), such updates may span multiple transmission slots, and medium-access constraints limit simultaneous transmissions. As sensing networks increasingly support real-time monitoring, autonomous systems, and cyberphysical applications, efficient scheduling of heterogeneous updates becomes critical to maintaining timely situational awareness [2]. The Age of Information (AoI) quantifies information freshness by measuring the time elapsed since the most recently generated update was successfully delivered [2]–[4]. Unlike traditional delay or throughput metrics, AoI directly captures the timeliness of the received information, making it particularly suitable for sensing and monitoring applications where stale data can degrade estimation accuracy, control performance or tracking reliability. Although AoI is a theoretical metric, its practical value has been demonstrated experimentally; for example, [5] shows that an AoI-aware WiFi middleware significantly improves information freshness and tracking accuracy in UAV networks compared to standard WiFi-UDP/TCP. We consider a set of heterogeneous sources connected to a common receiver through an unreliable wireless channel that allows only one source to transmit at a time (see Figure 1). The sources generate updates of different sizes, which must be delivered to the receiver so as to minimize the long term weighted average age of updates at the receiver.
Fig. 1: N sources with heterogeneous update sizes, connected to a receiver through an unreliable wireless channel. A. Related Work We now briefly discuss the related work on (a) AoI minimization and on (b) Lagrange index based heuristics for RMAB problems. 1) AoI Minimization: The concept of AoI was introduced in [3], and a comprehensive overview of its extensions and practical relevance was provided in [6]. The papers concerned with AoI minimization can be categorized as in Table I. There are two dimensions: (a) Whether all source updates are of equal length or not, and (b) whether one can interrupt transmission of an update from a source before it is complete, and “switch” to transmitting another source’s update [“switching”], or not [“non-switching”]. [7] studies a wireless network in which a base station generates single-packet updates and, in each slot, selects a user to which it will transmit, over an unreliable channel with user-dependent success probabilities pi (constant over time). The objective is to minimize the longterm average AoI. The greedy policy was shown to be optimal when pi = p for all i. For the asymmetric case, a Whittle index and a max-weight policy were proposed. In [8], for equal
1
update lengths, the same model as in [7] was considered, but with a nonlinear function of AoI as the objective. The authors established indexability and proposed a Whittle index–based policy. In reality update lengths can be different and we consider differing update lengths in our work. For heterogeneous sources with reliable channels, [9] considered an AoI model in which each source requires a fixed processing time, followed by a fixed transmission time under a non-preemptive service discipline. They established indexability and proposed a Whittle index policy. The problem was formulated as a restless multi-arm bandit and decoupled into single-source Markov Decision Process (MDP). In the resulting single-source MDP, only two actions were considered: when the tagged source is scheduled, the AoI resets to the total processing and transmission time; when it is not scheduled, the AoI increases by one. In heterogeneous systems, this assumption is restrictive, since the cost when the tagged source is not scheduled depends on service duration of the scheduled source. In [10] and [11], the same uplink model as ours (Figure 1) was considered. [10] considers policies that allowed switching and suggested a suboptimal policy to minimize the average AoI. For the non-preemptive setting, [11] proposed a stationary randomized policy, referred to as the No-Switching Randomized Policy (NSRP).
average age of updates at the receiver (Section II). We pose it as a average cost SMDP problem (Section II-A). 2) We propose an approach to frame general weakly coupled SMDPs as RMABs. Using this formulation, we develop a Lagrange index based heuristic for weakly coupled SMDPs (Section III). 3) We apply the above heuristic to the update scheduling problem. In particular, we argue that the policies suggested for the decoupled single source problems are one step lookahead policies [15, Section 4.4] and provide an iterative algorithm to obtain these. We use solutions to the decoupled problems to obtain Lagrange indices, and subsequently, a heuristic for the original problem (Section V). Our numerical results show that the proposed heuristic noticeably outperforms the known solutions (Section VI). II. S YSTEM M ODEL We consider a discrete-time sensing and communication system with N sources (e.g., sensors) indexed by 1, · · · , N . Each source generates updates that have to be communicated to a common receiver through an unreliable wireless channel. We consider scheduling of update transmissions so as to minimize the average age of updates at the receiver. We now formally describe the update generation and communication processes, age evolution at the receiver, and the optimal scheduling problem. Update generation: Source i’s updates are Li packet long. A source can take multiple slots to transmit an update. When a source is scheduled to transmit, it generates a new update unless it has an unfinished update transmission. Update transmission: The communication channel allows only one source to transmit at a time. When scheduled, a source transmits one packet per slot. Owing to channel unreliability, each packet transmission succeeds with probability p ∈ (0, 1] and fails with probability 1 − p. Clearly, source i requires at least Li slots to transmit an update. We consider non-preemptive update transmissions; a scheduled source keeps the channel until it successfully transmits all the packet pertaining to its update. (i) Let τk denote the time when kth successful update delivery (i) of source i is accomplished. Moreover, let Xk denote the number of slots needed for delivery of this update. From the above discussion, the generation time of this packet is (i) (i) τk − Xk . Note that because of the packet generation model (i) (generate at will) assumed, if Li = 1 then Xk = 1 for all k (i) and if Li ≥ 2 then Xk , k ≥ 1 are i.i.d. random variables. In particular, (i) (i) P(Xk = l) = pl
TABLE I: Related Works Equal length update Switching Non-switching
[7], [8]
Unequal length update [11], [10] [11], [9]
2) Lagrange Indices for RMABs: Lagrange index policies for restless multi-armed bandits have been studied through linear programming relaxations in [12], [13], where the dual decomposition yields index-type policies and asymptotic optimality was established for large-scale systems with underlying Markov Decision Process (MDP) dynamics. The framework was further extended in [14] to settings with unknown transition kernels, preserving asymptotic optimality via learningbased methods. Our setting differs fundamentally in that we consider restless bandits under an SMDP formulation induced by non-preemptive service with random completion times, rather than discrete-time MDP dynamics. While we adopt a similar Lagrange relaxation principle, we do not establish asymptotic optimality for the resulting policy under SMDP and instead use it as a computationally tractable heuristic for the heterogeneous AoI problem. None of the above works considers RMAB formulation and index-based policies for weakly coupled SMDPs. In the context of AoI minimization for heterogeneous sources and unreliable channels, existing work is limited to stateindependent stationary policies that are understandably suboptimal.
(i)
where, if Li = 1 then p1 = 1, and if Li ≥ 2 then ( L −1 l−2 i (1 − p)l−Li if l ≥ Li , (i) Li −2 p pl = (1) 0 otherwise. The above equation follows from the observation that after successful transmission of the first packet, the remaining Li −1 successful packet transmissions require a negative binomial (i) number of additional slots. It follows that E[Xk ] = Li −(1−p) . p
B. Our Contributions Following are our main contributions. 1) We model the problem of scheduling of updates from heterogeneous sources to minimize the long run weighted
2
increment by one at successive slots between tk and tk+1 . Hence the kth stage cost associated with source i equals τ (k)−1 X ∆(k)(∆(k) − 1) . αi (vi (k) + s) = αi ∆(k)vi (k) + 2 s=0 Consequently, the expected kth stage cost associated with source i, denoted as gi (vi (k), a(k)), is given by N X gi (vi (k), a(k)) = αi aj (k)(vi (k)Lj + w(Lj )). (3)
Age of updates: For any source, the age of updates, also referred to as the age of information (AoI), at the receiver is defined as the time elapsed since generation of the last received update. Let v̄i (t) denote the age of updates of source i at the receiver at time t. Clearly, ( (i)
(i)
Xk if t = τk , v̄i (t − 1) + 1 otherwise. The expected long term weighted average cost is given as " T # X 1 lim E αi v̄i (t) . T →∞ T t=1 v̄i (t) =
j=1
where
Lj (Lj − 1) ∆(k)(∆(k) − 1) l aj (k) = 1 = . w(Lj ) := E 2 2p (4)
Optimal Scheduling problem: Update transmissions of various sources must be scheduled so as to minimize the above cost. Notice that a source must be selected for update transmission after either of the following events.
AoI
1) An update is successfully delivered. 2) Transmission of the first packet of an update fails.
AoI
Clearly, the intervals between successive decision instants are random variables. We frame the above scheduling problem as a semi-Markov decision process (SMDP) as described below.
vj (k) + 3 vi (k) + 1 vi (k)
vj (k) vi (k) + 1
A. SMDP Formulation
3 vi (k)
vi (k)
Let tk , k ≥ 1 denote the successive decision instants. Let vi (k) denote the age of updates of source i at the receiver at tk ; v(k) := (v1 (k), · · · , vN (k)) ∈ ZN + represents the state at tk . Further, let a(k) := (a1 (k), · · · , aN (k)) ∈ {0, 1}N denote the scheduling decision at tk ; ai (k) = 1 if source i is chosen for update transmission at tk and ai (k) = 0 otherwise. The scheduling constraint prescribes that exactly one source be PN chosen at each tk , i.e., a (k) = 1 ∀k ≥ 1. Let i i=1 ∆(k) := tk+1 − tk , k ≥ 1 denote the gaps between successive decision instants. Given action a(k) with ai (k) = 1, ∆(k) = 1 if the first packet’s transmission at tk fails and ∆(k) ≥ Li otherwise. More specifically, ∆(k) is distributed as follows. (i) P(∆(k) = l|ai (k) = 1) = ppl + (1 − p)1(l = 1). (2) It can be easily checked that E[∆(k)|ai (k) = 1] = Li . More generally, the expected value of the interval ∆(k), denoted as S(a(k)), is given as follows. N X S(a(k)) ≜ E[∆(k)] = aj (k)Lj .
transmission Time
tk tk+1
(a) ∆(k) = 1 (failure)
tk
Time tk+1 = tk + l
(b) ∆(k) = 3 (success)
Fig. 2: State transition from tk to tk+1 given that source i is scheduled at tk . We assume Li = 2. We can formulate the scheduling problem as a long-term average cost control problem. A stationary admissible policy is a mapping from the state space ZN + to the set of N -dimensional standard unit vectors. So, given the initial state, any policy π induces a set of actions a(k) ∈ {0, 1}N , k ≥ 1 such that N X aj (k) = 1 ∀k ≥ 1. (5) j=1
Using Markov renewal reward theorem [16, Theorem 7.5], the long-term expected average-cost associated with policy π is given by hP i K PN Eπ k=0 i=1 gi (vi (k), a(k)) i hP (6) lim K PN K→∞ Eπ i=1 ai (k)Li k=0
j=1
Further, given v(k) and a(k) with ai (k) = 1, vi (k + 1) = vi (k)+1 if the first packet’s transmission at tk fails and vi (k+ 1) = ∆(k) otherwise. In either case, vj (k+1) = vj (k)+∆(k) for all j ̸= i. See Figure 2 for an illustration. We thus see that vj (k + 1) = vj (k) + 1 for all j with probability 1 − p, and vi (k + 1) = l and vj (k + 1) = vj (k) + l for all j ̸= i with (i) probability ppl . Clearly, v̄i (t), t ≥ 1 is a controlled semiMarkov chain (or SMDP). We refer to tk as the kth stage of this SMDP. Now, we describe the single stage cost associated with the above SMDP. The weighted update-age cost incurred over {tk , · · · , tk+1 − 1}, also referred to as the kth stage cost, is a function of the state v(k), action a(k) and the interval length ∆(k). Note that the ages of updates for all the sources
The optimal control problem aims to minimize this cost over all the admissible policies. Evidently, this problem suffers from curse of dimensionality and is non-viable even for moderate number of sources. We address this issue via posing the scheduling problem as a RMAB problem with the sources being treated as the arms, and proposing a Lagrange index based heuristic. We can see that the update age evolution of different sources are weakly coupled through the actions at the decision instants as in RMAB problems. However, unlike a classical RMAB setting where states constitute a controlled Markov chain, state evolution in our case is a controlled semi-Markov chain. Here,
3
over all π for which the the induced actions a(k), k ≥ 0 satisfy (8). Constraint (8) allows multiple arms to be played in a slot. This relaxation enables a Lagrangian formulation that decomposes into N independent single-arm control problems.
the decoupled problems associated with different arms are also SMDPs. To the best of our knowledge, RMAB formulation of SMDPs has not been considered so far. In the next section, we discuss how the RMAB framework can be extended for general weakly-coupled SMDPs and also propose a Lagrange index based heuristic.
The Dual Problem: Introducing a Lagrange multiplier λ ∈ R associated with constraint (8), the Langrangian can be written ash i PK PN Eπ k=0 i=1 (gi (vi (k), a(k)) + λai (k)S(a(k))) hP i lim −λ K K→∞ Eπ k=0 S(a(k))
III. RMAB F ORMULATION OF SMDP S In this section, we consider general weakly-coupled SMDPs, treat them as RMABs and develop a Lagrange index based heuristic. We retain most of the notation in Section II-A. In particular, we consider N arms with vi (k) ∈ Vi being the state of arm i and ai (k) ∈ {0, 1} being the action associated with i at the kth stage. As before, the actions are coupled Parm N as i=1 ai (k) = 1 for all k ≥ 1 and. v(k) and a(k) represent state and action vectors at the kth stage. Given a(k), ≥ 1, the states of different arms, i.e., vi (k), k ≥ 1 evolve independently. In particular, for all k ≥ 1, given vi (k) and a(k), vi (k + 1) is independent of vj (k), j ̸= i and previous state and action vectors. For any i, Li represents the sojourn time of the joint SMDP in the kth stage given ai (k) = 1. Finally, gi (vi , a) represents the single stage cost associated with arm i given that it is in state i and action a is taken. The total single state PN cost for state-action pair (v, a) is given by i=1 gi (vi , a). We do not specify the state transition probabilities as these are not needed for the following discussion. QN N An admissible policy π : induces i=1 Vi → {0, 1} a sequence of actions a(k), k ≥ 1 that satisfy (5). Let Π be the set of all admissible policies. We aim to minimize the long-term average expected cost, given by (6), over all π ∈ Π. Constraint (5) which couples the individual SMDPs necessitates that these be solved together rendering an optimal solution intractable. Below, we propose a novel relaxation of (5) that facilitates decoupling of individual SMDPs.
So, the dual problem is max min λ∈R
where L̃i (π, λ) := " Eπ
PK k=0
π
! L̃i (π, λ) − λ .
(10)
i=1
gi (vi (k), a(k)) + λ ai (k) S(a(k))
lim
K→∞
N X
Eπ
hP
K k=0 S(a(k))
i
# . (11)
We note that (10) does not decouple. However, a lower bound to (10) can be obtained as follows ! N X min L̃i (π, λ) − λ . (12) max λ∈R
π
i=1
Now we propose a method to solve (12). 1) Inner Minimization Problem: For a fixed λ The inner minimization problem is equivalent to min L̃i (π, λ) π
which decouples into N SMDPs associated with the N arms. A policy π for the ith arm’s problem is a mapping from Vi from {0, 1}N . The collection of these single-flow solutions provides the minimizing policy for the current λ. We now focus on the corresponding single-arm problem. In particular, for a fixed multiplier λ, we study the optimal control of an individual arm i under the modified expected per-stage cost gi (vi (k), a(k)) + λai (k)S̃(a(k)).
A. A Relaxed Problem We adopt the standard relaxation used in classical RMABs [12]–[14]. Let N (T ) denote the number of decision stages up to time T . Constraint (5) which ensures that exactly one arm be played at each stage also implies that the long term expected fractions of slots during which different arms are played add up to one. More formally, (5)implies that N (T ) N
The single-arm average-cost optimality equation can be written as n o hi (vi ) = min Qi,i (vi ), min Qi,j (vi ) , (13)
The relaxed problem therefore becomes hP i K PN Eπ k=0 i=1 gi (vi (k), a(k)) hP i min lim K π K→∞ Eπ k=0 S(a(k))
where Qi,k (vi ) ( gi (vi , ei ) + (λ − θ(λ))S(ei ) + E[hi (Vi′ ) | vi , ei ], k = i, = gi (vi , ek ) − θ(λ)S(ek ) + E[hi (Vi′ ) | vi , ek ], k ̸= i. Here, ek denotes the unit scheduling vector that selects source k. In (13), hi (v) is the bias (relative value) function and θ(λ) is the optimal average cost for the single-flow problem. The Bellman equation contains N actions corresponding to activating each arm. Solving (13) for a fixed λ yields the optimal policy for source i under the Lagrangian relaxation. The assumptions on gi (v, ei ) such that the solution to (13) exists is as per [17], [18].
j̸=i
1 X X Eπ ai (k)S(a(k)) = 1. (7) T →∞ T k=0 i=1 hP i N Note that the expected sojourn times Eπ i=1 ai (k)Li are bounded by maxi Li . Hence, by Markov renewal reward theorem [15], [16],h (7) is equivalent to i PK PN Eπ i=1 ai (k)S(a(k)) k=0 i hP lim = 1. (8) K K→∞ Eπ k=0 S(a(k)) lim
(9)
4
2) Dual Update: Note that the dual problem is a concave maximization problem. The resulting dual function is then maximized over λ using standard scalar ascent methods (e.g., subgradient ascent), yielding an optimal multiplier λ⋆ , which is then used to update the dual variable. Iterating this procedure produces λ⋆ and a corresponding policy. To update the dual variable, we compute the average fraction of time the i-th arm is activated under this optimal policy. This is obtained by solving an auxiliary average-cost Bellman equation where the per-stage cost equals 1 when arm i is activated and 0 otherwise. Let µi (λ) denote the resulting long-run activation fraction of arm i under the optimal policy for multiplier λ. The dual variable is then updated using bisection method.
We establish a few structural properties of the hi (.) function. In Lemma 1, we show the monotonicity property of the Bellman equation. In Lemma 2 we reduce the action space from N to 2 actions. Theorem 1 shows that the 2 action Bellman equation has a threshold structure using one step lookahead policies.
B. Lagrange Indices
We now show that the inner minimization over j ̸= i in (16) reduces to a single dominant competing action.
Lemma 1 (Monotonicity of the value function). The one-step cost gi (v, a) is nondecreasing in v for every feasible action a. Consequently, any solution hi (·) of (16) is nondecreasing in v, i.e., v1 ≥ v2 =⇒ hi (v1 ) ≥ hi (v2 ). Proof. See Appendix A
⋆
Upon convergence to λ , we compute, for each arm i, the Lagrange index γi (vi ) = Qi,i (vi ) − min Qi,j (vi ). (14)
Lemma 2 (Dominant competing action). Fix a source i and multiplier λ, and define m(i) = arg min Lj .
j̸=i
Heuristic for the Original Problem: The resulting Lagrange index policy selects the arm m∗ = argmin γi (vi ). (15)
j̸=i
Then, for all vi ∈ Z+ and all j ̸= i, Qi,m(i) (vi ) ≤ Qi,j (vi ). That is, among all competing sources, it is optimal to select the one with the smallest update length.
i
This constitutes the Lagrange index policy for restless multiarmed bandits for SMDP. In Section IV we discuss about the AoI minimization problem stated in (6).
Proof. The proof is provided in Appendix B.
IV. S INGLE SOURCE AO I MINIMIZATION
Lemma 2 formalizes the structural property that, whenever source i is not scheduled, it is optimal to schedule the “fastest” competing source, i.e., one with smallest update length Lj . Intuitively, this minimizes the time during which the age of flow i continues to grow. As a consequence of Lemma 2, the inner minimization over j ̸= i in (16) is achieved by the single index m. Accordingly, the Bellman equation simplifies to a reduced two-action form. n o
We now return to the weighted AoI minimization problem introduced in Section II. Under Lagrangian relaxation, the original multi-source problem decouples into independent single-source subproblems as per Section III. We focus on one such subproblem corresponding to a fixed source index i. A. Average-Cost Bellman Equation (SMDP) Fix a multiplier λ ∈ R. For the weighted AoI cost, the expected cumulative cost incurred over a decision stage when scheduling source j admits the closed-form expressions given in (4)–(3). The corresponding average-cost optimality equation is given by [17]: n o
hi (vi ) = (1 − p) hi (vi + 1) + min Qi,i (vi ), Qi,m (vi ) , (17) where Qi,i and Qi,m are given in (16). We show that the Bellman equation (17) admits a threshold structure: there exists a threshold Ti (λ) such that it is optimal to schedule source i when vi ≥ Ti (λ) and the competing source m otherwise.
hi (vi ) = (1 − p) hi (vi + 1) + min Qi,i (vi ), min Qi,j (vi ) . j̸=i
(16) The term (1 − p)hi (vi + 1) represents the continuation B. Computing the threshold and average cost value under transmission failure, which occurs with probability In this section we suggest a numerical method to compute 1 − p regardless of the chosen action. In that case, the AoI the optimal threshold of the single source problem. deterministically increases by one. Since this transition is action-independent, the corresponding term appears outside Theorem 1 (Threshold structure and characterization). Fix a source index i and multiplier λ ∈ R. Consider the correthe minimization. The action-dependent terms are X (i) sponding two-action SMDP Bellman equation (17), where the ppl hi (l), j = i, gi (vi , ei ) + (λ − θ(λ))Li + competing action is denoted by m ̸= i. Then the optimal policy i X l≥L Qi,j (vi ) ≜ is of threshold type: there exists a threshold Ti (λ) ∈ Z≥0 such (j) ppl hi (vi + l), j ̸= i. gi (vi , ej ) − θ(λ)Lj + that ( l≥Lj em , Li ≤ vi < Ti (λ), ⋆ Here, ek denotes the unit scheduling vector that selects source πi (vi ) = (18) ei , vi ≥ Ti (λ). k. The scalar θ(λ) denotes the optimal average cost of the single-source problem for a fixed multiplier λ. The multiplier Ti (λ) is given by λ can be interpreted as a penalty you pay to associated with θ(λ) Lm − 1 Li Ti (λ) = − − . (19) scheduling source i. αi 2p p
5
Proof. See Appendix C
Algorithm 1: Fixed-point iteration to compute Ti (λ) Input: i, λ, m ̸= i, (p, αi , Li , Lm ), β ∈ (0, 1), θ(λ)(0) , ε > 0 Output: Ti (λ) and θ(λ) n ← 0; repeat (n) θ(λ)(n) Li Lm −1 Ti ← − − ; α 2p p
Theorem 1 shows that the threshold Ti (λ) is determined by the (unknown) average cost θ(λ). We now derive a second relation between θ(λ) and Ti (λ) that enables efficient computation of both quantities for a fixed multiplier λ. From Theorem 1 and (17), we can write for all vi ≥ Li as hi (vi ) = fi,1 (vi ) − θ(λ)fi,2 (vi ), (20) where fi,1 and fi,2 are functions independent of θ(λ). In particular, for the region vi ≥ Ti (λ), we have αi Li Li fi,1 (vi ) = vi , fi,2 (vi ) = . (21) p p Next, consider the region Li ≤ vi < Ti (λ), where the threshold policy schedules the competing source m. Define c(vi ) := Ti (λ) − vi , so c(vi ) ≥ 1 in this region. The Bellman equation (17) reduces to hi (vi ) =(1 − p) hi (vi + 1) + (αi vi − θ(λ))Lm + αi w(Lm )+ X (m) ppl hi (vi + l),
i
Compute fi,1 (·),fi,2 (·)using (23)–(24); (n) θ̄(λ)(n) ← θ(λ) Ti using (25); θ(λ)(n+1) ← β θ(λ)(n) + (1 − β) θ̄(λ)(n) ; n ← n + 1; until |θλ(n+1) − θ(λ)(n) | ≤ ε; (n−1) Ti (λ) ← Ti ; θ(λ) ← θ(λ)(n) ;
V. L AGRANGE I NDEX POLICY A. Dual update via average activation fractions
For a fixed multiplier λ, the dual problem (10) decomposes into N independent single-source SMDPs, each solved as in l≥Lm Section IV. To solve the outer maximization over λ in (10), (22) we update λ using bisection method. The P derivative of the Since Ti (λ) is the threshold, the term hi (vi +l) must be treated N Lagrangian with respect to λ is given by ( i=1 µi (λ) − 1), differently depending on whether vi + l < Ti (λ) or vi + l ≥ where µi (λ) denotes the long-run fraction of time (in slots) Ti (λ). For l ≥ c(v) we have vi + l ≥ Ti (λ), so hi (vi + l) is during which source i is scheduled under the single-flow affine. Substituting into the Bellman equation and collecting optimal policy for multiplier λ. the coefficients of θ(λ) gives the recursions for fi,1 (·) and To compute µi (λ), we consider the policy πi∗ in (18) and fi,2 (·) in the region Li ≤ vi < Ti (λ). evaluate the long run fraction of time for which the action i fi,1 (vi ) = αi vi Lm + αi w(Lm ) + (1 − p) fi,1 (vi + 1)+ is chosen. This is done as follows; The one-step cost function X X (m) αi Li (m) ( pl fi,1 (vi + l) + pl (vi + l), is modified to p 1, vi ≥ Ti (λ) ∗ Lm ≤l≤c(v) l>c(v) ĝi (vi , πi (v)) = (26) (23) 0, Li ≤ vi < Ti (λ) and and we consider the policy evaluation equation fi,2 (vi ) = Lm + (1 − p) fi,2 (vi + 1)+ πi∗ πi∗ ′ ∗ A (v ) = (ĝ (v , π (λ)) − µ (v)) L + E[A (27) i i i i i X X i i i (vi )] (m) (k) Li pl fi,2 (vi + l) + pl . (24) where Aπi∗ (·) is the bias function and v ′ is the next state to i i p Lk ≤l≤c(v) l>c(v) which the process transitions. From equation (21) and the recursions (23)–(24) we uniquely From (27), we can write for all v ≥ Li , determine fi,1 (vi ) and fi,2 (vi ) for all vi ≥ Li . Finally, we π∗ Ai i (vi ) = Ai,1 (vi ) − µi (λ) Ai,2 (vi ), (28) obtain a closed-form expression for θ(λ) using (20); where A and A are independent of µ (λ). Substituting i,1 i,2 i θ(λ) = (28) into (27) we get linear recursions for Ai,1 and Ai,2 over P (i) p λLi + p l≥Li pl fi,1 (l) + αi w(Li ) + αi Li (1 − p) the region Li ≤ vi < Ti (λ), with boundary conditions for . P vi ≥ Ti (λ) given by, Ai,1 (vi ) = Ai,2 (vi ) = Lpi . Finally, we (i) p2 l≥Li pl fi,2 (l) get the activation fraction in closed form (25) P (i) l≥Li pl Ai,1 (l) The equations (19) and (25) define an implicit relationship µi (λ) = P . (29) (i) between the threshold Ti (λ) and the unknown average cost l≥Li pl Ai,2 (l) θ(λ). We compute (Ti (λ), θλ ) via a fixed-point iteration as Having computed µi (λ) policies for a fixed multiplier λ, shown in Algorithm 1. we update λ to solve the outer maximization in (10) using Lemma 3 (Monotonicity in λ). For each source i, the bisection method as given in Algorithm 2. threshold Ti (λ) and the corresponding average cost θ(λ) are Remark 1 (On existence of an exact multiplier). In general, nondecreasing functions of the multiplier λ. That is, for any there may not exist a multiplier λ⋆ such that λ1 ≤ λ2 , N X Ti (λ1 ) ≤ Ti (λ2 ) and θ(λ1 ) ≤ θ(λ2 ). µi (λ⋆ ) = 1. i=1
Proof. The proof is provided in Appendix D.
This is due to the P discrete nature of the actions, which makes N the mapping λ 7→ i=1 µi (λ) piecewise constant and possibly
6
for heterogeneous sources derived in [9]. Figure 3 compares the NSRP, Greedy, Scaled Greedy, and proposed Lagrange index policies as the channel reliability varies. As p increases, all policies improve; however, the Lagrange index policy consistently achieves the lowest long-run average weighted AoI across the range of reliabilities. Figures 4, 5, and 6 examine the impact of update-length heterogeneity, system scaling, and weight asymmetry, respectively. In each case, the left subplots (Figures 4a, 5a, and 6a) correspond to unreliable channels (p < 1) and compare NSRP, Lagrange index, Greedy, and Scaled Greedy policies, where the proposed policy consistently performs best. The right subplots (Figures 4b, 5b, and Figure 6b corresponds to the reliable channel case (p = 1) and additionally includes the Whittle index policy. In this regime, the proposed Lagrange index policy consistently outperforms or closely matches the Whittle index policy across all considered scenarios, demonstrating its effectiveness even in settings where Whittle indices are available. Importantly, while the Whittle index policy is currently characterized only for the reliable channel case, the Lagrange index framework naturally extends to unreliable channels (p < 1), where no Whittle index characterization is yet available.
discontinuous. Consequently, the relaxed constraint may not be met with equality for any single value of λ. Nevertheless, there exist multipliers λ⋆− and λ⋆+ such that N N X X µi (λ⋆− ) < 1 and µi (λ⋆+ ) > 1, i=1
i=1
which ensures that the dual optimality condition is satisfied. The resulting multiplier is therefore dual optimal. However, since the feasible set of the original problem does not satisfy a strict interior condition, a nonzero dual gap may exist between the primal and dual problems. The activation fractions satisfy a monotonicity property: as λ increases, each µi (λ) decreases, which makes bisection algorithm particularly effective. B. Lagrange index policy Having obtained the optimal multiplier λ⋆ , we define the Lagrange index for each source i at state vi as γi (vi ) ≜ Qi,i (vi ) − Qi,m (vi ), (30) which measures the incremental cost incurred by serving source i over competing action. The resulting scheduling policy selects, at each decision instant, the source with the smallest Lagrange index given in (15). For classical restless bandit problems formulated as discrete-time MDPs, Lagrange index policies are known to be asymptotically optimal as N increases [13]. Such guarantees have not been established for semi-Markov decision processes (SMDPs). We adopt the Lagrange index policy as a heuristic and evaluate it numerically, where it consistently outperforms the NSRP policy in [11]. Algorithm 2: Compute Lagrange index Input: {Li }N i=1 , p, λlow , λhigh , ε Output: λ⋆ , {γi (·)}N i=1 repeat λlow + λhigh λ← ; 2 Compute T1 (λ), . . . , TN (λ) using Algorithm 1; Obtain µ1 (λ), . . . , µN (λ) using (29); P if N i=1 µi (λ) − 1 < 0 then λhigh ← λ;
Fig. 3: Simulation results under varying channel reliability. The network has N = 10 sources split evenly into two classes: Class 1 with (Li , αi ) = (2, 5) and Class 2 with (Li , αi ) = (50, 1). The common channel reliability varies over p ∈ {0.2, 0.3, . . . , 0.8}. VII. C ONCLUSION In this paper, we developed a Lagrange index heuristic to minimize the weighted average AoI. The problem was formulated as a RMAB with SMDP dynamics. We proposed an heuristic based on the Lagrange index policy. We showed that the proposed policy outperforms both the NSRP in [11] and a scaled greedy policy, demonstrating that structural analysis translates into tangible performance gains. For the weighted AoI model, we established key structural properties, most notably threshold behavior and leveraged them to derive efficient algorithms to compute the Lagrange indices. Beyond the specific AoI setting, the proposed framework extends naturally to a broader class of RMAB problems with SMDP dynamics, thereby expanding the scope of index-based control beyond standard discrete-time formulations. Future work will consider
else λlow ← λ; until |λhigh − λlow | < ε; λlow + λhigh λ⋆ ← ; 2 for i = 1 to N do γi (·) ← Qi,i (·) − Qi,j (·); return λ⋆ , {γi (·)}N i=1 ;
VI. N UMERICAL R ESULTS We compare the proposed Lagrange index policy with NSRP [11], Greedy, Scaled Greedy, and the Whittle index policy. The Greedy policy selects the flow with the largest AoI, while Scaled Greedy selects arg maxi αi vi . Under NSRP, a probability mass function over sources is obtained by solving the optimization problem in [11], and a source is selected randomly according to this distribution. For reliable channels (p = 1), we additionally compare with the Whittle index policy
7
(a) p = 0.5
(b) p = 1
(a) p = 0.7
Fig. 6: Average weighted AoI versus α2 . We consider N = 10 flows, with five class–1 sources having (L1 , α1 ) = (2, 12) and five class–2 sources having (L2 , α2 ) = (15, α2 ), where α2 ∈ {1, 3, 5, 7, 9}. The left panel corresponds to p = 0.7, and the right panel to p = 1. The Whittle index and Lagrange index policies achieve nearly identical performance.
Fig. 4: Average weighted AoI versus update-length heterogeneity. We consider N = 2 sources with (L1 , α1 ) = (2, 5) and (L2 , α2 ) = (L2 , 1), where L2 ∈ {2, 10, 50, 100, 150}. The left panel corresponds to p = 0.5, where the greedy and scaled greedy policies achieve identical performance. The right panel corresponds to p = 1, where the greedy, scaled greedy, and Whittle index policies acheive identical performance.
(a) p = 0.7
(b) p = 1
[8] V. Tripathi and E. Modiano, “A whittle index approach to minimizing functions of age of information,” IEEE/ACM Transactions on Networking, vol. 32, no. 6, pp. 5144–5158, 2024. [9] V. Tripathi, L. Ballotta, L. Carlone, and E. Modiano, “Computation and communication co-design for real-time monitoring and control in multiagent systems,” in 2021 19th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pp. 1– 8, 2021. [10] B. Zhou and W. Saad, “Minimum age of information in the internet of things with non-uniform status packet sizes,” IEEE Transactions on Wireless Communications, vol. 19, no. 3, pp. 1933–1947, 2020. [11] Z. Zhao, V. Tripathi, and I. Kadota, “Optimizing age of information in networks with large and small updates,” in 2025 23rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), pp. 1–8, 2025. [12] I. M. Verloop, “Asymptotically optimal priority policies for indexable and nonindexable restless bandits,” The Annals of Applied Probability, vol. 26, no. 4, pp. 1947–1995, 2016. [13] N. Gast, B. Gaujal, and C. Yan, “Linear program-based policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality,” Mathematics of Operations Research, vol. 49, p. 2468–2491, Nov. 2024. [14] K. Avrachenkov, V. S. Borkar, and P. Shah, “Lagrangian index policy for restless bandits with average reward,” arXiv preprint arXiv:2412.12641, 2024. [15] D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 3rd ed., 2007. [16] S. M. Ross, Applied Probability Models with Optimization Applications. New York: Dover Publications, 1992. [17] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. USA: John Wiley & Sons, Inc., 1st ed., 1994. [18] L. I. Sennott, Stochastic dynamic programming and the control of queueing systems. John Wiley & Sons, 1998. [19] M. Shaked and J. G. Shanthikumar, Stochastic orders. Springer, 2007.
(b) p = 1
Fig. 5: Average cost versus the number of sources. We consider two classes with an equal number of sources in each class. The total number of sources is N ∈ {2, 10, 20, 30}. Class– 1 sources have (L1 , α1 ) = (2, 5), and class–2 sources have (L2 , α2 ) = (25, 1). The left panel corresponds to p = 0.7, and the right panel to p = 1. The Whittle index and Lagrange index policies achieve identical performance.
systems with switching and alternative update-generation models, building on the structural foundations developed here. R EFERENCES [1] M. Tubaishat and S. Madria, “Sensor networks: an overview,” IEEE Potentials, vol. 22, no. 2, pp. 20–23, 2003. [2] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in 2011 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, pp. 350–358, 2011. [3] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?,” in 2012 Proceedings IEEE INFOCOM, pp. 2731–2735, 2012. [4] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” Foundations and Trends in Networking, vol. 12, pp. 162–259, 11 2017. [5] V. Tripathi, I. Kadota, E. Tal, M. S. Rahman, A. Warren, S. Karaman, and E. Modiano, “Wiswarm: Age-of-information-based wireless networking for collaborative teams of uavs,” in IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pp. 1–10, IEEE, 2023. [6] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1183– 1210, 2021. [7] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” IEEE/ACM Transactions on Networking, vol. 26, no. 6, pp. 2637–2650, 2018.
A PPENDIX A. Proof of Lemma 1 Proof. Step 1: Convergence of RVI. Consider the single–flow SMDP under a fixed multiplier λ. Let π (i) denote the stationary policy that schedules flow i at every decision stage. Under this policy, the AoI process {v(k)} evolves as follows: ( v + 1, with probability (1 − p), v→ (i) l ≥ Li , with probability pl . The state space is {Li , Li + 1, . . . }.
8
Thus h(k+1) is nondecreasing.
Since from any state v ≥ Li there is positive probability of (i) transitioning to any state l ≥ Li with pl > 0, the induced Markov chain is irreducible on its state space. We now establish positive recurrence using a Foster–Lyapunov drift argument. Consider the Lyapunov function V (v) = v. The conditional drift satisfies E[v(k + 1) − v(k) | v(k) = v] X (i) pl (l − v) = (1 − p)(1) +
By induction, all iterates are nondecreasing. Since RVI converges pointwise (up to a constant), and monotonicity is preserved under limits, the limiting bias function hi is nondecreasing. B. Proof of Lemma 2 Proof. We first consider the corresponding discounted-cost problem with discount factor β ∈ (0, 1). Let Viβ (v) denote the discounted value function. The Bellman equation can be written as n o Viβ (v) = (1 − p)βViβ (v + 1) + min Qβi,i (v), min Qβi,j (v) ,
l≥Li
= (1 − p) + Li − (1 − p) − vp. P P (i) (i) Since l≥Li pl = p and l≥Li pl l = Li − (1 − p), the drift simplifies to E[v(k + 1) − v(k) | v(k) = v] = Li − pv. For sufficiently large v, the drift is strictly negative. Therefore, the Markov chain satisfies the Foster–Lyapunov condition and is positive recurrent. Hence the induced Markov Chain under the policy π (i) is unichain. Since the one–stage cost is nonnegative in v [18], the average cost under π is finite. Under this unichain condition and boundedness of the relative value differences, standard SMDP results imply that Relative Value Iteration (RVI) converges (up to an additive constant) to a solution hi of (16) [18]. Step 2: Monotonicity of the iterates. We prove by induction that v1 ≤ v2 =⇒ h(k) (v1 ) ≤ h(k) (v2 ), Base case: h(0) ≡ 0 is nondecreasing.
j̸=i
where X (i) β pl Vi (l), gi (v, ei ) + λLi + β l≥L β i X (j) β Qi,j (v) = pl Vi (v + l), gi (v, ej ) + β
For competing actions j ̸= i, and let m = arg minj̸=i Lj , the immediate cost term satisfies gi (v, ej ) = αi (vLj + w(Lj )) , where w(Lj ) is increasing in Lj . Since, Lm ≤ Lj , then gi (v, em ) ≤ gi (v, ej ), and X (j) β pl Vi (v + l).
∀k.
l≥Lj
Consider the ratio of the corresponding stage-duration probability mass functions: l−2 (j) pl Lj −2 l ≥ Lj . = l−2 pLj −Lm (1 − p)−(Lj −Lm ) , (m) pl Lm −2 Using the factorial representation of the binomial coefficients, l−2 Lj −Lm −1 Y (Lm − 2)! Lj −2 = (l − Lm − k), l−2 (Lj − 2)! L −2
Case 1: j = i. X (i) (k) Qhi,i (v) = gi (v, ei ) + (λ − θ)Li + pl h(k) (l). l≥Li
m
(k)
v1 ≤ v2 =⇒ Qhi,i (v1 ) ≤ Qhi,i (v2 ). Case 2: j ̸= i. X (j) (k) Qhi,j (v) = gi (v, ej ) − θLj + pl h(k) (v + l). l≥Lj
The term −θLj is constant in v. Since gi (v, ej ) is nondecreasing in v and v 7→ v + l is increasing, the induction hypothesis implies v1 ≤ v2 =⇒ h(k) (v1 + l) ≤ h(k) (v2 + l), ∀l. Taking expectation preserves order, hence
E Viβ (v + S (m) ) ≤ E Viβ (v + S (j) ) ,
(k)
Qhi,j (v1 ) ≤ Qhi,j (v2 ). Since v 7→ v ′ is increasing and h(k) is nondecreasing, (k)
(k)
v1 ≤ v2 =⇒ Qhi,j (v1 ) ≤ Qhi,j (v2 ), Taking minima preserves order, hence (T h(k) )(v1 ) ≤ (T h(k) )(v2 ). So, h(k+1) (v1 ) ≤ h(k+1) (v2 ).
k=0
which is strictly increasing in l over the support l ≥ Lj . Hence, {S (j) } is increasing in likelihood ratio order. It follows that S (m) ≤lr S (j) ⇒ S (m) ≤st S (j) , see, [19]. The monotonicity of the discounted value function follows by the same order-preserving dynamic programming argument used for the average-cost Bellman operator. The only modification is the multiplicative factor β ∈ (0, 1) applied to continuation values, which preserves inequalities. Hence the Bellman operator remains monotone, and the discounted value function is nondecreasing in v. Since Viβ (·) is nondecreasing, stochastic ordering preservesi the expectation, yielding h h i
The last two terms are independent of v. Since gi (v, ei ) is nondecreasing in v, it follows that
(k)
j ̸= i.
l≥Lj
Induction step: Assume h(k) is nondecreasing. Let v1 ≤ v2 . The stage cost gi (v, a) is nondecreasing in v. We verify monotonicity separately for the two types of actions.
(k)
j = i,
which establishes the desired inequality. Hence, for every β ∈ (0, 1), Qβi,m (vi ) ≤ Qβi,j (vi ), ∀vi , ∀j ̸= i, where m ∈ arg minj̸=i Lj . Thus, in the discounted problem, whenever flow i is not scheduled, it is optimal to select the competing flow with the smallest expected stage duration. Finally, by Blackwell optimality (see [17]), if a stationary policy is optimal for
∀j.
9
all discount factors sufficiently close to 1, then it is also optimal for the average-cost problem. Since the dominance of action m holds uniformly in v and for all β, the same action remains optimal in the average-cost SMDP. This completes the proof.
Hence the optimal policy is of threshold type. D. Proof of Lemma 3 Proof. For any fixed threshold policy T , let θT (λ) denote the long-run average cost obtained when threshold T is used under multiplier λ. Under a fixed threshold policy, the multiplier λ enters the average cost only through the penalty term associated with transmissions. Since the average transmission rate under any threshold policy is nonnegative, it follows that θT (λ) is nondecreasing in λ. Hence, for any λ1 ≤ λ2 , θT (λ1 ) ≤ θT (λ2 ), ∀T. Now, the optimal average cost is obtained by minimizing over all feasible thresholds: θ(λ) = min θT (λ).
C. Proof of Theorem 1 Proof. Fix λ and flow index i. Let m ̸= i denote any competing action. We use a one–step look ahead argument and the optimality principle [15]. Step 1: Cost of scheduling flow i. Suppose that at state v we schedule flow i, and thereafter continue scheduling flow i at every decision stage. The corresponding cost-to-go satisfies Ci (v) = (αi v + λ − θλ )Li + αi w(Li ) X (i) pl hi (l). + (1 − p)hi (v + 1) +
T
Therefore, θ(λ1 ) = min θT (λ1 ) ≤ min θT (λ2 ) = θ(λ2 ),
l≥Li
Scheduling of only flow i admits the affine solution αi Li θλ Li hi (x) = x− , x ≥ Ti (λ), p p up to an additive constant.
T
T
which proves that θ(λ) is nondecreasing in λ. Next, from the threshold characterization, θ(λ) Lm − 1 Li Ti (λ) = − . (31) − αi 2p p Since θ(λ) is nondecreasing in λ, the quantity inside the ceiling operator in (31) is also nondecreasing in λ. The ceiling function preserves monotonicity, and therefore Ti (λ1 ) ≤ Ti (λ2 ), λ1 ≤ λ2 . Hence, both θ(λ) and Ti (λ) are nondecreasing in λ.
Step 2: One–step look ahead to flow m. Now consider a deviating policy that schedules flow m at state v for exactly one decision epoch and then switches permanently to scheduling flow i. The corresponding cost-to-go is Cm (v) = (αi v − θλ )Lm + αi w(Lm ) X (m) + (1 − p)hi (v + 1) + pl hi (v + l). l≥Lm
Step 3: Comparison. Scheduling flow i is optimal at state v if Ci (v) − Cm (v) ≤ 0. The common continuation term (1 − p)hi (v + 1) cancels. Substituting the affine form of hi (·) and simplifying yields a linear inequality in v of the form Lm − 1 Li θλ − . − v≥ αi 2p p Define θλ Lm − 1 Li Ti (λ) = − − . αi 2p p Then for all v ≥ Ti (λ), Ci (v) ≤ Cm (v). Step 4: Invariance and optimality. For v ≥ Ti (λ), if flow m is scheduled, the next state equals v + 1 with probability (1 − p) or v + l for some l ≥ Lm . In all cases, the next state is at least v, and hence remains in the region [Ti,m (λ), ∞). Thus, once v ≥ Ti,m (λ), any one–step lookahead to action m cannot improve the cost, and the process remains in the region where scheduling i is better. By the one–step deviation principle for average cost [15], no profitable deviation exists for v ≥ Ti (λ). we conclude that for all v ≥ Ti (λ), scheduling flow i is optimal, whereas for v < Ti (λ) scheduling flow m ̸= i is optimal.
10