{'fraction_non_alphanumeric': 0.050098950849892916, 'fraction_numerical': 0.012985604684577223, 'mean_word_length': 4.161326430670211, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Age Minimization Transmission Scheduling over Time-Correlated Fading Channel under An Average Energy Constraint

In this paper, we consider transmission scheduling in a status update system, where updates are generated periodically and transmitted over a Gilbert-Elliott fading channel. The goal is to minimize the long-run average age of information (AoI) at the destination under an average energy constraint. We consider two practical cases to obtain channel state information (CSI): (i) without channel sensing and (ii) with delayed channel sensing. For case (i), the channel state is revealed when an ACK/NACK is received at the transmitter following a transmission, but when no transmission occurs, the channel state is not revealed. Thus, we have to design schemes that balance tradeoffs across energy, AoI, channel exploration, and channel exploitation. The problem is formulated as a constrained partially observable Markov decision process problem (POMDP). To reduce algorithm complexity, we show that the optimal policy is a randomized mixture of no more than two stationary deterministic policies each of which is of a threshold-type in the belief on the channel. For case (ii), (delayed) CSI is available at the transmitter via channel sensing. In this case, the tradeoff is only between the AoI and energy consumption and the problem is formulated as a constrained MDP. The optimal policy is shown to have a similar structure as in case (i) but with an AoI associated threshold. Finally, the performance of the proposed structure-aware algorithms is evaluated numerically and compared with a Greedy policy.


I. INTRODUCTION
For status update systems, where time-sensitive status updates of certain underlying physical process are sent to a remote destination, it is important that the destination receives fresh information updates. The age of information (AoI) is a performance metric that is a good measure of the freshness of the data at the destination. In particular, AoI is defined as the time elapsed since the generation of the recently received status update.
The problem of minimizing the AoI in status update systems has attracted significant recent attention (e.g., [1], [2], [3], [4], [5]). Due to the fact that sensors in the status update system are usually battery-powered and thus have limited energy supply, the problem of minimizing the long-run average AoI has to take energy constraints into account. Moreover, communication over a wireless channel is subject to multiple impairments such as fading, path loss and interference, which may lead to status updating failure. Since each failed transmission consumes unnecessary energy, there is a strong motivation for designing intelligent transmission scheduling algorithms i.e., retransmission or suspension of transmission to increase channel utilization as well as prolong battery life.
Many existing works that deal with the AoI minimization problem under energy constraints in status update systems assume either perfect knowledge of the channel state or noiseless channel to guarantee successful transmission. In [6], [7], the authors assume that the channel is noiseless, and propose offline or online status updating policies to minimize the longrun average AoI under energy constraints. In [8], the authors jointly design sampling and updating processes over a channel with perfect channel state information. The success of each transmission is guaranteed via using predefined transmission power which is a function of the channel state. However, in most practical scenarios, the channel state may not be known a priori. More appealing cases are to consider unreliable transmissions with imperfect knowledge of wireless channels. Papers [9] and [10] consider transmission scheduling over unreliable channels to minimize average AoI under average energy/resource constraints. In [9], the authors consider a block fading channel, where the channel is assumed to vary independently and identically over time slots. In [10], the authors consider an error-prone channel, where decoding error depends only on the number of retransmissions.
All of these works neglect an important characteristics of the wireless fading channel-the channel memory or time correlation [11]. Indeed, the memory can be intelligently exploited to predict the channel state and thus to design efficient scheduling policies in the presence of transmission cost. A finite state Markov chain is an often used and appropriate model for fading channel [12]. A somewhat simplified but often-used abstraction is a two-state Markovian model known as the Gilbert-Elliot channel [13]. The model assumes that the channel can be either in good or bad state, and captures the essence of the fading process. In [14], the authors consider status updating in cognitive radio networks, where updates from the energy harvesting secondary user are generated at will and transmitted over the primary user's channel. The occupation of primary user's channel is modeled as a twostate Markov chain. Although a Markov chain is used to model occupation of primary channel, their threshold-type structural result is built on perfect knowledge of the channel state since update decisions are made based on perfect sensing results. In contrast, in our work, we do not assume that the channel state is known a priori at the time of making updating decisions.
Motivated by the time-correlation in a fading channel and the fact that sensors in practice are typically configured to generate status updates periodically [15], in this paper, we consider a status update system where the status update is generated periodically and transmitted over a Gilbert-Elliot channel. We do not assume that the channel state is known a priori and consider two practical cases to obtain the channel state information (CSI): (i) (without channel sensing) CSI is revealed by ACK/NACK feedback on transmission; (ii) (with delayed channel sensing) delayed CSI is always available via delayed channel sensing regardless of transmission decisions.
To increase the reliability of received status updates, retransmissions are allowed. With these, we study the problem of how to minimize the average AoI under a long-run average energy constraint. The problem in case (i) is formulated as a constrained partially observable Markov decision process problem (POMDP) while in case (ii), it is formulated as a constrained Markov decision problem (MDP). It is known that in general POMDP is PSPACE hard to solve and MDP suffers from the curse of dimensionality. In fact, the problem in both cases involves long-run average cost with infinite state space and unbounded costs, which makes the analysis difficult. Hence, the main contributions of this paper are to characterize the structure of optimal transmission scheduling policies and accordingly develop structure-aware algorithms for both cases.
In particular, our key contributions include: • For the case without channel sensing, we formulate the problem as a constrained average-AoI POMDP and reexpress it as a constrained average-AoI belief MDP by adding the belief on the channel to the system state. For the case with delayed channel sensing, we formulate the problem as a constrained average-AoI MDP. • Using the Lagrangian approach, we transform the constrained average-AoI (belief) MDP in either case into a parameterized unconstrained average cost (belief) MDP. By relating the unconstrained average cost MDP to the unconstrained discounted cost MDP, we prove that in either case, there exists a stationary deterministic thresholdtype policy that minimizes the unconstrained average cost. Value iterations are used in proof for both cases while concavity of the value functions is used in the case without channel sensing. • Based on a result in [16], we show that the optimal transmission scheduling policy in either case is a randomized mixture of no more than two deterministic threshold-type policies. • To reduce the algorithm complexity, we develop structure-aware algorithms based on relative value iteration (RVI) and Lagrange dynamic programming for each case.
The remainder of this paper is organized as follows. The system model is introduced in Section II. For the case without channel sensing, we formulate the problem in Section III, and in Section IV, we explore the structure of the optimal policy and propose a structure-aware algorithm. In Section IV-B, we investigate the case with delayed channel sensing. Section VI

II. SYSTEM MODEL
We consider a status update system where status updates are generated periodically and transmitted to a remote destination over a time-correlated fading channel as shown in Fig. 1. We consider a time-slotted system, where a time slot corresponds to the time duration of the packet transmission time and feedback period. Every K consecutive time slots form a frame. The frame length represents the generation period of status updates. Define K as the set of relative slot index within a frame, K {1, 2, · · · , K}. Use t ∈ {1, 2, · · · } as an absolute index for the slot count, which increments indefinitely with time. For any slot t, the corresponding frame index l t ∈ {1, 2, · · · } is determined by l t = t K +1 and relative slot index k t ∈ K is determined by k t = ((t − 1) mod K) + 1, where · is the floor function.

A. Channel Model
The time-correlated fading channel for transmission is assumed to evolve as a two-state Gilbert-Elliot model [13]. Let h t denote the channel state at the time slot t, which is modeled as a one-dimensional Markov chain with two states: a "good" state denoted by 1 and a "bad" state denoted by 0. In the "bad" state, the channel is assumed to be in a deep fade such that transmission fails with probability one; while in the "good" state, a transmission attempt is always successful. This assumption conforms with the signal-to-noise ratio (SNR) threshold model for reception where successful decoding of a packet at the destination occurs if and only if the SNR exceeds certain threshold value. The channel transition probabilities are given by P(h t+1 = 1|h t = 1) = p 11 and P(h t+1 =1|h t = 0) = p 01 . We assume that the channel transitions occur at the end of each time slot, and that p 11 and p 01 are known.
The presence of channel memory (time correlation) makes it possible to predict the channel state. Define Markovian channel memory as µ = p 11 − p 01 [17], [18]. In this paper, we assume that p 11 ≥ p 01 (positively correlated channel) (similar assumptions have been used in [19], [20]). Note that p 11 < p 01 corresponds to oscillatory channels and doesn't have practical meaning in Gilbert-Elliot channels [18].

B. Transmission Scheduler and Channel State Information
Updates are generated at the beginning of each time frame. In any frame, if the generated status update is not delivered by the end of the frame, then it gets replaced by a new one in the next frame. We use u t ∈ U {0, 1} to denote the decision of the scheduler at the time slot t, where u t = 1 means transmitting (retransmitting) the undeliverd statues update, and u t = 0 denotes suspension of transmission (retransmission). In each slot t, if the status update is delivered, i.e. ∆ t < K, then we have u t = 0. For simplicity, we use transmission to refer to both transmission and retransmission in the remaining content.
In this paper, we consider two practical cases to obtain CSI: (i) (without channel sensing) CSI is revealed via the feedback on transmission from the destination; (ii) (with delayed channel sensing) CSI of the last time slot is always available via delayed channel sensing regardless of transmission decisions. In particular, for case (i), if a transmission is attempted, then the scheduler receives an error-free ACK/NACK feedback from the destination specifying whether the status update was delivered or not before the end of the slot. We use Θ to denote the set of observations, Θ {0, 1}. Let θ t ∈ Θ be the observation at time slot t. Then, θ t = 1 denotes a successful transmission. θ t = 0 occurs when the transmission occurs over the channel in the bad state or the transmission is suspended. Note that when a decision is made not to transmit updates, the scheduler will not obtain feedback revealing the CSI. Thus, the channel in this case is partially observable. In contrast, for case (ii), CSI of the last time slot is always available via delayed channel sensing regardless of transmission decisions.

C. Age of Information
Age of information (AoI) reflects the timeliness of the information at the destination. It is defined as the time elapsed since the generation of the most recently received update at the destination. Let ∆ t denote the AoI at the beginning of the time slot t. Let U (t) denote the generation time of the last successfully received status update for time slot t. Then, ∆ t is written as (1) If a status update is not successfully delivered in slot, then the AoI increases by one, otherwise, the AoI drops to the time elapsed since the beginning of the frame (generation time of the newly delivered status update). Then, the value of ∆ t+1 is updated as follows: Let A k denote the set of all possible AoI values at the kth slot of a frame. By (2), denotes the relative slot index before k. In Fig. 2, the evolution of AoI is illustrated for a given sample path of deliveries at the destination with K = 4.

D. Optimization Problem
A transmission scheduling policy π = {d 1 , d 2 , · · · } specifies the decision rules for each time slot, where a decision rule d t is a function that maps the past actions, past and current AoI, relative slot index of a frame and channel states to actions. We assume that each transmission consumes the same energy which is normalized as one unit energy. Note that if there is no energy constraint on the transmitter, then exploiting every time slot in transmitting the undelivered update is optimal. This is because suspending the transmission of an undelivered status update does not contribute to decreasing the AoI and also wastes an opportunity to learn the channel state in the case without channel sensing. But in practice, repeated transmission attempts could result in excessive energy consumption. Accordingly, we employ an average energy consumption constraint. In particular, our objective in this paper is to design a transmission scheduling policy π that minimizes the following long-run average AoĪ while the long-run average energy consumptionĒ(π) does not exceed E max ∈ (0, 1], i.e.
where E π denotes expectation under policy π. Note that E max = 1 corresponds to the case in which energy is enough to support transmission in every slot.

III. CONSTRAINED POMDP FORMULATION AND LAGRANGIAN RELAXATION WITHOUT CHANNEL SENSING A. Constrained POMDP Formulation
At the beginning of each time slot, the scheduler chooses an action u. Given that the state of the underlying Markov channel is i, the user observes θ(i, u) ∈ {0, 1}, which indicates the state of the current channel. Specifically, an ACK will be received if and only if the status update is transmitted over a "good" channel, i.e. θ(1, 1) = 1. Otherwise, for (i, u) = (1, 1), θ(i, u) = 0. Upon receipt of the feedback/observation, the AoI changes accordingly at the end of this slot. The sequence of operations in each slot is illustrated in Fig. 3. Note that when transmission is suspended, the channel state is not directly observable. Together with the average energy constraint, the problem we consider in the paper turns out to be a constrained partially observable Markov decision problem (POMDP).

Take the Action
Observation ,

Fig. 3: Sequence of operations in a slot
At the beginning of each time slot t, our knowledge of underlying channel state can be summarized by a belief state ω t , where ω t is based on previous observations and decisions. Specifically, the belief state ω t is defined as conditional probability (given observation and action history) that channel is in "good" state at the beginning of the slot t. It has been shown in [21] that for any slot t, the belief ω t is a sufficient statistic to describe the knowledge of the channel and thus can be used for making optimal decisions at time slot t. Thus, adding the belief to the system state, the constrained POMDP can be written as constrained belief MDP [22]. We describe the components of the framework as follows: States: The system state consists of completely observable states and the belief state, i.e., the system state at slot t is defined by a 3-tuple s t =(∆ t , k t , ω t ), where ∆ t ∈ A kt is the AoI state that evolves as (2); k t ∈ K is the relative slot index in the frame l t that evolves as k t+1 = (k t ) + , where (y) + (y mod K) + 1; ω t is the belief state whose evolution is defined in the following paragraph.
Belief Update: Given u t and θ t , the belief state in slot t + 1 is updated by ω t+1 = Λ(ω t , u t , θ t ) as follows. If u t = 0, then the scheduler will not learn the channel state and the belief is updated only according to the Markov chain. If u t = 1, the observation θ t after the transmission provides the true channel state before the state transition which occurs at the end of the slot (see Fig. 3). In particular, Λ(ω t , u t , θ t ) is expressed as where T (ω t ) = ω t p 11 +(1−ω t )p 01 denotes the one-step belief update. Let T m (ω t ) P(h t+m = 1|ω t ) denote m-step belief update when the channel is unobserved for m consecutive slots, where m ∈ {0, 1, · · · } and T 0 (ω) = ω. Note that by (5), after a transmission (u = 1), ω is either p 01 or p 11 . Afterwards, ω is updated by T upon each suspension until next transmission attempt. Thus, the belief state ω is in the form of T m (p 01 ) or T m (p 11 ), where m ≥ 0. Moreover, an increase in AoI by one results from either a failed transmission (ω becomes p 01 ) or suspension (ω is updated by T ). This implies that the AoI cannot be smaller than the updating times via T . Thus, the set of belief states regarding ∆ is expressed as In this paper, we consider the state space S {(∆, k, ω) : k ∈ K, ∆ ∈ A k , ω ∈ Ω ∆ }. Note that if an initial state s 1 is outside S, then eventually the state s 1 will enter S (with state (k, k + , p 01 ) or (k, k + , p 11 ), k ∈ K) and stay in S onwards; otherwise, the status update is never transmitted.
Actions: Action set is U = {0, 1} defined in Section II-B.
Transition probabilities: Given the current state s t = (∆ t , k t , ω t ) and action u t at slot t, the transition probability to the state s t+1 = (∆ t+1 , k t+1 , ω t+1 ) at the next slot t + 1, which is denoted by P stst+1 (u t ), is defined as Costs: The AoI cost of one slot is the AoI at the beginning of a slot. Then, the change in AoI that results from the action taken at slot t is reflected at the beginning of the next slot t + 1. Thus, given state s t = (∆ t , k t , ω t ) and action choice u t at slot t, the AoI cost of one slot is expressed as and the energy consumption of one slot is For any transmission scheduling policy π, we assume that the resulted Markov chain is a unichain (same assumptions are also made in [8], [23]). The transmission scheduling problem can be formulated as a constrained belief MDP: Problem 1 (Constrained average-AoI belief MDP): s.t.Ē(π) = lim sup We useĀ * to denote the optimal average AoI, which is the solution to the problem (11). In Section IV, we show that there exists a stationary policy which achievesĀ * . In particular, a stationary policy is independent of time and can be expressed by a single decision rule π = {d, d, · · · }, where d probabilistically maps states to actions.

B. Lagrange Formulation of the Constrained POMDP
To obtain the optimal transmission scheduling policy, we reformulate the constrained average-AoI belief MDP in (11) as a parameterized unconstrained average cost belief MDP using Lagrangian approach. Given Lagrange multiplier λ, the instantaneous Lagrangian cost at time slot t is defined by Then, the average Lagrangian cost under policy π is given bȳ Then, we have an unconstrained average cost belief MDP which aims at minimizing the above average Lagrangian cost: Problem 2 (Unconstrained average cost belief MDP): whereL * (λ) is the optimal average Lagrangian cost with regard to λ. A policy is said to be average cost optimal if it minimizes the average Lagrangian cost. The relation between the optimal solutions of the problems (11) and (14) is provided in the following corollary. Corollary 1. The optimal average AoI of problem (11) and the optimal average Lagrangian cost of problem (14) satisfȳ Proof Sketch: By Theorem 12.7 in [16], we only need to check the following condition: for all r ∈ R, the set G(r) {s ∈ S : inf u C ∆ (s, u) < r} is finite. Given r, for any s = (∆, k, ω) ∈ G(r), ∆ = inf u C ∆ (s, u) < r. With fixed finite ∆, Ω ∆ is finite. Thus, G(r) is finite. The corollary establishes that the constrained average-AoI belief MDP in (11) can be solved with two steps: (i) solve the unconstrained average cost belief MDP in (14) with fixed λ; (ii) determine λ to obtain the optimal policy for (11).

IV. STRUCTURE OF THE OPTIMAL TRANSMISSION SCHEDULING POLICY AND ALGORITHM DESIGN
In this section, we investigate the structure of the optimal policy for the constrained average-AoI belief MDP in (11) and propose a structure-aware algorithm.
A. Structure of Constrained Average-AoI Optimal Policy 1) Main results: To explore the structure, we first show that there exists a stationary deterministic threshold-type scheduling policy that solves the unconstrained average cost belief MDP in (14). Theorem 1. Given Lagrange multiplier λ, there exists a stationary unconstrained average cost optimal policy that is deterministic and of threshold-type in belief. Specifically, (14) can be minimized by the policy of the form where ω * (∆, k; λ) denotes the threshold given pair of AoI and relative slot index (∆, k) and Lagrange multiplier λ.
Proof. Please see Section IV-A2.
Next, we show that the optimal policy for the original problem (11) is a mixture of no more than two stationary deterministic threshold-type policies. Corollary 2. There exists a stationary transmission scheduling policy π * that is the optimal solution to the constrained average-AoI belief MDP in (11), where π * is a randomized mixture of threshold-type scheduling policies as follows: where q ∈ [0, 1] is a randomization factor; π * λ1 , π * λ2 are two average cost optimal policies that are of the form in (16) for some Lagrange multipliers λ 1 and λ 2 .
Proof. Note that a stationary policy that transmits at the beginning of every 1 KEmax frames satisfies energy constraint, where · is the ceil function. Thus, the problem (11) is feasible. Together with our unichain assumption, the result follows from Theorem 4.4 in [16].
The method to determine λ 1 , λ 2 and q will be discussed in Section IV-B2.
2) Proof of Theorem 1: We prove Theorem 1 in two steps: (i) address an unconstrained discounted cost belief MDP; (ii) relate it to the unconstrained average cost belief MDP. In particular, we show that the optimal policy for the unconstrained discounted cost belief MDP is of threshold-type in ω, which implies that the optimal policy for the unconstrained average cost belief MDP is of threshold-type in ω Given an initial state s, the total expected discounted Lagrangian cost under policy π is given by where β ∈ (0, 1) is a discount factor. The optimization problem of minimizing the total expected discounted Lagrangian cost can be cast as Problem 3 (Unconstrained discounted cost belief MDP): where V β (s) denotes the optimal total expected β-discounted Lagrangian cost (for convenience, we omit λ in notation V β (s)).
A policy is said to be β-discounted cost optimal if it minimizes the total expected β-discounted Lagrangian cost. In Proposition 1, we introduce the optimality equation of V β (s).
Using (c) in Proposition 1, we show properties of V β in Lemma 1. In this lemma, some transient states like (·, ·, 0) are used. That's why they are included in the state space S. Note that adding these transient states will not change the optimal value. This is because the average cost until the transient states enter state space of recurrent states approaches 0, as the number of slots goes to infinity. Lemma 1. If p 11 ≥ p 01 , then V β has the following properties: (a) V β (∆, k, ω) is non-decreasing with regard to age ∆. (26) where x = T m (p 11 ), y = T m (p 01 ) and z = T m+1 (ω), for m ≥ 0, ω ∈ {0, 1, T j (p 01 ), T j (p 11 ), j ≥ 0}. (d) The optimal policy corresponding to V β is of a thresholdtype in ω, i.e. given ∆, k, there exists a threshold ω * β (∆, k; λ) such that it is optimal to transmit only when ω ≥ ω * β (∆, k; λ). Proof Sketch: Please see Appendix A.
By (d) in Lemma 1, the β-discounted cost optimal policies are of threshold-type in belief. By [24], under certain conditions (A proof sketch of these conditions verification is provided in Appendix B), average cost optimal policy can be viewed as a limit of a sequence of β-discounted cost optimal policies as β → 1. Thus, the average cost optimal policies are of threshold-type in belief.

B. Structure-Aware Algorithm Design
By Corollary 2, we (i) design a structure-aware algorithm for the unconstrained average cost belief MDP in (14); (ii) design the way to determine parameters λ 1 , λ 2 and q. In the end, (i) and (ii) are combined in Algorithm 1.
1) Structure-Aware Algorithm for the approximate unconstrained average cost belief MDP: Value iteration is a classical method to solve an MDP. However, the value iteration cannot work in practice if state space is infinite, since an infinite number of states need to be updated for each iteration. To deal with this, we (i) approximate the infinite S with a large but finite space; (ii) propose structure-aware algorithm to minimize the average Lagrangian cost of the approximate belief MDP; (iii) show that the sequence of our approximate belief MDPs converges to the original unconstrained average cost belief MDP.
Let N be an upper bound for the AoI and the times of Markov transitions on either p 01 or p 11 . In particular, with bound N , the state space of the approximate belief MDP is defined by S N {(∆, k, ω) ∈ S : ∆ ≤ N, ω ≤ T N (p 01 ) or ω ≥ T N (p 11 )}. Without loss of generality, we assume N > K.
In general, a sequence of approximate MDPs may not converge to the original MDP [25]. We show the convergence of our approximate MDPs to the original MDP in Theorem 2. The Relative Value Iteration (RVI) algorithm can be utilized to obtain an optimal stationary deterministic policy for the approximate MDP. In particular, RVI starts with V N 0 (s) = 0, ∀s ∈ S N and updates V N n+1 (s) by minimizing the RHS of equation (29) in the n + 1-th iteration, n ∈ {0, 1, 2, · · · }.
where 0 is the reference state and h N n (s) = V N n (s) − V N n (0). Note that similar to the proof in Section. IV-A, it can be shown that the optimal policy for the approximate MDP is still of threshold-type. Thus, we utilize the threshold property in traditional RVI and propose a threshold-type RVI to reduce algorithm complexity in Algorithm 1 (Line 4-24). For each iteration, we update threshold ω * (∆, k; λ) (Line 16) in addition to V N (s). If certain state satisfies threshold condition, then the optimal action for the state in this iteration is determined immediately without doing the optimization operation (Line 12), which reduces algorithm complexity. 2) Lagrange Multiplier Estimation: By Lemma 3.4 of [26], A(π * λ1 )≤Ā(π * λ2 ) andĒ(π * λ1 )≥Ē(π * λ2 ) given λ 1 <λ 2 . Thus, the optimal Lagrangian multiplier λ * is defined as λ * inf{λ > 0 : E(π * λ ) ≤ E max }. If there exists λ * such thatĒ(π * λ * ) = E max , then the constrained average-AoI optimal policy is a stationary deterministic policy where q in Corollary 2 is either zero or one. Otherwise, the optimal policy π * chooses policy π * λ * − with probability q and policy π * λ * + with probability 1 − q. The randomization factor q can be computed with following equation: The bisection method can be used to compute λ * − , λ * + and thus q. The details are provided in algorithm 1 (Line 2-3 and Line 26-30) and the algorithm starts with λ * − = 0 and sufficiently large λ * + .

V. AOI MINIMIZATION UNDER ENERGY CONSTRAINT WITH DELAYED CHANNEL SENSING
With delayed channel sensing, the CSI of the last time slot is always available at the beginning of each slot. Thus, the problem in this case can be formulated as a constrained MDP. The state space reduces to S {(∆, k, g) : k ∈ K, ∆ ∈ A k , g ∈ {0, 1}}, where g denotes the CSI of the last time slot. Given s t = (∆ t , k t , g t ) and u t at time slot t, the transition probability to s t+1 = (∆ t+1 , k t+1 , g t+1 ) is written as follows: if u t = 0, s t+1 = (∆ t + 1, (k t ) + , g t+1 ). (31) Following Section III-B and Section IV, the optimal transmission scheduling policy in this case is also a randomized mixture of no more than two deterministic policies, each of which is optimal for an unconstrained average cost MDP. But thanks to the simplification in state, we can show that the optimal policy for the unconstrained average cost MDP in this case is of threshold-type in AoI in Theorem 3.
Theorem 3. Given Lagrange multiplier λ, there exists a stationary unconstrained average cost optimal policy that is deterministic and of threshold-type in AoI. Specifically, the policy is in the form π and ∆ * (k, 1; λ) ≤ ∆ * (k, 0; λ), (33) where ∆ * (k, g; λ) denotes the threshold given pair of relative slot index and delayed CSI (k, g) and Lagrange multiplier λ.
Different from Theorem 1 which provides threshold structure in belief ω, Theorem 3 obtains that (i) the average cost optimal policy is of threshold-type in AoI, and (ii) threshold when g = 1 is no larger than the threshold when g = 0. Indeed, (ii) is used in algorithm to further reduce algorithm complexity. In particular, similar to Section IV-B1, we bound AoI with N and propose a threshold-type algorithm in Algorithm 2 to minimize unconstrained average cost. Different from corresponding part in Algorithm 1, ∆ * (k, 1; λ) is updated along with each threshold updating (Line 15) to keep the threshold relation in (33). This further reduces algorithm complexity.
The proof idea of Theorem 3 is similar to Theorem 1. We relate average cost MDPs to discounted cost MDPs. Next, we explore the structure of discounted cost optimal policies.
The optimality equation in (20) is modified as follows: First, we prove the monotonicity of value function V β in AoI in Lemma 2.
Proof Sketch: The proof uses induction and V β n (s) → V β (s) as n → ∞ which is similar to proof in Lemma 1.
With this, we characterize the structure of optimal policy for the unconstrained discounted cost MDP in Lemma 3. Lemma 3. Given λ and β, the optimal policy that minimizes the β-discounted Lagrangian cost is of threshold-type in AoI ∆, i.e. given k, g, there exists a threshold ∆ * β (k, g; λ) such that it is optimal to transmit only when ∆ ≥ ∆ * β (k, g; λ). In addition, ∆ * β (k, 1; λ) ≤ ∆ * β (k, 0; λ). Proof Sketch: For the first result, we show that, if it is optimal to transmit at a state (∆, k, g), then it is optimal to transmit for any state (∆ , k, g) such that ∆ > ∆. For the second result, we let ∆ 1 = ∆ * β (k, 0; λ) be AoI threshold when g = 0 and show that it is optimal to transmit at state (∆ 1 , k, 1), which implies that AoI threshold when g = 1 is no larger than ∆ 1 .
Similar to the proof of Theorem 1, we can extend the result to the unconstrained average cost MDP as in Theorem 3.

VI. NUMERICAL RESULTS
In this section, we numerically evaluate the performance of the proposed algorithms. We assume N = 1000 and obtain all simulation results over 10 5 time slots. Fig. 4 plots the AoI-energy tradeoff with different fading characteristics (different p 11 and p 01 ) for the two cases that we consider in this paper. In this simulation, we set K = 3. The optimal average AoI with no energy constraint is plotted as a gray dashed line accordingly. When comparing Fig. 4a with Fig. 4b, it is easy to observe that for fixed energy constraint and pair of p 11 and p 01 , the average AoI with delayed channel sensing is no larger than that without channel sensing.

A. Average AoI Performance
Moreover, the curves in Fig. 4a and Fig. 4b  In addition, we can observe that for certain energy constraint, the average AoI decreases with either p 11 or p 01 . This is due to the fact that increase in either p 11 or p 01 results in the increase of steady state probability that channel is in good state. Fig. 5 studies the average AoI performance vs frame length with different fading characteristics in the two cases. We set the energy constraint E max = 0.3. Let e t denote total energy consumption before slot t. Then, e t e t /(t − 1) denotes the average energy consumed before slot t. We compare the proposed transmission scheduling policies with a greedy policy that transmits whenē t < E max and ∆ t ≥ K. We set K = 3, p 11 = 0.7, p 01 = 0.3, in which case the optimal AoI with no energy constraint is achieved with 0.6167 units energy on average. Thus, the comparison is conducted with energy constraint ranging from 0.1 to 0.6. In Fig. 6, it is easy to observe that the proposed transmission scheduling policy outperforms the greedy policy in both cases. The gap between the greedy policy and scheduling policy in either case narrows as the energy constraint is loosened.

VII. CONCLUSION
We studied scheduling transmission of periodically generated updates over a Gilbert-Elliott fading channel in two cases. For the case without channel sensing, the problem is a constrained POMDP and is rewritten as a constrained belief MDP by introducing belief state. We show that the optimal policy for the constrained belief MDP is a randomization of no more than two stationary deterministic policies, each of which is of a threshold-type in the belief on the channel. For the case with delayed channel sensing, we show that the optimal policy has a similar structure as the one in the former case but with AoI associated threshold. In addition, we show that the AoI threshold has monotonic behavior in the delayed channel state in this case. The structure is utilized in either case to reduce algorithm complexity. Suppose that (a)-(d) hold for n. First, we show that (d) holds for n+1. With similar argument in [21], we can show that V β n is a concave function in ω via induction. Thus, by (24), Q β n+1 (∆, k, ω; 0) is concave in ω. Moreover, by (25), Q β n+1 (∆, k, ω; 1) is linear in ω. Thus, (d) for n + 1 can be shown by analyzing two cases as in Fig. 7.
Second, we use similar method in proof of Theorem 1 in [27] to show that (a)-(c) hold for n+1. The difference is that we use both concavity of V β n and induction hypothesis to show properties while only induction hypothesis is used in [27]. APPENDIX B PROOF SKETCH FOR VERIFICATION OF CONDITIONS IN [24] The conditions are listed below: • A1: V β (s) defined in (19) is finite ∀s, β. In Proposition 1, we showed that a policy f that chooses u = 0 at every slot satisfies L β s (f ; λ) <∞. By (19), we have V β (s) ≤ L β s (f ; λ), which implies A1. Moreover, we have V β increasing in ∆ and decreasing in ω by lemma 1. Hence, by setting L = V β (0)−min k∈K V β ((k) − , k, 1) ≥ 0, where 0 = (K, 1, p 11 ) is the reference state, we proves A2.
Let δ be the policy that transmits at each time slot. Similar to proof of Lemma 6 in [28], The AoI can be regarded as a stable AoI queue. Hence, states that occur after delivery are recurrent. This implies that 0 is recurrent. Actually, the probability of not entering state 0 after l frames is no more than b l , where b is steady state probability that channel is in "bad" state. Hence, under policy δ the expected cost of the first passage from state s to 0, denoted by c s,0 (δ), is finite. Similar to proof of Proposition 5 in [24], we have h β (s)<c s,0 (δ) < ∞. Hence, by setting M (0)= 0 and M (s) =c s,0 (δ) for s = 0, we proves A3. After transition from s under any action, there will be at most two possible states. Since for all s, M (s) < ∞, the sum of at most two M (·) is also finite. Hence, A4 holds.
We use similar method in the proof of Theorem 9 in [28] to verify these conditions. The main difference is that we bound two components in state, i.e., AoI and belief while in [28], only AoI is bounded. We deal with the difference by carefully designing the bound in belief. Recall that ϕ(·) and ν(·) are operators defined in Section IV-B1 to bound belief and state, respectively. In fact, we have ϕ(ω) = T N (p 11 ) if T N (p 01 ) < ω < T N (p 11 ). Then, since V β (∆, k, ω) increases with age ∆ and decreases with belief state ω in Lemma 1, we have V β (ν(r)) ≤ V β (r), which is a key inequality used in the proof.