A Whittle Index Approach to Minimizing Functions of Age of Information

I. INTRODUCTION

• For general functions of AoI, stationary randomized policies can be arbitrarily worse than simple heuristic policies, whereas for linear AoI a stationary randomized policy is factor-2 optimal.Source: §I · p. 1
• Nonlinear age costs characterize how dissatisfaction depends on data staleness and arise in networked control and state-estimation settings, –[19].For LTI systems, prior work connects minimizing estimation error and transmission cost to minimizing a non-decreasing age-cost function for one source.Source: §I · p. 1
• The objective is to schedule updates from N sources over a wireless broadcast network to minimize the sum of their time-average general non-decreasing AoI costs.The cost functions can differ across sources.Source: §I · p. 1
• The Whittle Index approach uses a restless multi-armed bandit formulation to seek low-complexity scheduling policies with good performance.The paper considers examples such as logarithmic and indicator costs.Source: §I · p. 2, Figure 1 · p. 2
• Prior work on general age costs with reliable channels developed a high-complexity algorithm and found that an optimal policy is periodic; this work also considers unreliable channels and derives stronger structural properties, [13].The properties suggest why the Whittle Index heuristic may perform close to optimally.Source: §I · p. 2

II. MODEL

• Only one source can transmit in each time-slot because of interference, and each update takes one slot to send.Sources can generate fresh updates at will.Source: §II · p. 2
• A source’s age increases by one unless it is scheduled and its transmission succeeds, in which case its age resets to one.Transmission success is modeled by a Bernoulli variable with source-specific reliability.Source: §II · p. 2
• Each source has a positive non-decreasing age-cost function, and the scheduler seeks a causal policy minimizing the sum of the sources’ average costs.The cost for each source depends on its age process under the policy and channel processes.Source: §II · pp. 2–3

III. RESTLESS MULTI-ARMED BANDIT FORMULATION

• The restless multi-armed bandit formulation models each source as an arm with active and inactive state transitions, an age-based cost, and a shared constraint of activating only one arm per slot.The objective is to minimize long-term time-average cost.Source: §III · p. 3
• The arms are restless because their states continue evolving while inactive, so the problem cannot be reduced to a standard multi-armed bandit formulation.Whittle Index policies offer a low-complexity heuristic when the restless problem is indexable.Source: §III · p. 3
• For general age costs, stationary randomized policies can have unbounded cost even when a simple round-robin policy has bounded cost.The example uses two identical sources with cost f(x) = 3x and reliable channels.Source: §III · p. 3
• Max-Weight performance bounds rely on a factor-2-optimal stationary randomized policy for linear AoI, a property that does not hold for general age costs.The paper therefore says similar performance bounds cannot be developed for the general-cost problem using this approach.Source: §III · p. 3
• The Whittle Index policy is exactly optimal for two sources with reliable channels, including sources with different cost functions.The paper establishes indexability and derives the policy using the restless multi-armed bandit formulation.Source: §III · p. 3

IV. RELIABLE CHANNELS

• The decoupled problem is a single arm with a non-decreasing cost and a positive charge for activation, solved using dynamic programming.With zero activation charge, always activating is optimal; the analysis therefore considers strictly positive charges.Source: §IV · p. 4
• The decoupled problem's optimal policy is a stationary threshold policy: activate when age reaches H, and otherwise let the arm rest.If no suitable H exists, the optimal policy is to never activate the arm.Source: §IV · p. 4
• The decoupled problem is indexable: as activation charge C increases, the states where activation is optimal shrink monotonically from all states to none.This property permits construction of a Whittle-index policy.Source: §IV · p. 4
• The Whittle index is the activation charge that makes activating and resting equally desirable in a state, and the index is non-decreasing with age.The paper uses these indices to define its Whittle Index Policy.Source: §IV · p. 4
• For reliable channels and two sources, the Whittle index policy is exactly optimal, including finite asymmetric settings.The authors describe this as an atypical result because restless-bandit optimality results are typically symmetric or asymptotic.Source: §IV · pp. 4–5

• For reliable channels, every state-action pair on a shortest-length optimal cycle satisfies the strong-switch-type property.Source: A. Properties of an Optimal Policy · p. 5
• For reliable channels and up to three sources, an optimal stationary policy can satisfy the strong-switch-type property throughout the state space, and every strong-switch-type policy is an index policy.Source: A. Properties of an Optimal Policy · p. 5
• Strong-switch-type policies are equivalent to index policies regardless of channel connectivity, and the authors leave a general constant-factor guarantee for Whittle policies open.Source: A. Properties of an Optimal Policy · p. 6
• With reliable channels and up to three sources, there exists a stationary optimal policy that is an index policy.Source: A. Properties of an Optimal Policy · p. 6
• For N=2, the Whittle Index policy is optimal, whereas an example at N=4 shows it is only close to optimal.Source: A. Properties of an Optimal Policy · p. 6

V. UNRELIABLE CHANNELS

• Monotonicity alone does not ensure finite average cost with unreliable channels, so the analysis imposes a bounded-cost condition on age costs.The paper gives a single-source example with f(a) = 3a and success probability 0.5, where transmitting every slot still yields infinite expected average cost.Source: §V · p. 6
• The decoupled arm has age A(t), resets to 1 after a successful active transmission, increases by 1 after failure, and increases by 1 when inactive.The active transition succeeds with probability p and fails with probability 1 − p.Source: §V · p. 6
• The decoupled problem’s optimal policy is a stationary threshold: activate when A(t) ≥ H and rest otherwise, or never activate if no such H exists.Source: §V · p. 6
• As p approaches 1, the decoupled threshold policy and Whittle index reduce to their reliable-channel counterparts.For positive weighted linear AoI costs, the index functions correspond to the policy in, which is optimal for symmetric weights and channel probabilities.Source: §V · pp. 6–7
• The decoupled problem is indexable, with W(h) defined as the infimum activation charge that makes activating and resting equally desirable in state h.Source: §V · p. 7

Two-source simulations

• The two-source study tests three cost-function sets, each with reliable and unreliable channels.The functions and channel probabilities vary across settings A1–C2.Source: §VI · p. 7
• For two sources, the Whittle index policy matched the optimal cost with reliable channels and was very close to it with unreliable channels.Table I covers the costs of the Whittle index and optimal dynamic-programming policies for two sources.Source: Table I · p. 7, §VI · p. 7

More-than-two-source simulations

• The larger-source comparisons include three- and four-source settings with both reliable and unreliable channels.The paper reports results in Table II for more than two sources.Source: Table II · p. 7, §VI · p. 7
• In settings D1 and E1 costs matched, but F1 had a small performance gap, showing that the Whittle index policy is not always optimal.The dynamic-programming policy in F1 followed a cyclic pattern satisfying the strong-switch-type property and differed from the Whittle index policy.Source: §VI · p. 7
• Whittle index computation scales linearly in space and time with source count, while dynamic programming grows exponentially and becomes progressively harder.The authors report that the Whittle policy was close to optimal in every simulated setting.Source: §VI · pp. 7–8

VII. APPLICATIONS

• The framework is applied to two remote-monitoring and control problems as examples where optimizing general functions of Age of Information arises naturally.Source: §VII · p. 8

A. Monitoring LTI systems

• The monitor must schedule among N LTI systems because wireless interference allows it to observe only one system per time slot.The systems evolve independently with zero-mean Gaussian noise whose increments are independent across sources.Source: A. Monitoring LTI systems · p. 8
• Monitoring error is defined using the monitor’s maximum-likelihood estimate of each system’s state based on past observations.Source: A. Monitoring LTI systems · p. 8
• The paper relates expected monitoring error after Δ unobserved slots to a function of AoI, making error minimization equivalent to minimizing functions of AoI.The expected-error relation is stated for a system last observed at time τ.Source: A. Monitoring LTI systems · p. 8
• The resulting AoI cost functions are monotonically increasing, so the Whittle index approach applies to this monitoring problem.Source: A. Monitoring LTI systems · p. 8
• The rate at which the AoI cost increases depends on the largest eigenvalue of the system matrix: inside the unit circle it is slower than linear, outside it is faster, and on it is linear.Source: A. Monitoring LTI systems · p. 8

B. Monitoring Markov Chains

• The setting comprises N symmetric two-state Markov chains, with only one chain observable in any time slot.Each chain’s state distribution is represented as a probability vector over states 0 and 1.Source: B. Monitoring Markov Chains · p. 8
• Monitoring error measures divergence between the estimated distribution and the actual chain state, with KL divergence and total variation distance discussed.Source: B. Monitoring Markov Chains · pp. 8–9
• Theorem 10 relates expected monitoring error to the number of time slots since the chain was last observed.The relation is stated for a chain last observed at time τ and evaluated at time τ + Δ.Source: B. Monitoring Markov Chains · p. 9
• For Markov chains, minimizing monitoring error is equivalent to minimizing functions of AoI, and the functions are monotonically increasing, enabling the Whittle index approach.Source: B. Monitoring Markov Chains · p. 9
• In the KL-divergence case, monitoring error is the entropy of the estimated distribution, which represents base-station uncertainty and increases as the chain remains unobserved.Source: B. Monitoring Markov Chains · p. 9

VIII. CONCLUSION

• For two sources with reliable channels, the Whittle index policy is exactly optimal.The paper also derives structural properties of optimal policies that suggest the index policy may perform close to optimally in general.Source: §VIII · p. 9
• Proving constant-factor optimality of the Whittle index policy in general remains future work.The paper also identifies stochastic arrivals and unknown, possibly time-varying age functions as extensions to consider.Source: §VIII · p. 9

A. Proof of Theorem 1

• For the decoupled arm, a threshold H satisfying (27) yields an optimal threshold policy; if no such H exists, never activating is optimal.Source: A. Proof of Theorem 1 · pp. 10–11

B. Proof of Theorem 2

• The decoupled problem is indexable: its optimal threshold is non-decreasing in activation charge, and the Whittle index in state h is W(h+1).At C = W(h+1), activating and resting are equally desirable in state h.Source: B. Proof of Theorem 2 · p. 11

C. Proof of Theorem 4

• Assuming a violating pair, the proof relabels it as x1 and xk with d1 = 1 and dk = 2, then substitutes d1 at xk to reach yk+1 ≤ x2.With reliable channels, following the original actions afterward preserves the element-wise age bound against the corresponding original states.Source: C. Proof of Theorem 4 · p. 11
• The substitution creates a cycle of length k + T − 1 whose later age vectors are no greater than the corresponding original ones.The original action sequence over a full period returns the system to x1 because every source is activated at least once during that period.Source: C. Proof of Theorem 4 · p. 11
• A cyclic permutation and repeated action segment also produce a cycle of length 2T − k + 1, with specified states matching or bounded above by original cycle states.Source: C. Proof of Theorem 4 · pp. 11–12
• Comparing the constructed cycles with the optimal cycle forces the relevant inequalities to be tight; otherwise the original cycle is not optimal.Source: C. Proof of Theorem 4 · p. 12
• If the inequalities are tight, the actions d2 through dk form a shorter cycle with the same cost, contradicting the assumed minimum length.Thus no violating pair can exist, and the shortest optimal cycle satisfies the strong-switch property.Source: C. Proof of Theorem 4 · pp. 11–12

D. Proof of Theorem 5

• For N ≤ 3, a strong-switch-type optimal cycle can be extended to a stationary optimal policy with that property over the entire state-space.The extension works because the conflicting-action scenario never occurs for two or three sources.Source: D. Proof of Theorem 5 · pp. 12–13

E. Proof of Theorem 6

• By induction, every strong-switch-type policy for the reliable-channel functions-of-age problem can be represented as an index policy.The induction starts from the single-source case, where both policy types are monotone threshold policies.Source: E. Proof of Theorem 6 · pp. 13–14

1) Case 1:

• Given W1(1) ≥ W2(k) and W2(k + 1) > W1(1), the Whittle index policy schedules source 1 k times, then source 2 once, repeats this sequence, and is optimal.Source: 1) Case 1 · p. 14

2) Case 2:

• For k = 1, W2(2) > W1(1) and W1(2) > W2(1) make the Whittle policy schedule each source once, then repeat.Source: 2) Case 2 · p. 14

F. Proof of Theorem 3

• For N = 2 and reliable channels, the Whittle Index policy is exactly optimal.The proof shows that two-source index policies have a cycle in which one source is scheduled repeatedly and the other once, or each source is scheduled once per cycle.Source: 2) Case 2 · p. 14, F. Proof of Theorem 3 · p. 14

G. Proof of Theorem 7

• If a threshold H satisfies condition (11), its threshold policy is optimal; if no such H exists, never activating the arm is optimal.In the latter case, the proof uses boundedness and monotonicity of W and f to verify the Bellman equations.Source: G. Proof of Theorem 7 · pp. 15–16

H. Proof of Theorem 8

• The optimal threshold is non-decreasing in activation charge, and C = W(h + 1) is the Whittle index in state h.When W is non-decreasing but not strictly increasing, the proof chooses the smallest h satisfying the threshold condition.Source: H. Proof of Theorem 8 · p. 16

I. Proof of Theorem 9

• With no additional updates and i.i.d. Gaussian increments, the state-estimation error at time Δ is a zero-mean multivariate normal random variable.The setup assumes the base station knows the process state at an earlier time but not the intervening increments.Source: §I · p. 16
• Positive semidefiniteness of the covariance matrices implies nonnegative trace, establishing that each covariance-based AoI cost function is non-decreasing.The proof uses this trace property to show f_i(∆+1) ≥ f_i(∆).Source: §I · p. 16

J. Proof of Theorem 10

• For a symmetric Markov chain, monitoring error measured by KL divergence grows monotonically with AoI.The proof establishes this result using the convexity of x log(x).Source: J. Proof of Theorem 10 · p. 17
• The cited inequality establishes that monitoring error, when measured using total variation (TV) distance, grows monotonically with the age of information (AoI).The argument notes that 2x(1 − x) is concave for all x.Source: J. Proof of Theorem 10 · p. 17