1
Age of Information Optimization for Status Updates in Integrated Sensing and Communication Systems
arXiv:2605.24714v1 [cs.IT] 23 May 2026
Marco Zanni, Mohamad Assaad, Touraj Soleymani
Abstract—In this paper, we study age of information (AoI) optimization for status updating in an integrated sensing and communication (ISAC) system. We consider a discrete-time architecture in which a base station interacts with a physical environment and a remote monitor, and at each time slot can operate in one of three modes: sensing, communication, or joint sensing and communication. Each mode is unreliable and incurs a different operational cost. The objective is to minimize a discounted infinite-horizon cost that combines the AoI at the monitor with action-dependent sensing and communication costs. For the single source scenario, we formulate the problem as a Markov decision process with a two-dimensional AoI state and prove that the optimal stationary policy admits an ordered threshold structure in the AoI state space. Since the AoI evolves over an infinite space, we truncate the state space to reduce complexity and rigorously bound the resulting error. The analysis analytically determines the truncation size needed to keep the error below a given threshold. For the multi-source scenario, we formulate the scheduling problem as a restless multi-armed bandit. We develop both a Whittle index policy and an approximate Whittle index policy for scheduling under two different regimes, one where indexability is guaranteed, and one where it is not. Numerical results illustrate the structure of the optimal policy in the single-source case and show that the proposed approximate Whittle index policy performs comparably to the Whittle index policy in the indexable regime, while remaining effective beyond it. Index Terms—age of information, real-time monitoring, networks, status updating, integrated sensing and communication.
I. I NTRODUCTION Real-time remote monitoring systems are a fundamental component of modern cyber-physical infrastructures, allowing remote controllers, operators, and decision-makers to keep awareness of dynamic physical processes. Their importance spans a wide range of applications, including industrial automation, smart transportation, environmental surveillance, and networked control. In such systems, status information is collected from one or more sources and delivered over possibly unreliable communication channels, so that decisions can be made on the basis of the most recent available observations. However, successful delivery alone is not sufficient: the information available at the monitor must also be timely, since outdated status updates may provide an inaccurate representation of the current system state and degrade the quality of subsequent decisions. Marco Zanni ([email protected]) and Mohamad Assaad ([email protected]) are with the Laboratory of Signals and Systems, CentraleSupélec, University of Paris-Saclay, 91190 Gif-sur-Yvette, France. Touraj Soleymani is with the City St George’s School of Science and Technology, University of London, London EC1V 0HB, United Kingdom ([email protected]).
A natural metric to quantify this notion of timeliness is the age of information (AoI), introduced in [1]. If h(t) denotes the generation time of the most recently received update available at a receiver at time t, then the AoI is defined as ∆(t) = t − h(t). The AoI measures how much time has passed since the generation of the freshest update currently available at the destination. Since it directly measures information staleness at the receiver, the AoI has become a standard timeliness metric in status updating systems, and it has been extensively studied in queueing systems, scheduling problems, wireless networks, and remote estimation settings [2]–[4]. In these settings, AoI serves as a natural framework for analyzing trade-offs among update frequency, transmission reliability, and resource usage. The AoI has also stimulated the development of several related metrics that extend the notion of timeliness. The age of incorrect information (AoII) was introduced in [5] to account for both staleness and correctness: the AoII grows only when the receiver’s estimate of the current system state is incorrect. Likewise, the value of information (VoI) considers how much a new observation improves performance in a control or estimation loop [6], [7] emphasizes that information should be evaluated not only by whether it is delivered, but also by how useful it is for the task of interest. To this day, the AoI remains the canonical and most straightforward metric when the main objective is to control information freshness. Among the many problems studied in the AoI literature, scheduling takes a central role. When several users share limited communication resources, the system must decide which user should be served at each time in order to maintain freshness across the network. This question has been investigated in several settings, including broadcast networks, random access systems, and more general AoI optimization problems [8]– [13]. In these multi-user settings, the exact dynamic programming solution is often computationally out of reach, which makes low-complexity scheduling rules particularly attractive. A prominent approach in this direction is given by restless multi-armed bandit formulations and Whittle index policies. Following the seminal work [14], Whittle index policies have received significant attention in wireless scheduling and, more recently, in the AoI literature. In practice, at each time step a priority index is assigned to every user, and this induces a low-complexity policy where the scheduler can address the users with the highest priority. This heuristic is generally well-performing. In the AoI context, Whittle index policies have been used for broadcast scheduling, random access, federated learning, and query-aware uplink systems [8]–[13].
2
Their performance is not only empirical: in some settings they have also been shown to be asymptotically optimal or even globally optimal, as in [4], [15]. The simplicity and strong performance of the Whittle index policy makes it interesting to analyze in our model. The present paper is motivated by a setting in which freshness is determined by two mechanisms: information about the current state of a physical process must first be acquired, and then delivered to a remote monitor. The monitor cannot directly observe the physical process, but has to rely on a central base station that collects status information on its behalf. This is quite frequent in practice since the monitor cannot have a view of the whole environment required for monitoring. In particular, the base station acquires information about the current state of the physical process through a sensing mechanism, e.g. by sending a radar signal to collect updated observations about the environment useful for the physical process. In such a system, the scheduler at the base station must decide not only when to communicate, but also when to refresh its own local knowledge of the process. The base station can operate in three modes: pure sensing, pure communication, and a joint mode in which it acquires fresh status information and communicates previously acquired information within the same slot. The decision maker must choose among these three competing actions with different costs and success probabilities. Real-world applications can be, for instance: Remote navigation: a remote operator or controller must track the state of a vehicle and of its surrounding environment, including nearby obstacles. The monitored physical process is the navigation scene, while the base station acquires fresh information through onboard or roadside sensors, and then delivers the acquired status to the remote monitor. • Industrial robotic cells: a control room must monitor the state of a production area where mobile robots and human workers coexist. The physical process includes the positions and operating conditions of these elements, while the base station obtains fresh observations from sensors before reporting them to the monitor.
•
An integrated sensing and communication (ISAC) architecture provides a natural operational setting for this problem, since the same platform is used both to acquire and to deliver information [16]–[19]. Much of the existing ISAC literature focuses on physical-layer metrics such as waveform design, beamforming, interference management, estimation error, and throughput. Our goal is different in that we do not seek to optimize the physical layer operation of an ISAC system, but to characterize the AoI-optimal scheduling rule. AoI and scheduling ISAC layers have received less attention in the literature. Recent examples include AoI optimization in multiUAV, UAV-enabled, and air-ground ISAC systems [20]–[23]. [24] applies AoI metrics to an ISAC setting, but focuses on the physical layer of the system and applies it specifically to vehicular networks. A preliminary two-action formulation of our freshness problem was considered in [25], where the base station can only choose between separate sensing and
Figure 1. Representative example of an ISAC architecture for remotely monitoring a ground vehicle.
communication operations. The present paper studies a threeaction model by introducing a joint sensing and communication action, which is motivated by the recent settings in ISAC technology in which a transmitter can transmit a communication signal that can be useful to collect sensing information. Unlike the two-mode scenario, the third joint communication-and-sensing mode fundamentally changes the problem geometry, making standard submodularity approaches inapplicable. Furthermore, this paper extends the analysis to multiple physical process–monitor pairs. In this paper, we study AoI optimization for status updates in such an architecture. We consider a discrete-time system composed of a source, an ISAC-enabled base station, and a remote monitor (see Figure 1 for a representative example). The source can track the state of an underlying physical process, while the monitor cannot, and must rely on status information collected by the base station. At every time step, the base station can perform sensing to acquire fresh information from the source about the current state of the process, communicate previously acquired status information to the monitor, or perform sensing and communication simultaneously. These operations are unreliable and incur different costs. To capture the resulting trade-off, we formulate a discounted infinite-horizon Markov decision process whose state is the pair formed by the AoI at the monitor and the AoI at the base station. The objective is to minimize a long-term cost that combines information staleness at the monitor with action costs. We also extend the analysis to a multiple processmonitor setting in which one base station must schedule several monitored processes. A. Contributions and Organization The main contribution of this paper is a structural and algorithmic study of the above problem in both single processmonitor and multiple process-monitor pairs scenarios. •
For the single process-monitor case, we show that the optimal stationary policy admits an ordered switching structure in the AoI state space. This yields a policy described by two switching thresholds. We also quantify the error induced by truncating the unbounded state space and derive a simple closed-form criterion for selecting the truncation level for the numerical computation of the optimal policy. The proof of the threshold structure of the optimal policy significantly differs from standard
3
AoI and/or MDP formulations, since the optimal value function is not submodular in our problem. • We then extend the analysis to a multiple process-monitor pairs scenario in which one base station must share its sensing and communication capability among several subsystems. This leads to a restless multi-armed bandit formulation. By introducing an idle action and applying a Lagrangian relaxation, we obtain a relaxed singlearm problem that enables the construction of Whittletype scheduling rules. We provide a sufficient condition under which the relaxed problem is Whittle-indexable, so that an exact Whittle index policy can be defined. In contrast to classical AoI scheduling formulations, each arm involves two coupled AoI variables and three active sensing-communication modes, so the scheduling rule must jointly determine which sources to activate and which ISAC action to choose. • Finally, we develop an approximate Whittle index policy based on linear interpolation. This approximate construction is computationally attractive, can be used in non-indexable regimes, and comes with an explicit approximation bound. Numerical results illustrate both the threshold geometry of the optimal single process-monitor policy and the effectiveness of the proposed heuristic policies in the multiple process-monitor pairs scenario. The remainder of the paper is organized as follows. Section II introduces the system model and formulates the optimization problem. Section III studies the single-source scenario and establishes the structure of the optimal policy together with the truncation bound. Section IV addresses the multi-source scenario and develops the index-based scheduling policies. Section V presents numerical results. Section VI concludes the paper.
communication are modeled through success probabilities and operational costs. In particular, the joint action is treated as a single effective mode: when it succeeds, it both delivers the previously sensed information and refreshes the base station information; when it fails, neither update is performed. This abstraction allows us to isolate the effect of the additional reset mechanism on the AoI dynamics. A. System Model Let Zk denote the state of the physical process/source at time k. At the beginning of each slot, the base station selects an action uk ∈ {sense, comm, joint}, corresponding, respectively, to sensing the process/source, transmitting previously acquired information to the monitor, or performing both operations simultaneously. These three actions incur fixed costs c0 ≥ 0, c1 ≥ 0, and c2 ≥ 0. The key difference among the three modes lies in how information is handled within a slot. A sensing action attempts to acquire the current process/source state. A communication action attempts to forward the most recent state information already available at the base station. A joint sensing and communication action combines these two operations: during the same slot, the base station transmits its previously available estimate while also attempting to collect a fresh measurement of the source. Let Xk denote the measurement obtained by the base station at time k, whenever sensing is performed successfully. If uk = sense, the base station sends a radar signal in order to collect fresh information regarding the state of the process. The sensing operation succeeds with probability λ0 ∈ (0, 1), and the sensing outcome satisfies
II. P ROBLEM F ORMULATION
Pr(Xk = Zk | Zk , uk = sense) = λ0 ,
We study a discrete-time remote monitoring system supported by an integrated sensing and communication (ISAC) infrastructure. The architecture consists of three entities: a physical process, an ISAC-enabled base station, and a remote monitor. The monitor aims to track the evolution of the process state, useful for the monitor that has a limited sensing capability and does not have a good view/observation of the environment. The monitor must rely on information provided by the base station. At each time slot, the base station selects one of three operating modes: sensing the current process state, transmitting previously acquired status information to the monitor, or performing sensing and communication simultaneously (i.e; acquiring new sensing while transmitting the previous sensing status to the monitor). The transmission channels are lossy, so the chosen operation may fail. The objective is to design a scheduling policy for the base station that balances information freshness and operational cost, namely by keeping the AoI at the monitor low while accounting for sensing and communication costs. Our focus is on the decision and scheduling layer of an ISAC monitoring system, rather than on physical layer design. Accordingly, sensing, communication, and joint sensing and
Pr(Xk = ∅ | Zk , uk = sense) = 1 − λ0 . The base station stores the most recent successfully sensed state. Let Z̃k denote the state information stored at the base station after the ISAC action at time k. If uk = comm, the base station attempts to transmit the most recent locally available estimate, denoted by Z̃k−1 , to the remote monitor. The communication operation succeeds with probability λ1 ∈ (0, 1). Let Yk denote the received packet at the remote monitor. Then Pr(Yk = Z̃k−1 | Z̃k−1 , uk = comm) = λ1 , Pr(Yk = ∅ | Z̃k−1 , uk = comm) = 1 − λ1 . If uk = joint, the base station transmits the estimate available from the previous slot while simultaneously senses the current source state. In this case, the joint operation succeeds with probability λ2 ∈ (0, 1), and the outcome satisfies Pr(Xk = Zk , Yk = Z̃k−1 | Zk , Z̃k−1 , uk = joint) = λ2 , Pr(Xk = ∅, Yk = ∅ | Zk , Z̃k−1 , uk = joint) = 1 − λ2 .
4
The state information stored at the base station evolves according to ( Xk , if uk ∈ {sense, joint} and Xk ̸= ∅, Z̃k = Z̃k−1 , otherwise. Let Ẑk denote the state estimate available at the remote monitor after the ISAC action at time k. The monitor can be updated only when an action involving communication is selected and the transmission succeeds. Its state therefore evolves according to ( Yk , if uk ∈ {comm, joint} and Yk ̸= ∅, Ẑk = Ẑk−1 , otherwise. In particular, under a pure sensing action the monitor receives no packet and keeps its previous estimate. For notational convenience, we also introduce the binary outcome variable ηk ∈ {succ, fail}, which indicates whether the selected operation at time k is successful. Its conditional distribution is given by λ0 , if uk = sense, (1) Pr(ηk = succ | uk ) = λ1 , if uk = comm, λ2 , if uk = joint, with Pr(ηk = fail | uk ) = 1 − Pr(ηk = succ | uk ). This model separates three distinct uses of the ISAC resource: information acquisition through sensing, information delivery through communication, and the combined execution of the two within the same slot. Throughout the paper, we assume that λ2 ≤ λ0 ≤ λ1 and c0 ≤ c1 ≤ c2 . These assumptions reflect the fact that communication is typically more reliable than sensing because of coding and retransmission mechanisms, whereas simultaneous sensing and communication is generally the most demanding operating mode in terms of both reliability and cost. B. Freshness Metric We track information freshness separately at the remote monitor and at the base station. For i ∈ {m, b}, where m and b index the remote monitor and the base station, let αki denote the AoI at time k before the ISAC action, and αki + denote the AoI at time k after the ISAC action. These variables quantify the freshness of the state information Ẑk available at the remote monitor and Z̃k stored at the base station. The post-action AoI values depend on which operation is selected and on whether that operation succeeds. In particular, when the selected action is successful, the pair b (AoIm k+ , AoIk+ ) evolves as follows: m if uk = sense, (AoIk , 0), m b b b (AoIk+ , AoIk+ ) = (AoIk , AoIk ), if uk = comm, (2) (AoIbk , 0), if uk = joint. If the selected operation is unsuccessful, no fresh information is acquired or delivered, and therefore b m b (AoIm k+ , AoIk+ ) = (AoIk , AoIk ).
Finally, between time instants k+ and k + 1, the AoI increases by one unit at both entities, so that AoIik+1 = AoIik+ + 1. This representation highlights the fact that the remote monitor and the base station may carry information with different freshness levels, depending on whether the selected action refreshes local information, delivered information, or both. C. Performance Criterion and Optimization Problem The dynamics introduced above induce a discounted infinite-horizon Markov decision process. At each time k, the ISAC system selects an action uk . For compactness, we use the conventions αki := AoIik , uk = 0 ⇔ uk = sense, uk = 1 ⇔ uk = comm, uk = 2 ⇔ uk = joint, ηk = 0 ⇔ ηk = fail, and ηk = 1 ⇔ ηk = succ. The state at time k is then Sk = (αkm , αkb ). We associate with each state-action pair a one-step cost composed of a freshness term at the remote monitor and an action-dependent operational cost. Specifically, the stage cost is defined as g(Sk , uk ) = αkm + c0 1{uk = 0} + c1 1{uk = 1} + c2 1{uk = 2}.
(3)
Starting from an initial state S0 , the objective is to find a policy π that minimizes the expected discounted cumulative cost over an infinite horizon, namely "∞ # X min E γ k g(Sk , uk ) , (4) π∈P
k=0
subject to the state dynamics defined in the previous subsections, where γ is a discount factor, and P is the set of admissible stationary policies. We denote by π ∗ an optimal policy. The problem in (4) captures the trade-off of the considered ISAC system. On the one hand, frequent updates improve freshness at the remote monitor by reducing the age of the information on which it relies. On the other hand, each operating mode consumes resources and is affected by a different reliability level. The optimization problem seeks a policy that coordinates sensing and communication decisions while balancing freshness performance against sensing and communication costs. For the structural analysis developed in the next section, we restrict the discount factor γ to the following admissible regime. Assumption. The discount factor γ is chosen such that 0<γ≤
λ2 . λ0 λ1 + λ2 (1 − λ1 )
(5)
Remark. This condition is used only to establish the monotonicity of the action-difference function ∆∗02 in Lemma 9. It is not a physical constraint on the sensing or communication links, and it is not required for the MDP formulation, for the existence of an optimal stationary policy, or for the
5
numerical computation of the optimal policy. Numerically, the ordered threshold structure is also observed in several sets of parameters violating this sufficient condition. III. S INGLE PROCESS - MONITOR S CENARIO In this section, we specialize the model in (4) to the single process-monitor case. We study the structure of the optimal stationary policy, with the goal of showing that it has a switching-threshold form in the AoI state space. We then find an upper bound for the error caused by the truncation of the state space, which is inevitable for the offline computation of the optimal policy.
optimal value function. These properties are subsequently used to control directional increments of the optimal value function and to analyze the action-difference functions associated with the three available actions. The goal is to prove that the actiondifference functions satisfy suitable single-crossing properties. Finally, we combine these findings to prove that the optimal policy admits a threshold structure. Remark. Unlike several standard AoI problems, the present model does not naturally admit a proof based on submodularity of the optimal value function, which makes the derivation more delicate. The argument developed below relies instead on monotonicity and concavity properties of the Bellman operator and suitable bounds on directional increments.
A. State Transitions and Reachable State Space We first characterize the state transitions and the reachable area of the AoI state space. With the conventions introduced in Section II, the single process-monitor system is a discounted infinite-horizon MDP with state Sk = (αkm , αkb ) and action space U = {0, 1, 2}. The state dynamics follow directly from the AoI update rules. In particular, m if (uk , ηk ) = (0, 1), (αk + 1, 1), m b (α + 1, α + 1), if (uk , ηk ) = (0, 0), k k (αb + 1, αb + 1), if (u , η ) = (1, 1), k k m b k k (αk+1 , αk+1 )= m b (αk + 1, αk + 1), if (uk , ηk ) = (1, 0), b (α if (uk , ηk ) = (2, 1), k + 1, 1), m b (αk + 1, αk + 1), if (uk , ηk ) = (2, 0). (6) We make the process start at the initial state S0 = (1, 1)1 . From this, only a triangular subset of N2 is reachable: every transition preserves αkm ≥ αkb for any time step k. Accordingly, the analysis can be restricted to the reachable state space S := {(αm , αb ) ∈ N2 : αm ≥ αb ≥ 1}. Theorem 1. The problem in (4) admits an optimal stationary deterministic policy π ∗ with a switching-threshold structure. Specifically, there exist two functions τ1 , τ2 : N → N0 ∪{+∞} such that m b sense, if α ≤ τ1 (α ), ∗ m b b u (α , α ) = joint, if τ1 (α ) < αm ≤ τ2 (αb ), comm, if αm > τ2 (αb ). for all (αm , αb ) ∈ S, where τ1 (αb ) is nondecreasing in αb and τ1 (αb ) ≤ τ2 (αb ) for every αb . Theorem 1 shows that the optimal policy has an ordered structure: along each fixed value of the base station AoI, the optimal action can only move in the order 0 → 2 → 1. Thus, the optimal rule is described by two switching boundaries. The derivation proceeds in several steps. We first present the space in which the Bellman operator can be defined. Then, we derive structural properties of the Bellman operator and of the 1 One could also fix the initial state at (0,0), in which case the state transitions would all lead to (1,1) in the following time step, for whatever action u and outcome η. The results would be identical, up to a shift in the indices.
B. Proof of Theorem 1 We begin by introducing a setting in which the Bellman operator can be analyzed in a rigorous way. Since the MDP is unbounded, it is necessary to define a suitable norm and work on the corresponding Banach space. This allows us to show that the Bellman operator is well defined and contractive, and therefore admits a unique fixed point, which coincides with the optimal value function. Convergence to a fixed point first ensures that the optimal value function exists, and second lets us prove some of its key properties through value iteration. m Let ρ ∈ (1, γ −1 ), and define w(αm , αb ) := ρα , the norm ∥V ∥w :=
|V (αm , αb )| , m b (αm ,αb )∈S w(α , α ) sup
and the Banach space Bw := {V : S → R : ∥V ∥w < ∞}. For V ∈ Bw , define the Bellman operator T V (S) =
min u∈{0,1,2}
Qu (S),
Qu (S) := g(S, u) + γE [V (S ′ ) | S, u] . Since the next monitor AoI always satisfies αm′ ≤ αm + 1, we have E w(S ′ ) | S, u ≤ ρ w(S), ∀S ∈ S, ∀u ∈ {0, 1, 2}. Moreover, g(S, u) ≤ αm + c2 ≤ Cw w(S) for some finite constant Cw > 0, because supn≥1 (n+c2 )ρ−n < ∞. Therefore T : Bw → Bw and, for every V, W ∈ Bw , ∥T V − T W ∥w ≤ γρ ∥V − W ∥w . Since γρ < 1, T is a contraction on Bw . We work on the Banach space Bw , on which the Bellman operator is a contracting operator. This lets us exploit a value iteration algorithm for which T has a unique fixed point, which is the optimal value function V ∗ . We can now write the action-value function Q∗u (S) = gu (S, u) + γE V ∗ (S ′ )|S, u (7) and the Bellman equation V ∗ (S) =
min u∈{0,1,2}
Q∗u (S).
(8)
6
We now prove some structural properties of the optimal value function by defining a class of functions that is invariant under the Bellman operator. These properties will be used later on to analyze the behavior of the action-value functions Q∗u . Let F be the class of functions V : S → R with these properties: • V is coordinatewise nondecreasing; m b m • V (α , α ) is discretely concave in α for every fixed b α . Lemma 1. Let V ∈ F be coordinatewise nondecreasing. Then T V is also coordinatewise nondecreasing. Proof. For u ∈ {0, 1, 2}, write
Lemma 3. The optimal value function V ∗ belongs to F. Proof. Start value iteration from V (0) ≡ 0 ∈ F . Lemma 1 and Lemma 2 imply V (n+1) = T V (n) ∈ F whenever V (n) ∈ F. Hence V (n) ∈ F for all n ≥ 0. Pointwise convergence of V (n) to V ∗ ensures V ∗ ∈ F. 1) Marginal Value Increments: The proof of the threshold structure relies on comparing the three action-value functions Q∗0 , Q∗1 , and Q∗2 . These comparisons involve differences of the optimal value function evaluated at adjacent states. For this reason, we begin by deriving bounds on several onestep increments of V ∗ . These bounds will later be used to show that the action-difference functions satisfy singlecrossing properties. We define the following horizontal, diagonal, and vertical one-step increments:
Qu (s) = g(s, u) + γ E[V (S ′ ) | s, u]. Using the state transition in (6), we obtain Q0 (αm , αb ) = αm + c0 + γ λ0 V (αm + 1, 1) + (1 − λ0 )V (αm + 1, αb + 1) , Q1 (αm , αb ) = αm + c1 + γ λ1 V (αb + 1, αb + 1) + (1 − λ1 )V (αm + 1, αb + 1) , Q2 (αm , αb ) = αm + c2 + γ λ2 V (αb + 1, 1) + (1 − λ2 )V (αm + 1, αb + 1) .
A(αb ) := V ∗ (αb + 2, 1) − V ∗ (αb + 1, 1),
Because V is coordinatewise nondecreasing, the sum in the square bracket is coordinatewise nondecreasing for every u. Moreover, the stage cost g (αm , αb ), u = αm + cu is nondecreasing in the state. The pointwise minimum of coordinatewise nondecreasing functions is coordinatewise nondecreasing. Therefore, T V (s) = minu∈{0,1,2} Qu (s) is coordinatewise nondecreasing. Lemma 2. Let V ∈ F be discretely concave in αm . Then T V is also discretely concave in αm . Proof. Fix αb ≥ 1 and, for αm ≥ αb , define qu (αm ) := Qu (αm , αb ),
in αm . Therefore, for each u ∈ {0, 1, 2}, the sequence qu (αm + 1) − qu (αm ) is nonincreasing in αm , which means that qu is discretely concave. The pointwise minimum of discretely concave functions is discretely concave2 . Therefore, T V (αm , αb ) = minu∈{0,1,2} qu (αm ) is discretely concave in αm for every fixed αb .
u ∈ {0, 1, 2}.
Using the state transitions in (6), we write their forward differences as q0 (αm + 1) − q0 (αm )
b
∗
b
b
∗
m
∗
b
b
∗
m
(10) b
C(α , α ) := V (α + 1, α + 2) − V (α + 1, α + 1), αm ≥ αb + 1.
(11)
Lemmas 4–8 are structured as follows. Lemma 4 gives a lower bound on horizontal increments of V ∗ . Lemma 5 gives a uniform upper bound on local one-step increments. Lemma 6 identifies the optimal action on the diagonal and yields a recursion for the diagonal increment B. Finally, Lemmas 7 and 8 compare the increments A, B, and C, which will be needed to establish the monotonicity of the action-difference functions. The proofs of these lemmas are in the Appendices A–E. Lemma 4. For every αm ≥ αb ≥ 1, 1 . 1 − γ + γλ1
(12)
Proof. See Appendix A. Lemma 5. For every αm ≥ αb ≥ 1 and every (α̃m , α̃b ) ∈ S such that 0 ≤ α̃m − αm ≤ 1 and 0 ≤ α̃b − αb ≤ 1,
q1 (αm + 1) − q1 (αm )
0 ≤ V ∗ (α̃m , α̃b ) − V ∗ (αm , αb ) ≤
h = 1 + γ(1 − λ1 ) V (αm + 2, αb + 1) i − V (αm + 1, αb + 1) ,
1 . 1−γ
(13)
Proof. See Appendix B. Lemma 6. For every α ≥ 1, action 0 is optimal on the diagonal state (α, α).
q2 (αm + 1) − q2 (αm ) h = 1 + γ(1 − λ2 ) V (αm + 2, αb + 1) i − V (αm + 1, αb + 1) . m
(9) b
B(α ) := V (α + 1, α + 1) − V (α , α ), m
V ∗ (αm + 1, αb ) − V ∗ (αm , αb ) ≥
= 1 + γλ0 V (αm + 2, 1) − V (αm + 1, 1) h + γ(1 − λ0 ) V (αm + 2, αb + 1) i − V (αm + 1, αb + 1) ,
b
Proof. See Appendix C.
b
Since V is discretely concave in α , for every fixed α the differences in the square brackets are all nonincreasing
2 Here discrete concavity means f (a + 2) − 2f (a + 1) + f (a) ≤ 0. Unlike the continuous case, the pointwise minimum preserves this property on N: if h(a) = mini fi (a) and i⋆ reaches the minimum at a + 1, then 2h(a + 1) = 2fi⋆ (a + 1) ≥ fi⋆ (a) + fi⋆ (a + 2) ≥ h(a) + h(a + 2).
7
Writing the Bellman equation at (αb + 1, αb + 1) and (αb , αb ), and subtracting the latter from the former, we obtain the following recursive definition for B(αb ) which will be used in Lemmas 7 and 8: b
b
b
B(α ) = 1 + γλ0 A(α ) + γ(1 − λ0 )B(α + 1).
(14)
Lemma 7. For every αb ≥ 1, B(αb ) − A(αb ) ≤
1 1 − (1 − γ)A(αb ) < . 1 − γ + γλ0 γλ0
Lemma 8. For every αb ≥ 1 and every αm ≥ αb + 1, C(αm , αb ) ≤ B(αb + 1). Proof. See Appendix E. 2) Properties of the Action-Difference Functions: We now define the action-difference functions associated with the three available actions. Their explicit representation will be the main tool for comparing actions across the AoI state space. ∆∗02 := Q∗0 −Q∗2 ,
∆∗21 := Q∗2 −Q∗1 .
With this convention, ∆∗01 ≤ 0 means that sensing is no worse than communication, ∆∗02 ≤ 0 means that sensing is no worse than the joint action, and ∆∗21 ≤ 0 means that the joint action is no worse than communication. The idea is to show that these functions are single-crossing in the two coordinates: this leads to the single-switching structure of the optimal policy. Using (6), the action-difference functions can be written as ∆∗01 (αm , αb ) = (c0 − c1 ) + γλ0 V ∗ (αm + 1, 1) − γλ1 V ∗ (αb + 1, αb + 1) ∗
m
(16a) b
+ γ(λ1 − λ0 )V (α + 1, α + 1), ∆∗02 (αm , αb ) = (c0 − c2 ) + γλ0 V ∗ (αm + 1, 1) − γλ2 V ∗ (αb + 1, 1) + γ(λ2 − λ0 )V ∗ (αm + 1, αb + 1),
(16b)
∆∗21 (αm , αb ) = (c2 − c1 ) + γλ2 V ∗ (αb + 1, 1) − γλ1 V ∗ (αb + 1, αb + 1) ∗
m
Lemma 10. For each fixed αm , the functions ∆∗01 (αm , αb ) and ∆∗02 (αm , αb ) are nonincreasing in αb for 1 ≤ αb ≤ αm − 1. Proof. See Appendix G.
(15)
Proof. See Appendix D.
∆∗01 := Q∗0 −Q∗1 ,
two actions are nonincreasing in αb . Therefore, a larger base station AoI makes sensing relatively more attractive, which will imply that the lower threshold τ1 (αb ) is nondecreasing.
(16c) b
+ γ(λ1 − λ2 )V (α + 1, α + 1). The next step is to show that the action comparisons vary monotonically over the AoI state space. For fixed αb , we prove that the action-difference functions are nondecreasing in αm . Hence, once sensing becomes worse than another action as the monitor AoI grows, it cannot become better again. This is the single-crossing property that leads to thresholds along each horizontal row of the state space. Lemma 9. For each fixed αb , the functions ∆∗01 (αm , αb ), ∆∗02 (αm , αb ), and ∆∗21 (αm , αb ) are nondecreasing in αm . Proof. See Appendix F. We also need to understand how the sensing region changes when the base station AoI increases. The following lemma shows that the differences comparing sensing with the other
The logical structure is now the following. Lemmas 4–8 provide the increment bounds needed to prove the single-crossing properties of Lemmas 9 and 10. Lemma 9 implies that, for each fixed αb , the sensing region is an initial segment and the communication region is a terminal segment in αm . The remaining states therefore form the intermediate joint region. Lemma 10 then implies that the lower sensing threshold is nondecreasing in αb . 3) Threshold Structure of the Optimal Policy: We collect the properties derived from the previous lemmas to prove the optimal policy structure established in Theorem 1. The singlecrossing properties stated above imply that, for every fixed value of the base station AoI, the regions in which the three actions are optimal must appear in an ordered way. This yields the desired switching-threshold structure and allows us to show that the lower switching boundary is nondecreasing. Proof of Theorem 1. For each state (αm , αb ), define 0, if ∆∗01 (αm , αb ) ≤ 0 and ∆∗02 (αm , αb ) ≤ 0, u∗ (αm , αb ) = 1, if ∆∗01 (αm , αb ) > 0 and ∆∗21 (αm , αb ) ≥ 0, 2, otherwise. This rule is optimal. Indeed, if ∆∗01 ≤ 0 and ∆∗02 ≤ 0, then Q∗0 ≤ Q∗1 and Q∗0 ≤ Q∗2 , so action 0 is optimal. If ∆∗01 > 0 and ∆∗21 ≥ 0, then Q∗1 < Q∗0 and Q∗1 ≤ Q∗2 , so action 1 is optimal. In all remaining cases action 2 is optimal: if ∆∗01 ≤ 0 and the first case fails, then necessarily ∆∗02 > 0, hence Q∗2 < Q∗0 ≤ Q∗1 ; if ∆∗01 > 0 and the second case fails, then necessarily ∆∗21 < 0, hence Q∗2 < Q∗1 < Q∗0 . Now fix αb ∈ N and define A0 (αb ) := {αm ≥ αb : ∆∗01 (αm , αb ) ≤ 0, ∆∗02 (αm , αb ) ≤ 0}, A1 (αb ) := {αm ≥ αb : ∆∗01 (αm , αb ) > 0, ∆∗21 (αm , αb ) ≥ 0}. By construction, action 0 is optimal on A0 (αb ), action 1 is optimal on A1 (αb ), and action 2 is optimal on the complement of A0 (αb ) ∪ A1 (αb ) in {αm ≥ αb }. By Lemma 6, αb ∈ A0 (αb ), so A0 (αb ) is nonempty. Moreover, by Lemma 9, both ∆∗01 and ∆∗02 are nondecreasing in αm . Hence, if αm ∈ A0 (αb ) and α̃m satisfies αb ≤ α̃m ≤ αm , then ∆∗01 (α̃m , αb ) ≤ ∆∗01 (αm , αb ) ≤ 0, ∆∗02 (α̃m , αb ) ≤ ∆∗02 (αm , αb ) ≤ 0,
8
so α̃m ∈ A0 (αb ). Therefore A0 (αb ) is an initial segment of {αm ≥ αb }. Similarly, by Lemma 9, both ∆∗01 and ∆∗21 are nondecreasing in αm . Hence, if αm ∈ A1 (αb ) and α̃m ≥ αm , then ∆∗01 (α̃m , αb ) ≥ ∆∗01 (αm , αb ) > 0, ∆∗21 (α̃m , αb ) ≥ ∆∗21 (αm , αb ) ≥ 0, so α̃m ∈ A1 (αb ). Therefore A1 (αb ) is a terminal segment of {αm ≥ αb }. We may thus define τ1 (αb ) := sup A0 (αb ) ∈ N0 ∪ {+∞}, ( inf A1 (αb ) − 1, if A1 (αb ) ̸= ∅, τ2 (αb ) := +∞, if A1 (αb ) = ∅. b
b
Since A0 (α ) is an initial segment and A1 (α ) is a terminal segment, we have A0 (αb ) = {αm ≥ αb : αm ≤ τ1 (αb )}
of the model may lead to a policy that is different from the optimal policy of the original unbounded problem. In this section, we explicitly quantify the error induced by truncation and derive a possible closed-form criterion for selecting the truncation level. This shows that the truncated model maintains a controlled approximation of the original MDP, and provides a justification for the numerical procedure used to compute the optimal policy. Precisely, the goal of the following analysis is to bound the value error introduced by the clipped approximation of the original unbounded dynamic program. For a fixed A ∈ N, define the truncated state space (αm , αb ) ∈ SA := {(αm , αb ) : 1 ≤ αb ≤ αm ≤ A}. Whenever the state exceeds the boundary in the truncated model, it is clipped to A. Let dπ (s) be the discounted occupancy measure of state s under a policy π, namely dπ (s) := (1 − γ)
A1 (αb ) = {αm ≥ αb : αm > τ2 (αb )}. Because the two sets are disjoint, τ1 (αb ) ≤ τ2 (αb ). Hence m b 0, if α ≤ τ1 (α ), ∗ m b b u (α , α ) = 2, if τ1 (α ) < αm ≤ τ2 (αb ), 1, if αm > τ2 (αb ). It remains to prove that τ1 is nondecreasing in αb . Let αm ∈ A0 (αb ) with αm ≥ αb + 1. By Lemma 10, ∆∗01 (αm , αb + 1) ≤ ∆∗01 (αm , αb ) ≤ 0, ∆∗02 (αm , αb + 1) ≤ ∆∗02 (αm , αb ) ≤ 0, so αm ∈ A0 (αb + 1). Therefore A0 (αb ) \ {αb } ⊆ A0 (αb + 1). Since Lemma 6 gives αb + 1 ∈ A0 (αb + 1), and both sets are initial segments, it follows that b
b
τ1 (α ) ≤ τ1 (α + 1).
∞ X
π
γ k Pr(Sk = s | S0 = (1, 1)) .
k=0
More generally, P forπ any subset B of the state space, let dπ (B) := s∈B d (s). For every i ∈ N, define Bi := {(αm , αb ) : αm ≥ A + i}. Lemma 11. For every i ∈ N, the discounted occupancy measure satisfies: dπ (Bi ) ≤ γ A+i−1 . Proof. From the state transition in (6) αm can increase by at most one unit per slot under any action. Therefore, reaching Bi from (1, 1) requires at least A + i − 1 time steps. It follows that dπ (Bi ) = (1 − γ) ≤ (1 − γ)
∞ X
π
γ k Pr Sk ∈ Bi | S0 = (1, 1)
k=0 ∞ X
γ k = γ A+i−1 .
k=A+i−1
Thus τ1 is nondecreasing in αb . C. Truncation of the State Set Since the state space of the single-source MDP is unbounded, the optimal solution requires to solve the Bellman equation on an infinite amount of states. In practical implementations, this is clearly an impossible task. For this reason, one must truncate the state space, and solve the resulting truncated MDP. The truncated model then works as follows: • Offline, the Bellman equation is modified at the boundary: whenever a transition would lead outside the truncated state space, the corresponding value function is replaced by its clipped boundary counterpart. • Online, whenever the state exceeds the truncation value, it gets projected back to the boundary. In this way, the problem in (4) can be approximated by a finite-state MDP, which is solvable. However, such truncation
Now let Vπ∞ ∗ (1, 1) be the value of the unbounded MDP at (1, 1), and let VπAA (1, 1) be the value of the truncated MDP at the same initial state, where π ∗ and πA are optimal for the unbounded and truncated models, respectively. Theorem 2. The error due to the truncation satisfies A Vπ∞ ∗ (1, 1) − Vπ (1, 1) ≤ A
γA . (1 − γ)2
ext Proof. Let πA be the extension of πA to the unbounded model defined by ext πA (αm , αb ) = πA min{αm , A}, min{αb , A} . ext Since πA is feasible for the unbounded MDP, ∞ Vπ∞ ∗ (1, 1) ≤ Vπ ext (1, 1). A
9
Coupling the unbounded and truncated processes under the same realization of the channel outcomes, A ∞ A Vπ∞ ∗ (1, 1) − Vπ (1, 1) ≤ Vπ ext (1, 1) − Vπ (1, 1) A A "A∞ X =E γ k αkm − min{αkm , A} k=0
# S0 = (1, 1) =
1 X πAext d (s)(αm − A). 1−γ s∈S / A
Every reachable state satisfies αm ≥ αb , so s ∈ / SA implies αm > A. Hence ∞ X m α −A= 1{αm ≥ A + i}. i=1
Substituting into the previous expression and using Lemma 11, A Vπ∞ ∗ (1, 1) − Vπ (1, 1) ≤ A
≤
∞ 1 X πAext d (Bi ) 1 − γ i=1 ∞ 1 X A+i−1 γA γ = . 1 − γ i=1 (1 − γ)2
This closed-form bound can be directly inverted to choose the truncation level for a given tolerance. If one requires the truncation error to be at most ε, it is enough to impose γ A /(1− γ)2 ≤ ε, which leads to & ' log ε(1 − γ)2 A≥ . (17) log(γ) The value ε is a tolerance on the differencial total discounted cost. A more intuitive value is ε̂ := (1 − γ)ε, which corresponds to the tolerance on the differencial discounted cost per time slot. In other words, ε̂ is the error that, if experienced for every time slot, would lead to a total differencial discounted cost equal to ε. Note that ε̂ has the same scale as the cost function g(S, u), so it has a clear interpretation. The criterion (17) becomes & ' log ε̂(1 − γ) A≥ . (18) log(γ) Table I reports the minimum values of A satisfying (18) for different values of γ and ε̂. Table I M INIMUM TRUNCATION LEVEL A SATISFYING (18). ϵ̂ 1 5 · 10−1 10−1 5 · 10−2 10−2 5 · 10−3 10−3
γ = 0.50 1 2 5 6 8 9 11
γ = 0.70 4 6 10 12 17 19 23
γ = 0.85 12 16 26 31 41 45 55
γ = 0.90 22 29 44 51 66 73 88
γ = 0.95 59 72 104 117 149 162 194
IV. M ULTIPLE PROCESS - MONITOR PAIRS S CENARIO In this section, we study a constrained multiple processmonitor pairs scheduling problem in which a single base station must share its sensing and communication capability among several independent monitor-source pairs. In contrast to the single process-monitor case, the decision process can no longer be treated separately for each source, since the base station can actively serve only a limited number of subsystems at each time slot. The controller must therefore decide, at every time step, which subsystems should be addressed and which ISAC action should be applied to each selected subsystem. This coupling across subsystems makes the exact dynamic programming solution intractable when the number of sources grows. To model this setting, we extend the single process-monitor formulation by introducing an idle action, which represents the decision not to address a given subsystem in a given slot. This leads naturally to a constrained restless multi-armed bandit (RMAB) formulation. The key difficulty is that every subsystem (arm) keeps evolving over time, including those that are not selected, so the overall state process remains coupled through the activation constraint. A standard way to handle this difficulty is through a Lagrangian relaxation, which decouples the global scheduling problem into a family of relaxed singlearm problems. This relaxation is the basis for Whittle index policies, which assign to each subsystem a priority value and then activate the subsystems with the largest priorities. In this way, a high-dimensional scheduling problem is replaced by an offline index computation and a simple online ranking rule. Compared with standard AoI scheduling models, the relaxed single-arm problem considered here has two distinctive features. First, each subsystem state contains two coupled freshness variables, corresponding to the AoI at the monitor and at the base station. Second, each active arm has three possible active modes, with different state transitions, success probabilities, and operational costs. Therefore, the resulting index construction must account not only for whether a source should be scheduled, but also for which sensingcommunication action should be selected once the source is activated. Our analysis focuses on two regimes. First, we identify a sufficient condition under which the relaxed single-arm problem is Whittle-indexable, so that an exact Whittle index policy can be defined. Second, since this sufficient condition need not hold for all parameter values, we also develop an approximate Whittle index policy that remains computationally light and can still be used beyond the guaranteed indexable regime. The rest of the section is organized as follows. We first formulate the multi-source problem as an RMAB and derive the relaxed single-arm problem. We then study indexability and the exact Whittle index policy. Finally, we introduce an approximate index policy for the non-indexable regime. A. RMAB Formulation We consider a multi-source scenario with N total subsystems, each of which can be modeled as a single processmonitor MDP as presented in Section III. Every subsystem
10
i has its own parameters: ci0 , ci1 , ci2 , λi0 , λi1 , λi2 , and Ai for numerical implementation. A constraint forces the base station to address at most M < N sources, each with its own optimal action. To implement this constraint, we now introduce action ui = 3, which means that the subsystem i stays idle. When a subsystem stays idle, its state variables both increase by 1. The optimal policy for the base station is now a vector π = {π i }N i=1 . Furthermore, let dπ i (k) := 1 if π i (k) ∈ {0, 1, 2} and 0 if π i (k) = 3 for subsystem i and for time step k, i.e. dπi (k) = 1 if the base station addresses source i at time step k. The RMAB can be formulated as follows: ∞ N hX i X min E γk g(Ski , uik ) π
s.t.
k=0 N X
i=1
dπi (k) ≤ M,
(19) ∀k ≥ 0,
i=1
Accordingly, we define the active-idle difference functions ∆iu3 (si , W ) := Qu (si , W ) − Q3 (si , W ),
u ∈ {0, 1, 2}. (21)
By direct substitution, ∆i03 (si , W ) = ci0 + W − γλi0 V (si,+1 , W ) − V (s′i 0,W) , (22a) i i i i i,+1 ′i ∆13 (s , W ) = c1 + W − γλ1 V (s , W ) − V (s1 , W ) , (22b) i i i i i,+1 ′i ∆23 (s , W ) = c2 + W − γλ2 V (s , W ) − V (s2 , W ) . (22c) These quantities compare each active action with the idle one in the relaxed problem. In particular, if all three of them are nonnegative at a given state, then staying idle is optimal for that state. Let P i (W ) be the set of states for which the optimal action is u = idle, i.e. P i (W ) := {si : u∗,i (si ) = 3}.
where g(Ski , uik ) = αkm,i + ci0 1{uik = 0} + ci1 1{uik = 1} + ci2 1{uik = 2}.
Equivalently, P i (W ) = {si :∆i03 (si , W ) ≥ 0, ∆i13 (si , W ) ≥ 0, ∆i23 (si , W ) ≥ 0}.
B. Lagrangian Relaxation The multiple process-monitor pairs problem in (19) is computationally demanding to solve. To obtain a scheduling rule, we use a Lagrangian relaxation, which is the standard starting point for Whittle index methods. The idea is to replace the activation constraint with a scalar term in the objective function. In this way, the constraint is no longer enforced for every time step k; instead, one introduces a multiplier W that measures the value of leaving a subsystem idle. This relaxed formulation is useful because it turns the original coupled problem into a collection of local control problems, one for each subsystem. Imposing a Lagrange multiplier W , the optimization problem in (19) can be written as: "∞ # N X X k i i i min E γ g(Sk , uk ) − W 1{uk = 3} (20) π
k=0
i=1
The Lagrangian relaxation decouples the constrained RMAB into N independent discounted dynamic programs, one for each subsystem i. Let s+1 denote the state whose coordinates are those in state s increased by 1, and let s′u denote the arrival state after a successful realization of action u in state s. For a fixed subsystem i, the relaxed Bellman equation is V (si , W ) =
min u∈{0,1,2,3}
Qu (si , W ),
where Q3 (si , W ) = g(si , 3) − W + γV (si,+1 , W ), and, for u ∈ {0, 1, 2}, Qu (si , W ) = g(si , u) + γλiu V (s′i u, W ) + γ(1 − λiu )V (si,+1 , W ).
The notion of indexability is central in Whittle theory. A subsystem is said to be indexable if increasing the idle subsidy W can only enlarge the set of states in which staying idle is optimal. In other words, as passivity becomes more attractive, the system should move monotonically toward the idle action. The problem in (19) is indexable if, for any W ′ > W , P i (W ) ⊆ P i (W ′ ). If the problem is indexable, then the Whittle index is well defined: for a given state, it is the minimum value of the subsidy W for which action idle becomes optimal in that state. In mathematical terms, the Whittle index of state s in subsystem i is defined as W i (si ) := inf{W : si ∈ P i (W )}.
(23)
This index can be interpreted as a state-dependent priority value for each subsystem, and it directly induces the Whittle index policy. In practice, the Whittle index of every state of every subsystem is computed offline and stored. Then, online, at each time step, the base station observes the current state of each subsystem, retrieves the corresponding index values, and ranks the subsystems in decreasing order of priority. The base station then activates the M subsystems with the largest indices and applies to each of them the corresponding local optimal action of the relaxed single-arm problem, while the remaining N − M subsystems stay idle. In this way, the original high-dimensional scheduling problem is replaced by an offline index computation and a simple online lookup-andsorting procedure. We now state a closed-form sufficient condition under which subsystem i is indexable, so that the Whittle index policy can be used. Theorem 3. If γ≤
1 , 1 + λi1
11
then subsystem i is indexable. Proof. Fix W ′ > W . Since only the idle action depends explicitly on W , the relaxed value function is nonincreasing in W and satisfies W′ − W 0 ≤ V (s, W ) − V (s, W ′ ) ≤ , ∀s. 1−γ
Algorithm 1 Whittle index computation 1: for all states si in the state space do 2: Choose Wmin and Wmax such that si ∈ / P i (Wmin ) i i and s ∈ P (Wmax ) (0) 3: Initialization: W (0) (si ) ← Wmin , W (si ) ← Wmax 4: for k = 1, . . . , Kmax do 5: Set
Using (22), for any u ∈ {0, 1, 2} we obtain W (k) (si ) ←
∆iu3 (si , W ′ ) − ∆iu3 (si , W ) = (W ′ − W ) + γλiu
h
(k−1)
(si )
Solve the local dynamic program using W i = W (si ) 7: if si ∈ P i (W (k) (si )) then 8: W (k) (si ) ← W (k−1) (si ) (k) W (si ) ← W (k) (si ) 9: 10: else 11: W (k) (si ) ← W (k) (si ) (k) (k−1) i 12: W (si ) ← W (s ) 13: end if (k) 14: if W (si ) − W (k) (si ) < ε then 15: break 16: end if 17: end for 18: Compute 6:
(k)
V (si,+1 , W ) − V (si,+1 , W ′ ) i ′i ′ − V (s′i u , W ) − V (su , W ) ≥ (W ′ − W ) − γλiu ∥V (·, W ) − V (·, W ′ )∥∞ . An upper bound for the difference ∥V (·, W ) − V (·, W ′ )∥∞ is given by [26, Theorem 12]: ∥V (·, W ) − V (·, W ′ )∥∞ ≤
W (k−1) (si ) + W 2
W − W′ . 1−γ
(24)
Therefore, γλiu ∆iu3 (si , W ′ ) − ∆iu3 (si , W ) ≥ (W ′ − W ) 1 − . 1−γ Since λiu ≤ λi1 for all u ∈ {0, 1, 2} and γ ≤ 1/(1 + λi1 ), the right-hand side is nonnegative. Hence each ∆iu3 (si , W ) i i is nondecreasing in W . Consequently, if s ∈ P (W ), then ∆iu3 (si , W ′ ) ≥ 0 for all u ∈ {0, 1, 2}, which proves that P i (W ) ⊆ P i (W ′ ).
Now let s+1 denote the state whose coordinates are those in state s increased by 1, and let s′u denote the arrival state after a successful realization of action u in state s. At W = W i (si ), we have min ∆iu3 (si , W i (si )) = 0, u∈{0,1,2}
which directly yields the following characterization: h W i (si ) = i max γλiu V si,+1 , W i (si ) u ∈{0,1,2} i i i i − γλiu V s′i u , W (s ) − cu .
(25)
W (si ) =
We now focus on the regime in which the sufficient condition of Theorem 3 is satisfied, so that the Whittle index is well defined as in (23). In this case, the relaxed single-arm problem admits an exact Whittle index for every state, which can be used as a priority value for scheduling. Under the indexable regime, the Whittle index of each state can be numerically computed through the bisection method reported in Algorithm 1. The output of Algorithm 1 will be the Whittle index of each state si of subsystem i, up to a certain tolerance ε. The process must be repeated for every i ∈ {1, 2, . . . , N }. Online, the implementation of the Whittle index policy is done through Algorithm 2:
(k)
(si )
19: end for
Algorithm 2 Implementation of the Whittle index policy 1: for k = 0, 1, 2, . . . do 2: Observe the current state sik of each subsystem i ∈ {1, 2, . . . , N } 3: Retrieve the Whittle indices {W i (sik )}N i=1 4: Sort the indices W i (sik ) in decreasing order 5: Let Ik be the set of the M subsystems with the largest indices 6: for all i ∈ Ik do 7: Select the active action uik ∈ arg min Qiu sik , W i (sik ) u∈{0,1,2}
8:
C. Whittle Index Policy Under Indexable Regime
W (k) (si ) + W 2
end for
9: for all i ∈ / Ik do 10: Set uik ← 3 11: end for 12: Apply the action vector uk = (u1k , . . . , uN k ) 13: end for
D. Approximate Whittle Index Policy Beyond the Indexable Regime The sufficient condition for indexability presented above can be restrictive. Moreover, having a two-dimensional state space, calculating the Whittle index for all states is generally challenging. In this section, we propose a heuristic, well-performing
12
f (si ) to every state through policy that assigns an index W linear interpolation. More precisely, we first compute the index values through Algorithm 1 on a set of anchor states, namely the diagonal states and the boundary states, and then use these values to interpolate the index over the interior of the state space. The interpolated value is then used to solve the local dynamic program only once, which yields f (si ). In this way, we obtain the final approximate index W a simple index-based policy that can be computed over the whole state space and used for scheduling in a broad range of parameter regimes. This makes the policy attractive both when the sufficient indexability condition is not satisfied and, more generally, when a much faster computational procedure is needed. The offline computation method for the approximate indices is described in Algorithm 3. Online, similarly to the Whittle index policy, for every time step the base station addresses the first M subsystems with f (si ), applying Algorithm 2 to the approximate the highest W indices. Algorithm 3 Approximate Whittle index computation 1: Define Di := {(a, a) : a = 1, . . . , Ai }, B i := {(Ai , b) : b = 1, . . . , Ai }. i
i
the whole state space, and also provides a practical method when indexability is not guaranteed. In the indexable case, Theorem 4 quantifies the sensitivity of this approximation to the interpolation error. Let λimax := maxui ∈{0,1,2} {λiu }, ∀i ∈ {1, 2, . . . , N }. Theorem 4. Let the subsystem i be indexable. With reference to Algorithms 1 and 3, for the subsystem i, the approximation error satisfies: i
c i (si ) − W i (si ) . f i (si ) − W i (si ) ≤ 2γλmax W W 1−γ Proof. We refer to subsystem i, and we omit index i to simplify notations. f (s) − W (s) in our From (25) and from the definition of W heuristic policy, h f (s) − W (s) = max γλu V s+1 , W c (s) W u∈{0,1,2} i c (s) − cu − γλu V s′u , W h − max γλu V (s+1 , W (s)) u∈{0,1,2} i − γλu V (s′u , W (s)) − cu . By the triangular inequality we can write
i
2: for all s ∈ D ∪ B do 3: Find W̄ i (si ) through Algorithm 1
f (s) − W (s) ≤ γ W
f i (si ) ← W̄ i (si ) 4: Set W 5: end for
c (s) − V s+1 , W (s) V s+1 , W c (s) + V s′u , W (s) − V s′u , W h ≤ γ max λu u∈{0,1,2} c (s) − V s+1 , W (s) V s+1 , W i c (s) . + V s′u , W (s) − V s′u , W
6: for b = 1, . . . , Ai − 1 do 7: for a = b + 1, . . . , Ai − 1 do 8: Compute the linear interpolation
c i (si ) ← W f i (b, b) + a − b W f i (Ai , b) − W f i (b, b) W i A −b Solve the local dynamic program using W i =
9:
c i (si ) W 10:
Compute f i (si ) = W
max i
u ∈{0,1,2}
h
ci i s′i u , W (s )
An upper bound for both differences in the value functions is again given by (24): c (s) − V s, W (s) V s, W
c i (si ) γλiu V si,+1 , W − γλiu V
max λu
u∈{0,1,2}
− ciu
i
11: end for 12: end for
The output of Algorithm 3 is an index approximation for each state si of subsystem i, and the process must be repeated for every i ∈ {1, 2, . . . , N }. This heuristic solution computes approximate Whittle indices for the boundary states (Ai , αb,i ) c (si ) to all and (α, α) through Algorithm 1, assigns values W other states by linear interpolation, and then updates them by solving the corresponding dynamic program only once. Whenever the exact Whittle index is well defined, the index assigned to any boundary state through Algorithm 1 coincides with the real Whittle index; otherwise, it can be viewed as a heuristic subsidy score. For the inner states, f (si ) are also heuristic priority scores. This avoids the full W iterative procedure needed to compute the Whittle index over
∞
≤
c (s) − W (s) W . 1−γ
Therefore, f (s) − W (s) ≤ 2γλmax V W c (s) − V W (s) W
∞
2γλmax c W (s) − W (s) . ≤ 1−γ Remark. Theorem 4 can be leveraged to get a more formal upper bound for the interpolation error. Let H i,b be the function defined by: H i,b :=
max
a=b,...,Ai −2
W i (a + 2, b) − 2W i (a + 1, b) + W i (a, b)
for every truncated subsystem i. Since the row {(a, b) : a = b, . . . , Ai } is finite, H i,b is well defined. Now consider the interpolation c i (a, b) = W i (b, b) + a − b W i (Ai , b) − W i (b, b) , W Ai − b b ≤ a ≤ Ai .
13
One can show that i,b
c i (a, b) − W i (a, b) ≤ H (a − b)(Ai − a). W 2 Hence, by Theorem 4, the approximation produced by one Whittle update satisfies i
f i (a, b) − W i (a, b) ≤ γλmax H i,b (a − b)(Ai − a). (26) W 1−γ The bound defined in (26) is zero at the states (b, b) and (Ai , b), and is maximized at the midpoint of the interval [b, Ai ], since the factor (a−b)(Ai −a) is a concave quadratic function of a. One may want to apply this remark to optimize their heuristic solution a posteriori. For example, if the numerically computed H i,b has a high curvature for a certain b, splitting the interval [b, Ai ] for interpolation is the theoretically optimal way to minimize the error upper bound, and might lead to significant improvements.
Figure 2. Value function as a function of the monitor and base station AoIs. The value function is non-decreasing in both coordinates and exhibits a structured surface induced by the optimal policy.
V. N UMERICAL R ESULTS After providing theoretical foundations in Sections III and IV, in this section we conduct several numerical analyses to corroborate our findings, addressing both the single processmonitor and the multiple process-monitor pairs scenarios. A. Single process-monitor Scenario We begin with the single process-monitor problem, for which the analysis in Section III proves an ordered policy with two switching thresholds. The purpose of this numerical study is to show how the interaction between the monitor AoI and the base station AoI shapes the optimal three-action policy, and in particular how the state space is divided into sensing, communication, and joint sensing and communication regions. We solve a truncated version of the MDP on the triangular state space αm , αb ∈ {1, 2, . . . , A}, αb ≤ αm . The optimal value function is computed via value iteration. In the experiment reported below, we set A = 50, γ = 0.85, λ0 = 0.75, λ1 = 0.95, λ2 = 0.65, c0 = 5, c1 = 5.5, and c2 = 6. Figure 2 represents the optimal value function V ∗ over the truncated state space. The value function increases monotonically as either AoI component grows, which is consistent with the fact that stale information leads to a larger longterm cost. Moreover, the dependence on αm is stronger than that on αb , since the stage cost penalizes the monitor AoI directly, whereas the base station AoI affects performance more indirectly through the quality of the information available for future transmissions. Figure 3 shows the corresponding optimal action map. Near the diagonal, sensing is optimal, since when the monitor and the base station hold information of comparable age it is preferable to refresh the local estimate before allocating resources to transmission. By contrast, when the monitor AoI becomes sufficiently large, communication is preferred because reducing the age at the monitor becomes the priority. Between these two regimes, there exists an intermediate region in which the joint sensing and communication action is
Figure 3. Optimal ISAC action map as a function of the monitor and base station AoIs. The boundaries separating the optimal actions exhibit a threshold structure, consistent with the theoretical results.
optimal, reflecting the fact that neither pure sensing nor pure communication alone provides the best compromise. For every fixed value of αb , the optimal action evolves according to the ordered pattern 0 → 2 → 1, and the lower switching boundary follows the monotonic trend established in Section III. B. Multiple source-monitor pairs Scenario For the multiple source-monitor scenario, we evaluate the performance of our approximate Whittle index policy (AWIP) under two different regimes. In the first regime, the sufficient condition for indexability is satisfied, so that the Whittle index policy (WIP) is well defined and can be used as a benchmark. In the second regime, the sufficient condition is violated,
14
so indexability is not guaranteed. In both regimes, we also simulate: • A random policy, which selects M subsystems uniformly at random; • A greedy policy, which selects the M subsystems with the highest αm . All policies apply the local optimal active action once a subsystem is selected, i.e. the action u ∈ {0, 1, 2} that minimizes Qu in that subsystem’s state. We consider a truncated state space αm , αb ∈ {1, 2, . . . , A}, b α ≤ αm , with A = 50 for every subsystem. The local optimal value functions are computed via value iteration. We fix two classes of parameters. The first class has higher action costs and success probabilities (λ0 = 0.95, λ1 = 0.98, λ2 = 0.90, c0 = 7, c1 = 7, and c2 = 7); the second class has lower action costs and success probabilities (λ0 = 0.60, λ1 = 0.80, λ2 = 0.55, c0 = 5, c1 = 5, and c2 = 5). In our first analysis, we carry out a scalability analysis over N . The N sources are split equally in the two classes of parameters. The performance metric is the average discounted cost per source: J(N ) :=
∞ N 1−γ X kX γ g(Ski , uik ). N i=1 k=0
In the online simulations, the infinite-horizon sum is approximated by truncating the evolution at Kmax = 200, and each experiment is repeated 10000 times. We first consider a parameter configuration satisfying the sufficient condition for indexability, with γ = 0.5. In this regime, we compare WIP, AWIP, the random policy, and the greedy policy. We fix M = N/2, i.e. the base station can address at most half of the total sources. The objective is to verify that AWIP closely tracks the performance of WIP when the Whittle index is well defined, and to assess the gain provided by both index-based policies with respect to the baselines.
Figure 4. Average discounted cost per source J with varying N in the indexable regime: comparison between WIP, AWIP, the random policy, and the greedy policy. 99% confidence intervals are also displayed.
Figure 4 shows that, when the sufficient condition for indexability is satisfied, AWIP achieves a performance practically identical to that of WIP, while both clearly outperform the baselines. This supports the use of AWIP as a low-complexity
surrogate of WIP in regimes where the exact Whittle index is well defined. Offline, the computation times of the indices for the WIP and the AWIP, shown in Table II, confirm the convenience of using the interpolated indices as the truncation value A grows. Table II O FFLINE COMPUTATION TIME FOR WIP AND AWIP INDICES . A
WIP (s)
AWIP (s)
Time saving (%)
10 20 30 40 50
2.773 14.32 39.22 95.13 179.7
1.040 3.421 7.637 13.97 23.81
62.5 76.1 80.5 85.3 86.7
To complement the large-scale simulations, we also compare the proposed policies with the globally optimal policy on a smaller instance where the full truncated dynamic program associated with (19) can still be solved exactly. We consider N = 4 and M = 2, and repeat the analysis for A ∈ {10, 12, 15}. We use the same two classes of parameters as above. The global optimal value functions are computed via value iteration. Table III reports the centralized optimal cost JDP and the relative gaps of WIP, AWIP, greedy, and random policies. Table III S MALL - SCALE COMPARISON WITH THE GLOBALLY OPTIMAL CENTRALIZED POLICY. Gap vs. JDP (%) A
JDP
WIP
AWIP
Greedy
Random
10 12 15
4.354528 4.354903 4.354907
0.00 0.00 0.00
0.00 0.00 0.00
9.37 9.36 9.36
11.22 11.21 11.21
Table III shows that, in the indexable regime, both WIP and AWIP coincide with the globally optimal policy up to the displayed numerical tolerance. This confirms that the proposed approximate index captures almost all of the scheduling gain of the centralized optimal policy, while retaining the simple online structure used in the large scale simulations. We then consider a second parameter configuration in which the sufficient condition for indexability is not satisfied, with γ = 0.9. In this case, we compare AWIP with the random policy and the greedy policies. We fix M = N/5, i.e. the base station can address at most one fifth of the total sources. The purpose of this experiment is to show that AWIP remains a competitive heuristic beyond the regime covered by the sufficient condition for indexability. Figure 5 illustrates that AWIP continues to outperform the baselines when the sufficient condition for indexability is violated. This indicates that the proposed approximation is not only computationally attractive, but also effective in parameter regimes where the Whittle index might not be defined. VI. C ONCLUSIONS In this paper, we studied sensing-communication scheduling in an ISAC architecture for status updating under AoI-based
15
Figure 5. Average discounted cost per source J with varying N when the sufficient condition for indexability is violated: comparison between AWIP, the random policy, and the greedy policy. 99% confidence intervals are also displayed.
freshness objectives. We formulated the single process-monitor problem as a discounted infinite-horizon Markov decision process, and established that the optimal stationary policy admits a two-threshold structure in the AoI state space, with a monotone lower threshold. Since the AoI state space unbounded, we quantified the error induced by the truncation of the state space, providing a simple criterion for selecting the truncation level in numerical implementations. For the multiple process-monitor pairs scenario, we formulated the problem as a restless multi-armed bandit and developed scheduling policies based on the Whittle index, including a low-complexity policy with strong performance and a provable approximation bound. Lastly, we carried out numerical analyses to confirm our theoretical findings, showing the threshold geometry of the optimal single-source policy and the effectiveness of the proposed index policies in the multi-source setting. R EFERENCES [1] S. Kaul, R. D. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proceedings of IEEE INFOCOM, 2012, pp. 2731–2735. [2] R. D. Yates, Y. Sun, D. R. B. III, 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. [3] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 7492–7508, 2017. [4] S. Kriouile, M. Assaad, and A. Maatouk, “On the global optimality of Whittle’s index policy for minimizing the age of information,” IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 572–600, 2022. [5] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: An enabler of semantics-empowered communication,” IEEE Transactions on Wireless Communications, vol. 22, no. 4, pp. 2621– 2635, 2023. [6] T. Soleymani, J. S. Baras, and S. Hirche, “Value of information in feedback control: Quantification,” IEEE Transactions on Automatic Control, vol. 67, no. 7, pp. 3730–3737, 2022. [7] T. Soleymani, J. S. Baras, S. Hirche, and K. H. Johansson, “Value of information in feedback control: Global optimality,” IEEE Transactions on Automatic Control, vol. 68, no. 6, pp. 3641–3647, 2023. [8] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. H. 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. [9] J. Sun, Z. Jiang, B. Krishnamachari, S. Zhou, and Z. Niu, “Closed-form Whittle’s index-enabled random access for timely status update,” IEEE Transactions on Communications, vol. 68, no. 3, pp. 1538–1551, 2020.
[10] V. Tripathi and E. H. 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. [11] S. Zhou and X. Lin, “An easier-to-verify sufficient condition for Whittle indexability and application to AoI minimization,” in IEEE INFOCOM 2024 – IEEE Conference on Computer Communications, 2024, pp. 1741–1750. [12] Y. Xu, M.-J. Xiao, C. Wu, J. Wu, J.-R. Zhou, and H. Sun, “Age-ofinformation-aware federated learning,” Journal of Computer Science and Technology, vol. 39, no. 3, pp. 637–653, 2024. [13] J. Liu and H. Chen, “Optimizing AoI at query in multiuser wireless uplink networks: A Whittle index approach,” IEEE Transactions on Communications, vol. 73, no. 11, pp. 10 318–10 329, 2025. [14] R. R. Weber and G. Weiss, “On an index policy for restless bandits,” Journal of Applied Probability, vol. 27, no. 3, pp. 637–648, 1990. [15] M. Larrañaga, M. Assaad, A. Destounis, and G. S. Paschos, “Asymptotically optimal pilot allocation over markovian fading channels,” IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5395–5418, 2017. [16] F. Liu, C. Masouros, A. P. Petropulu, H. Griffiths, and L. Hanzo, “Joint radar and communication design: Applications, state-of-the-art, and the road ahead,” IEEE Transactions on Communications, vol. 68, no. 6, pp. 3834–3862, 2020. [17] N. C. Luong, X. Lu, D. T. Hoang, D. Niyato, and D. I. Kim, “Radio resource management in joint radar and communication: A comprehensive survey,” IEEE Communications Surveys & Tutorials, vol. 23, no. 2, pp. 780–814, 2021. [18] J. Zhang, W. Lu, C. Xing, N. Zhao, N. Al-Dhahir, G. K. Karagiannidis, and X. Yang, “Intelligent integrated sensing and communication: A survey,” Science China Information Sciences, vol. 68, no. 3, p. 131301, 2025. [19] D. Wen, Y. Zhou, X. Li, Y. Shi, K. Huang, and K. B. Letaief, “A survey on integrated sensing, communication, and computation,” IEEE Communications Surveys & Tutorials, vol. 27, no. 5, pp. 3058–3098, 2025. [20] Y. Zhou, A. A. Khuwaja, X. Li, N. Zhao, and Y. Chen, “Optimizing multi-UAV multi-user system through integrated sensing and communication for age of information (AoI) analysis,” IEEE Open Journal of the Communications Society, vol. 5, pp. 6918–6931, 2024. [21] Y. Bai, Y. Zhang, B. Xie, Z. Chang, Y. Zhang, R. Jäntti, and Z. Han, “Age of Information minimization in UAV-enabled integrated sensing and communication systems,” arXiv preprint arXiv:2507.14299, 2025. [22] Z. Liu, X. Liu, W. Yang, and X. Zhang, “Joint sensing and age of information optimization for energy constrained UAV-assisted integrated sensing, calculation, and communication,” IEEE Transactions on Wireless Communications, vol. 24, no. 5, pp. 4440–4453, 2025. [23] H. Mei, H. Zhang, X. Zhou, and J. Wang, “AoI minimization for airground integrated sensing and communication networks with jamming attack,” IEEE Transactions on Vehicular Technology, vol. 74, no. 8, pp. 12 776–12 790, 2025. [24] W. Fan, N. Wei, R. Xi, A. Bazzi, Y. Xiu, C. Assi, J. Dong, and J. Jin, “Heterogeneous mixture-of-experts for energy-efficient multimodal ISAC in highly mobile networks,” arXiv preprint arXiv:2604.06697, 2026. [25] T. Soleymani, M. Assaad, and J. S. Baras, “Status updating via integrated sensing and communication: freshness optimisation,” arXiv preprint arXiv:2601.22901, 2026. [26] B. C. Csáji and L. Monostori, “Value function based reinforcement learning in changing markovian environments,” Journal of Machine Learning Research, vol. 9, no. 54, pp. 1679–1709, 2008. [Online]. Available: http://jmlr.org/papers/v9/csaji08a.html
16
A PPENDIX A P ROOF OF L EMMA 4 Let V (0) ≡ 0 and define V (n+1) = T V (n) for n ≥ 0. For each n ≥ 0, set (n) m Ln := inf V (α + 1, αb ) − V (n) (αm , αb ) . αm ≥αb ≥1
Clearly, L0 = 0. Since V (n) is coordinatewise nondecreasing, Ln ≥ 0 for every n ≥ 0. Fix αm ≥ αb ≥ 1. From the state evolution in (6), (n)
(n)
Q0 (αm + 1, αb ) − Q0 (αm , αb ) h i = 1 + γλ0 V (n) (αm + 2, 1) − V (n) (αm + 1, 1) h + γ(1 − λ0 ) V (n) (αm + 2, αb + 1) i − V (n) (αm + 1, αb + 1) , (n)
(n)
Q1 (αm + 1, αb ) − Q1 (αm , αb ) h = 1 + γ(1 − λ1 ) V (n) (αm + 2, αb + 1) i − V (n) (αm + 1, αb + 1) , (n)
(n)
Q2 (αm + 1, αb ) − Q2 (αm , αb ) h = 1 + γ(1 − λ2 ) V (n) (αm + 2, αb + 1) i − V (n) (αm + 1, αb + 1) . By definition of Ln , every horizontal increment of V (n) is at least Ln . Since λ2 ≤ λ0 ≤ λ1 and Ln ≥ 0, each of the three differences above is bounded below by 1 + γ(1 − λ1 )Ln . Using mini xi − mini yi ≥ mini (xi − yi ), we get Ln+1 ≥ 1 + γ(1 − λ1 )Ln . Hence, n n−1 X k 1 − γ(1 − λ1 ) . γ(1 − λ1 ) = Ln ≥ 1 − γ + γλ1 k=0
Pointwise convergence of V (n) to V ∗ ensures
Moreover, under the same action u and the same realization of η, the corresponding next states also differ by at most one in each coordinate. Therefore, m b (n) m b Q(n) u (α̃ , α̃ ) − Qu (α , α ) ≤ 1 + γUn . (n)
Using V (n+1) (s) = minu∈{0,1,2} Qu (s) and mini xi − mini yi ≤ maxi (xi − yi ), we get Un+1 ≤ 1 + γUn . By iteration, n−1 X 1 − γn . Un ≤ γk = 1−γ k=0
Pointwise convergence of V (n) to V ∗ ensures V ∗ (α̃m , α̃b ) − V ∗ (αm , αb ) ≤
Nonnegativity follows immediately from V ∗ being coordinatewise nondecreasing. A PPENDIX C P ROOF OF L EMMA 6 At (α, α), the Bellman equation gives Q∗0 (α, α) = α + c0 + γλ0 V ∗ (α + 1, 1) + γ(1 − λ0 )V ∗ (α + 1, α + 1), Q∗1 (α, α) = α + c1 + γV ∗ (α + 1, α + 1), Q∗2 (α, α) = α + c2 + γλ2 V ∗ (α + 1, 1) + γ(1 − λ2 )V ∗ (α + 1, α + 1). Hence Q∗0 (α, α) − Q∗1 (α, α) = (c0 − c1 ) − γλ0 V ∗ (α + 1, α + 1) − V ∗ (α + 1, 1) ≤ 0 and Q∗0 (α, α) − Q∗2 (α, α) = (c0 − c2 ) − γ(λ0 − λ2 ) · V ∗ (α + 1, α + 1) − V ∗ (α + 1, 1) ≤ 0,
1 V (α + 1, α ) − V (α , α ) ≥ , 1 − γ + γλ1 ∗
m
b
∗
m
b
where we used c0 ≤ c1 ≤ c2 , λ2 ≤ λ0 , and Lemma 3. Therefore action 0 is optimal on the diagonal.
for every αm ≥ αb ≥ 1. A PPENDIX B P ROOF OF L EMMA 5 m
b
1 . 1−γ
m
A PPENDIX D P ROOF OF L EMMA 7
b
Fix (α , α ) ∈ S and (α̃ , α̃ ) ∈ S such that 0 ≤ α̃m − αm ≤ 1,
0 ≤ α̃b − αb ≤ 1.
Let V (0) ≡ 0 and define V (n+1) = T V (n) for n ≥ 0. For each n ≥ 0, set (n) m b (n) m b V (α̃ , α̃ ) − V (α , α ) : Un := sup αm ≥ αb ≥ 1, 0 ≤ α̃m − αm ≤ 1, . 0 ≤ α̃b − αb ≤ 1 Clearly, U0 = 0. For every u ∈ {0, 1, 2}, the stage-cost difference satisfies g (α̃m , α̃b ), u − g (αm , αb ), u ≤ 1.
Iterating (14) n times yields B(αb ) =
n−1 X
γ j (1 − λ0 )j 1 + γλ0 A(αb + j)
j=0
+ γ n (1 − λ0 )n B(αb + n). 1 for every αb , so the sequence By Lemma 5, 0 ≤ B(αb ) ≤ 1−γ b (B(α ))αb ≥1 is bounded. Since γ(1−λ0 ) < 1, letting n → ∞ gives
B(αb ) =
∞ X j=0
γ j (1 − λ0 )j 1 + γλ0 A(αb + j) .
17
By Lemma 3, the sequence (A(αb ))αb ≥1 is nonincreasing. Hence A(αb + j) ≤ A(αb ) for every j ∈ N0 , and therefore B(αb ) ≤
∞ X
For u = 2, Q∗2 (αm + 1, αb + 2) − Q∗2 (αm + 1, αb + 1) h i = γλ2 V ∗ (αb + 3, 1) − V ∗ (αb + 2, 1) h + γ(1 − λ2 ) V ∗ (αm + 2, αb + 3) i − V ∗ (αm + 2, αb + 2)
b
1 + γλ0 A(α ) γ j (1 − λ0 )j 1 + γλ0 A(αb ) = . 1 − γ + γλ0 j=0
Subtracting A(αb ) from both sides, we obtain B(αb ) − A(αb ) ≤
1 − (1 − γ)A(αb ) . 1 − γ + γλ0
Since A(αb ) ≥ 0, it follows that B(αb ) − A(αb ) ≤
1 1 < . 1 − γ + γλ0 γλ0
A PPENDIX E P ROOF OF L EMMA 8
= γλ2 A(αb + 1) + γ(1 − λ2 )C(αm + 1, αb + 1). Taking the supremum over αm ≥ αb + 1, we obtain n M (αb ) ≤ max γ(1 − λ0 )M (αb + 1), γλ1 B(αb + 2) + γ(1 − λ1 )M (αb + 1), o γλ2 A(αb + 1) + γ(1 − λ2 )M (αb + 1) . We compare each term in the right-hand side with B(αb + 1). First, γ(1 − λ0 )M (αb + 1) − B(αb + 1)
Let M (αb ) :=
sup
= γ(1 − λ0 ) M (αb + 1) − B(αb + 2) + γ(1 − λ0 )B(αb + 2) − B(αb + 1) .
C(αm , αb ).
αm ≥αb +1
Fix αb ≥ 1 and αm ≥ αb + 1. Using the Bellman equation and mini xi − mini yi ≤ maxi (xi − yi ), we obtain n C(αm , αb ) ≤ max Q∗0 (αm + 1, αb + 2) − Q∗0 (αm + 1, αb + 1), Q∗1 (αm + 1, αb + 2) − Q∗1 (αm + 1, αb + 1), Q∗2 (αm + 1, αb + 2) o − Q∗2 (αm + 1, αb + 1) . For u = 0,
From (14), the bracket is nonpositive. Hence γ(1 − λ0 )M (αb + 1) − B(αb + 1) ≤ γ(1 − λ0 ) M (αb + 1) − B(αb + 2) . Second, γλ1 B(αb + 2) + γ(1 − λ1 )M (αb + 1) − B(αb + 1) = γ(1 − λ1 ) M (αb + 1) − B(αb + 2) + γB(αb + 2) − B(αb + 1) . Moreover, γB(αb +2)−B(αb +1) = −1+γλ0 B(αb +2)−A(αb +1) .
Q∗0 (αm + 1, αb + 2) − Q∗0 (αm + 1, αb + 1) h = γ(1 − λ0 ) V ∗ (αm + 2, αb + 3) i − V ∗ (αm + 2, αb + 2) = γ(1 − λ0 ) C(αm + 1, αb + 1). For u = 1, Q∗1 (αm + 1, αb + 2) − Q∗1 (αm + 1, αb + 1) h = γλ1 V ∗ (αb + 3, αb + 3) i − V ∗ (αb + 2, αb + 2) h + γ(1 − λ1 ) V ∗ (αm + 2, αb + 3) i − V ∗ (αm + 2, αb + 2) = γλ1 B(αb + 2) + γ(1 − λ1 )C(αm + 1, αb + 1).
Since (A(αb ))αb ≥1 is nonincreasing, Lemma 7 gives B(αb + 2) − A(αb + 1) ≤ B(αb + 2) − A(αb + 2) <
1 , γλ0
so the bracket is strictly negative. Therefore γλ1 B(αb + 2) + γ(1 − λ1 )M (αb + 1) − B(αb + 1) ≤ γ(1 − λ1 ) M (αb + 1) − B(αb + 2) . Third, γλ2 A(αb + 1) + γ(1 − λ2 )M (αb + 1) − B(αb + 1) = γ(1 − λ2 ) M (αb + 1) − B(αb + 2) + γλ2 A(αb + 1) + γ(1 − λ2 )B(αb + 2) − B(αb + 1) . Again using (14), γλ2 A(αb + 1) + γ(1 − λ2 )B(αb + 2) − B(αb + 1) = −1 + γ(λ0 − λ2 ) B(αb + 2) − A(αb + 1) .
18
By the same bound as above, λ0 − λ2 γ(λ0 − λ2 ) B(αb + 2) − A(αb + 1) < ≤ 1, λ0 hence this bracket is also strictly negative. Therefore γλ2 A(αb + 1) + γ(1 − λ2 )M (αb + 1) − B(αb + 1) ≤ γ(1 − λ2 ) M (αb + 1) − B(αb + 2) . Combining the three bounds, we get n M (αb ) − B(αb + 1) ≤ max γ(1 − λ0 ) M (αb + 1) − B(αb + 2) , γ(1 − λ1 ) M (αb + 1) − B(αb + 2) , γ(1 − λ2 ) M (αb + 1) o − B(αb + 2) . h
b
b
γ(1 − λ1 ) M (αb + 1) − B(αb + 2) , #+ o b b γ(1 − λ2 ) M (α + 1) − B(α + 2) n o ≤ max γ(1 − λ0 ), γ(1 − λ1 ), γ(1 − λ2 ) h i+ · M (αb + 1) − B(αb + 2) . Since λ2 ≤ λ0 ≤ λ1 , this gives Y (αb ) ≤ γ(1 − λ2 )Y (αb + 1),
∀αb ≥ 1.
By Lemma 5, both C(αm , αb ) and B(αb + 1) are bounded between 0 and 1/(1 − γ), so (Y (αb ))αb ≥1 is bounded. If Y (ᾱb ) > 0 for some ᾱb , then iterating the previous inequality gives Y (ᾱb ) , Y (ᾱb + n) ≥ [γ(1 − λ2 )]n
∀n ≥ 1,
which is impossible because γ(1 − λ2 ) < 1 and (Y (αb ))αb ≥1 is bounded. Therefore Y (αb ) = 0 for every αb ≥ 1, that is, M (αb ) ≤ B(αb + 1),
∀αb ≥ 1.
Since C(αm , αb ) ≤ M (αb ) by definition of M (αb ), we conclude C(αm , αb ) ≤ B(αb + 1), for every αb ≥ 1 and every αm ≥ αb + 1.
∆∗01 (αm + 1, αb ) − ∆∗01 (αm , αb ) = γλ0 V ∗ (αm + 2, 1) − V ∗ (αm + 1, 1) h + γ(λ1 − λ0 ) V ∗ (αm + 2, αb + 1) i − V ∗ (αm + 1, αb + 1) , which is nonnegative because V ∗ is coordinatewise nondecreasing and λ1 ≥ λ0 ≥ 0. For ∆∗02 , again from (16), ∆∗02 (αm + 1, αb ) − ∆∗02 (αm , αb ) = γλ0 V ∗ (αm + 2, 1) − V ∗ (αm + 1, 1) h + γ(λ2 − λ0 ) V ∗ (αm + 2, αb + 1) i − V ∗ (αm + 1, αb + 1) . By Lemma 4,
i+ Taking positive parts, let Y (α ) := M (α ) − B(α + 1) . Then " n b Y (α ) ≤ max γ(1 − λ0 ) M (αb + 1) − B(αb + 2) , b
A PPENDIX F P ROOF OF L EMMA 9 Fix αb . From (16),
V ∗ (αm + 2, 1) − V ∗ (αm + 1, 1) ≥
1 , 1 − γ + γλ1
and by Lemma 5, 0 ≤ V ∗ (αm + 2, αb + 1) − V ∗ (αm + 1, αb + 1) ≤
1 . 1−γ
Combining these bounds, ∆∗02 (αm + 1, αb ) − ∆∗02 (αm , αb ) is nonnegative if λ0 λ0 − λ 2 , ≥ 1 − γ + γλ1 1−γ which is equivalent to (5). Finally, ∆∗21 (αm + 1, αb ) − ∆∗21 (αm , αb ) h = γ(λ1 − λ2 ) V ∗ (αm + 2, αb + 1) i − V ∗ (αm + 1, αb + 1) ≥ 0, because λ1 ≥ λ2 and V ∗ is coordinatewise nondecreasing. A PPENDIX G P ROOF OF L EMMA 10 Fix αm . Using (16), for ∆∗01 we obtain ∆∗01 (αm , αb + 1) − ∆∗01 (αm , αb ) h i = −γλ1 V ∗ (αb + 2, αb + 2) − V ∗ (αb + 1, αb + 1) h + γ(λ1 − λ0 ) V ∗ (αm + 1, αb + 2) i − V ∗ (αm + 1, αb + 1) h i = γ (λ1 − λ0 )C(αm , αb ) − λ1 B(αb + 1) . By Lemma 8, C(αm , αb ) ≤ B(αb + 1), therefore ∆∗01 (αm , αb + 1) − ∆∗01 (αm , αb ) h i ≤ γ (λ1 − λ0 )B(αb + 1) − λ1 B(αb + 1) = −γλ0 B(αb + 1) ≤ 0,
19
because B(αb + 1) ≥ 0 by coordinatewise monotonicity of V ∗. For ∆∗02 , again using (16), we obtain ∆∗02 (αm , αb + 1) − ∆∗02 (αm , αb ) h i = −γλ2 V ∗ (αb + 2, 1) − V ∗ (αb + 1, 1) h + γ(λ2 − λ0 ) V ∗ (αm + 1, αb + 2) i − V ∗ (αm + 1, αb + 1) = −γλ2 A(αb ) + γ(λ2 − λ0 )C(αm , αb ). Since A(αb ) ≥ 0, C(αm , αb ) ≥ 0, and λ2 ≤ λ0 , it follows that ∆∗02 (αm , αb + 1) − ∆∗02 (αm , αb ) ≤ 0. Hence both ∆∗01 (αm , αb ) and ∆∗02 (αm , αb ) are nonincreasing in αb for 1 ≤ αb ≤ αm − 1.