Delay-Optimal Probabilistic Scheduling with Arbitrary Arrival and Adaptive Transmission
Xiang Chen Wei Chen Joohyun Lee Ness B. Shroff





Delay-Optimal Probabilistic Scheduling with 
 Arbitrary Arrival and Adaptive Transmission
    
Xiang Chen, Student Member, IEEE,
Wei Chen, Senior Member, IEEE,
Joohyun Lee, Member, IEEE,
and Ness B. Shroff, Fellow, IEEE

X. Chen and W. Chen are with the Department of Electronic Engineering and Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University. E-mail: chen-xiang12@mails.tsinghua.edu.cn, wchen@tsinghua.edu.cn.

J. Lee is with the Department of ECE at The Ohio State
University. E-mail: lee.7119@osu.edu.

Ness B. Shroff holds a joint appointment in both the Department of ECE and the Department of CSE at The Ohio State University. E-mail: shroff@ece.osu.edu.

    
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




In this paper, we aim to obtain the optimal delay-power tradeoff and the corresponding optimal scheduling policy for arbitrary i.i.d. arrival process and adaptive transmissions. The number of backlogged packets at the transmitter is known to a scheduler, who has to determine how many backlogged packets to transmit during each time slot. The power consumption is assumed to be convex in transmission rates. Hence, if the scheduler transmits faster, the delay will be reduced but with higher power consumption. To obtain the optimal delay-power tradeoff and the corresponding optimal policy, we model the problem as a Constrained Markov Decision Process (CMDP), where we minimize the average delay given an average power constraint. By steady-state analysis and Lagrangian relaxation, we can show that the optimal tradeoff curve is decreasing, convex, and piecewise linear, and the optimal policy is threshold-based. Based on the revealed properties of the optimal policy, we develop an algorithm to efficiently obtain the optimal tradeoff curve and the optimal policy. The complexity of our proposed algorithm is much lower than a general algorithm based on Linear Programming. We validate the derived results and the proposed algorithm through Linear Programming and simulations.


Cross-layer design, Queueing, Scheduling, Markov Decision Process, Energy efficiency, Average delay, Delay-power tradeoff, Linear programming.




§ INTRODUCTION

In this paper, we study an important problem of how to schedule the number of packets to transmit over a link taking into account both the delay and the power cost. This is an important problem because delay is a vital metric for many emerging applications (e.g., instant messenger, social network service, streaming media, and so on), and power consumption is critical to battery life of various mobile devices. In other words, we are studying the tradeoff between the timeliness and greenness of the communication service.

Such a delay-power scheduling problem can be formulated using a Markov Decision Process (MDP). The authors in <cit.> were among the earliest who studied this type of scheduling problem. Specifically, they considered a two-state channel and finite time horizon. The dual problem was solved based on results derived by Dynamic Programming and induction. Follow-up papers <cit.> extended this study in various directions. The optimal delay-power tradeoff curve is proven to be nonincreasing and convex in <cit.>. The existence of stationary optimal policy and the structure of the optimal policy are further investigated in <cit.>. Different types of power/rate control policies are studied in <cit.>. In <cit.>, the asymptotic small-delay regime is investigated. In <cit.>, a piecewise linear delay-power tradeoff curve was obtained along with an approximate closed form expression.

If one can show monotonicity or a threshold type of structure to the optimal policy for MDPs, it helps to substantially reduce the computation complexity in finding the optimal policy. Indeed, the optimal scheduling policies are shown to be threshold-based or monotone in <cit.>, proven by studying the convexity, superadditivity / subadditivity, or supermodularity / submodularity of expected cost functions by induction using dynamic programming. However, most of these results are limited to the unconstrained Lagrangian Relaxation problem. In <cit.>, some properties of the optimal policy for the constrained problem are described based on the results for the unconstrained problem. Detailed analysis on the optimal policy for the constrained problem is conducted in <cit.>. In <cit.>, properties such as unichain policies and multimodularity of costs are assumed to be true so that monotone optimal policies can be proven. In <cit.>, the transmission action is either 1 or 0, i.e. to transmit or not. In order to obtain the detailed structure of the solution to the constrained problem, we believe that the analysis of the Lagrangian relaxation problem and the analysis of the structure of the delay-power tradeoff curve should be combined together.

In <cit.>, we study the optimal delay-power tradeoff problem. In particular, we minimize the average delay given an average power constraint, considering Bernoulli arrivals and adaptive transmissions. Some technical details are given in <cit.>, where we proved that the optimal tradeoff curve is convex and piecewise linear, and the optimal policies are threshold-based, by Constrained Markov Decision Process formulation and steady-state analysis. In this paper, we substantially generalize the Bernoulli arrival process to an arbitrary i.i.d. distribution. We show that the optimal policies for this generalized model are still threshold-based. Furthermore, we develop an efficient algorithm to find the optimal policy and the optimal delay-power tradeoff curve.

The remainder of this paper is organized as follows. The system model and the constrained problem are introduced in Section II. We show that the optimal policy is threshold-based in Section III by using steady-state analysis and Lagrangian relaxation. Based on theoretical results, we propose an efficient algorithm in Section IV to obtain the optimal tradeoff curve and the corresponding policies. In Section V, theoretical results and the proposed algorithm are verified by simulations. Section VI concludes the paper.



§ SYSTEM MODEL

The system model is shown in  <ref>. We assume there are a[n] data packet(s) arriving at the end of the nth timeslot. The number a[n] is i.i.d. for different values of n and its distribution is given by Pr{a[n]=a}=α_a, where α_a≥ 0, a∈{0,1,⋯,A}, and ∑_a=0^A α_a=1. Therefore the expected number of packets arrived in each timeslot n is given by E_a= ∑_a=0^A aα_a.

Let s[n] denote the number of data packets transmitted in timeslot n. Assume that at most S packets can be transmitted in each timeslot because of the constraints of the transmitter, and S ≥ A. Let τ[n] denote the transmission power consumed in timeslot n. Assume transmitting s packet(s) will cost power P_s, where s∈{0,1,⋯,S}, therefore τ[n]=P_s[n]. Transmitting 0 packet will cost no power, hence P_0=0. In typical communications, the power efficiency decreases as the transmission rate increases, hence we assume that P_s is convex in s. Detailed explanations can be found in the Introduction section in <cit.>. The convexity of the power consumption function will be utilized in Theorem <ref> to prove that the optimal policy for the unconstrained problem is threshold-based.

Backlog packets are stored in a buffer with size Q. Let q[n]∈{0,1,⋯,Q} denote the queue length at the beginning of timeslot n. Since data arrive at the end of the timeslot, in order to avoid buffer overflow (i.e. q[n]>Q) and underflow (i.e. q[n]<0), we should have 0≤ q[n]-s[n] ≤ Q-A. Therefore the dynamics of the buffer is given as

    q[n+1]=q[n]-s[n]+a[n].


In timeslot n, we can decide how many packets to be transmitted based on the buffer state q[n]. It can be seen that this is a Markov Decision Process (MDP), where the queue length q[n] is the state of the MDP, and the number of packets transmitted in each timeslot s[n] is the action we take in each timeslot n. The probability distribution of the next state q[n+1] is given by

    Pr{q[n+1]=j|q[n]=q,s[n]=s}
    
    =    α_j-q+s    0 ≤ j-q+s ≤ A,
    
    0    otherwise.


We minimize the average queueing delay given an average power constraint, which makes it a Constrained Markov Decision Process (CMDP). For an infinite-horizon CMDP with stationary parameters, according to <cit.>, stationary policies are complete, which means stationary policies can achieve the optimal performance. Therefore we only need to consider stationary policies in this problem. Let f_q,s denote the probability to transmit s packet(s) when q[n]=q, i.e.,

    f_q,s=Pr{s[n]=s|q[n]=q}.

Then we have ∑_s=0^Sf_q,s=1 for q=0,⋯,Q. Since we guarantee that the transmission strategy will avoid overflow or underflow, we set

    f_q,s=0  if  q-s<0  or  q-s>Q-A.




Let F denote a (Q+1)×(S+1) matrix whose element in the (q+1)th row and the (s+1)th column is f_q,s. Therefore matrix F can represent a stationary transmission policy. Let P_F and D_F denote the average power consumption and the average queueing delay under policy F. Let ℱ denote the set of all feasible stationary policies that guarantee no queue overflow or underflow. Let ℱ_D denote the set of all stationary and deterministic policies which can guarantee no overflow or underflow. Thus to obtain the optimal tradeoff curve, we can minimize the average delay given an average power constraint P_th shown as



    min_F∈ℱ      D_F
    s.t.      P_F≤ P_th.



From another perspective, policy F will determine a point Z_F=(P_F,D_F) in the delay-power plane. Define ℛ={Z_F | F∈ℱ} as the set of all feasible points in the delay-power plane. Intuitively, since the power consumption for each data packet increases if we want to transmit faster, there is a tradeoff between the average queueing delay and the average power consumption. Thus the optimal delay-power tradeoff curve can be presented as ℒ={(P,D)∈ℛ|∀(P',D')∈ℛ, either P'≥ P or D'≥ D}.

If we fix a stationary policy for a Markov Decision Process, the Markov Decision Process will degenerate to a Markov Reward Process (MRP). Let λ_i,j denote the transition probability from state i to state j. According to the system model, because of the constraints of transmission and arrival processes, the state transition probability can be derived as

    λ_i,j=∑_s=max{0,i+A-Q,i-j}^min{S,i,i-j+A}α_j-i+sf_i,s.

An example of the transition diagram is shown in  <ref>, where λ_i,i for i=0,⋯,Q are omitted to keep the diagram legible.



The Markov chain could have more than one closed communication classes under certain transmission policies. Under this circumstance, the limiting probability distribution and the average cost are dependent on the initial state and the sample paths. In Appendix <ref>, it is proven that we only need to consider the cases where the Markov chain has only one closed communication class, which is called a unichain. Becausae of this key result, we focus only on the unichain cases in the following.



§ OPTIMAL THRESHOLD-BASED POLICY FOR THE CONSTRAINED MARKOV DECISION PROCESS


In this section, we will demonstrate that the optimal policy for the Constrained MDP problem is threshold-based. In other words, for an optimal policy, more data will be transmitted if the queue is longer. We give the rigorous definition of a stationary threshold-based policy F that, there exist (S+1) thresholds 0 ≤ q_F(0) ≤ q_F(1) ≤⋯≤ q_F(S) ≤ Q, such that f_q,s>0 only when q_F(s-1) ≤ q ≤ q_F(s) (set q_F(-1)=-1 for simplicity of notation). According to this definition, under policy F, when the queue state is larger than threshold q_F(s-1) and smaller than q_F(s), it transmits s packet(s). When the queue state is equal to threshold q_F(s), it transmits s or (s+1) packet(s). Note that under this definition, probabilistic policies can also be threshold-based.

In the following, we will first conduct the steady-state analysis of the Markov process, based on which we can show the properties of the feasible delay-power region and the optimal delay-power tradeoff, and then by proving that the Lagrangian relaxation problem has a deterministic and threshold-based optimal policy, we can finally show that the optimal policy for the constrained problem is threshold-based.



 §.§ Steady State Analysis

Since we can focus on unichain cases, which contain a single recurrent class plus possibly some transient states, the steady-state probability distribution exists for the Markov process. Let π_F(q) denote the steady-state probability for state q when applying policy F. Set π_F=[π_F(0),⋯,π_F(Q)]^T. Define Λ_F as a (Q+1)×(Q+1) matrix whose element in the (i+1)th column and the (j+1)th row is λ_i,j, which is determined by policy F. Set I as the identity matrix. Define 1=[1,⋯,1]^T, and 0=[0,⋯,0]^T. Set G_F=Λ_F-I. Set
H_F=[
[            1^T; G_F(0:(Q-1),:) ]] and
c=[
[ 1; 0 ]].

According to the definition of the steady-state distribution, we have G_Fπ_F=0 and 1^Tπ_F=1. For a unichain, the rank of G_F is Q. Therefore, we have H_F is invertible and

    H_Fπ_F=c.


For state q, transmitting s packet(s) will cost P_s with probability f_q,s. Define p_F=[∑_s=0^S P_s f_0,s,⋯,∑_s=0^S P_s f_Q,s]^T, which is a function of F. The average power consumption P_F can be expressed as

    P_F=∑_q=0^Qπ_F(q) ∑_s=0^S P_s f_q,s=p_F^Tπ_F.

Similarly, define d=[0,1,⋯,Q]^T. According to Little's Law, the average delay D_F under policy F is

    D_F=1/E_a∑_q=0^Q q π_F(q)=1/E_ad^Tπ_F.


The following theorem describes the structure of the feasible delay-power region and the optimal delay-power tradeoff curve.


The set of all feasible points in the delay-power plane, ℛ, and the optimal delay-power tradeoff curve ℒ, satisfy that


  * The set ℛ is a convex polygon.

  * The curve ℒ is piecewise linear, decreasing, and convex.

  * Vertices of ℛ and ℒ are all obtained by deterministic scheduling policies.

  * The policies corresponding to adjacent vertices of ℛ and ℒ take different actions in only one state.




See Appendix <ref>.




 §.§ Optimal Deterministic Threshold-Based Policy for the Lagrangian Relaxation Problem


In (<ref>), we formulate the optimization problem as a Constrained MDP, which is difficult to solve in general. Let μ≥ 0 denote the Lagrange multiplier. Consider the Lagrangian relaxation of (<ref>)

    min_F∈ℱ   D_F+μ P_F-μ P_th.


In (<ref>), the term -μ P_th is constant. Therefore, the Lagrangian relaxation problem is minimizing the weighted average cost D_F+μ P_F, which becomes an unconstrained infinite-horizon Markov Decision Process with an average cost criterion. It is proven in <cit.> that, there exists an optimal stationary deterministic policy. Moreover, the optimal policy for the relaxation problem has the following property.


An optimal policy F for the unconstrained Markov Decision Process is threshold-based. That is to say, there exists (S+1) thresholds q_F(0) ≤ q_F(1) ≤⋯≤ q_F(S), such that

    f_q,s=1     q_F(s-1)<q≤ q_F(s), s=0,⋯,S
    
    f_q,s=0    otherwise

where q_F(-1)=-1.



See Appendix <ref>.




 §.§ Optimal Threshold-Based Policy for the Constrained Problem

From another perspective, D_F+μ P_F=⟨(μ, 1),(P_F,D_F)⟩ can be seen as the inner product of vector (μ, 1) and Z_F. Since ℒ is piecewise linear, decreasing and convex, the corresponding Z_F minimizing the inner product will be obtained by the vertices of ℒ, as can be observed in  <ref>. Since the conclusion in Theorem <ref> holds for any μ, the vertices of the optimal tradeoff curve can all be obtained by optimal policies for the Lagrangian relaxation problem, which are deterministic and threshold-based. Moreover, from Theorem <ref>, the adjacent vertices of ℒ are obtained by policies which take different actions in only one state. Therefore, we can have the following theorem.


Given an average power constraint, the scheduling policy F to minimize the average delay takes the following form: there exists (S+1) thresholds q_F(0) ≤ q_F(1) ≤⋯≤ q_F(S), one of which we name q_F(s^*), such that

    {[                              f_q,s=1            q_F(s-1)<q≤ q_F(s),s≠ s^*;                            f_q,s^*=1               q_F(s^*-1)<q< q_F(s^*); 2@lf_q_F(s^*),s^*+f_q_F(s^*),s^*+1=1;                              f_q,s=0                            otherwise ].

where q_F(-1)=-1.



Since the optimal tradeoff curve is piecewise linear, assume Z_F is on the line segment between vertices Z_F' and Z_F”. According to Theorem <ref>, the form of optimal policies F' and F”, which are corresponding to vertices of the optimal tradeoff curve, satisfies (<ref>). Moreover, according to Theorem <ref>, the policies corresponding to adjacent vertices of ℒ take different actions in only one state. Define the thresholds for F' as q_F'(0),q_F'(1),⋯,q_F'(s^*),⋯,q_F'(S), then the thresholds for F' can be expressed as q_F'(0),q_F'(1),⋯,q_F'(s^*)-1,⋯,q_F'(S), where the two policies take different actions only in state q_F'(s^*). Since Z_F, the policy to obtain a point on the line segment between Z_F' and Z_F” is the convex combination of F' and F”, it should have the form shown in (<ref>).


We can see that the optimal policy for the Constrained Markov Decision Process may not be deterministic. At most two elements in the policy matrix F, i.e. f_q_F(s^*),s^* and f_q_F(s^*),s^*+1, can be decimal, while the other elements are either 0 or 1. Policies in this form also satisfy our definition of stationary threshold-based policy at the beginning of Section III.





§ ALGORITHM TO EFFICIENTLY OBTAIN THE OPTIMAL TRADEOFF CURVE

We design Algorithm <ref> to efficiently obtain the optimal delay-power tradeoff curve and the corresponding optimal policies. Similar to <cit.>, this algorithm takes advantage of the properties we have shown, i.e., the optimal delay-power tradeoff curve is piecewise linear, the vertices are obtained by deterministic threshold-based policies, and policies corresponding to two adjacent vertices take different actions in only one state. Therefore given the optimal policy for a certain vertex, we can narrow down the alternatives of optimal policies for its adjacent vertex. The policies corresponding to points between two adjacent vertices can also be easily generated.



Our proposed iterative algorithm starts from the bottom-right vertex of the optimal tradeoff curve, whose corresponding policy is known to transmit as much as possible. Then for each vertex we have determined, we enumerate the candidates for the next vertex. According to the properties we have obtained, we only need to search for deterministic threshold-based policies which take different actions in only one threshold. By comparing all the candidates, the next vertex will be determined by the policy candidate whose connecting line with the current vertex has the minimum absolute slope and the minimum length. Note that a vertex can be obtained by more than one policy, therefore we use lists ℱ_p and ℱ_c to restore all policies corresponding to the previous and the current vertices.

The complexity of this algorithm is much smaller than using general methods. Since during each iteration, one of the thresholds of the optimal policy will be decreased by 1, the maximum iteration times are AQ. Within each iteration, we have A thresholds to try. For each candidate, the most time consuming operation, i.e. the matrix inversion, costs O(Q^3). Therefore the complexity of the algorithm is O(A^2Q^4).

In comparison, we also formulate a Linear Programming (LP) to obtain the optimal tradeoff curve. As demonstrated in <cit.>, all CMDP problems with infinite horizon and average cost can be formulated as Linear Programming. In our case, by taking x_q,s=π(q) f_q,s as variables, we can formulate an LP with QS variables to minimize the average delay given a certain power constraint. Due to space limitation, we provide the LP without explanations.



    min     1/E_a∑_q=0^Q q ∑_s=0^S x_q,s
    s.t.     ∑_q=0^Q∑_s=0^S P_s x_q,s≤ P_th
       ∑_l=max{0,q-A}^q-1∑_a=0^A∑_s=0^l+a-qα_a x_l,s
       =∑_r=q^min{q+S-1,Q}∑_a=0^A∑_s=r+a-q+1^Sα_a x_r,s   q=1,⋯,Q
       ∑_q=0^Q∑_s=0^S x_q,s=1
        x_q,s=0     ∀ q-s<0  or  q-s>Q-A
        x_q,s≥ 0     ∀ 0 ≤ q-s ≤ Q-A.



By solving the LP, we can obtain a point on the optimal tradeoff curve. If we apply the ellipsoid algorithm to solve the LP problem, the computational complexity is O(S^4Q^4). It means that, the computation to obtain one point on the optimal tradeoff curve by applying LP is larger than obtaining the entire curve with our proposed algorithm. This demonstrates the inherent advantage of using the revealed properties of the optimal tradeoff curve and the optimal policies.







§ NUMERICAL RESULTS

In this section, we validate our theoretical results and the proposed algorithm by conducting LP numerical computation and simulations. We consider a practical scenario with adaptive M-PSK transmissions. The optional modulations are BPSK, QPSK, and 8-PSK. Assume the bandwidth = 1 MHz, the length of a timeslot = 10 ms, and the target bit error rate ber=10^-5. Assume a data packet contains 10,000 bits, and in each timeslot the number of arriving packet could be 0, 1, 2 or 3. Then by adaptively applying BPSK, QPSK, or 8-PSK, we can respectively transmit 1, 2, or 3 packets in a timeslot, which means S=3. Assume the one-sided noise power spectral density N_0=-150 dBm/Hz. The transmission power for different transmission rates can be calculated as P_0=0 J, P_1=9.0× 10^-14 J, P_2=18.2× 10^-14 J, and P_3=59.5× 10^-14 J. Set the buffer size as Q=100.

The optimal delay-power tradeoff curves are shown in  <ref> and  <ref>. In each figure, we vary the arrival process to get different tradeoff curves. As can be observed, the tradeoff curves generated by Algorithm <ref> perfectly match the Linear Programming and simulation results. As proven in Theorem <ref>, the optimal tradeoff curves are piecewise linear, decreasing, and convex. The vertices of the curves obtained by Algorithm <ref> are marked by squares. The corresponding optimal policies can be checked as threshold-based. The minimum average delay is 1 for all curves, because when we transmit as much as we can, all data packets will stay in the queue for exactly one timeslot. In  <ref>, with the average arrival rate increasing, the curve gets higher because of the heavier workload. In  <ref>, the three arrival processes have the same average arrival rate and different variance. When the variance gets larger, it is more likely that the queue size gets long in a short time duration, which leads to higher delay. It is interesting to characterize the effect of the variance in the arrival process, which we leave as a future work.



§ CONCLUSION

In this paper, we extend our previous work to obtain the optimal delay-power tradeoff and the corresponding optimal scheduling policy considering arbitrary i.i.d. arrival and adaptive transmissions. The scheduler optimize the transmission in each timeslot according to the buffer state. We formulate this problem as a CMDP, and minimize the average delay to obtain the optimal tradeoff curve. By studying the steady-state properties and the Lagrangian relaxation of the CMDP problem, we can prove that the optimal delay-power tradeoff curve is convex and piecewise linear, on which the adjacent vertices are obtained by policies taking different actions in only one state. Based on this, the optimal policies are proven to be threshold-based. We also design an efficient algorithm to obtain the optimal tradeoff curve and the optimal policies. Linear Programming and simulations are conducted to confirm the theoretical results and the proposed algorithm.





§ PROOF OF THE EQUIVALENCY TO REDUCE TO UNICHAIN CASES


We claim that we can focus only on the unichain cases, because for any Markov process with multiple recurrent classes determined by a certain policy, we can design a policy which leads to a unichain Markov process having the same performance as any of the recurrent class. We strictly express the reason as a proposition below, and give the detailed proof.


In the Markov Decision Process with arbitrary arrival and adaptive transmission, if there is more than one closed communication class in the Markov chain generated by policy F, which we define as 𝒞_1, ⋯, 𝒞_L where L>1, then for any 1≤ l ≤ L, there exists a policy F_l, under which the Markov chain has 𝒞_l as its only closed communication class. Furthermore, the steady-state distribution and the average cost of the Markov chain under F starting from state c∈𝒞_l are the same as the steady-state distribution and the average cost of the Markov chain under F_l.


Define the set of those transient states that have access to 𝒞_l as 𝒞_l^t. Define the set of transient states which don't have access to 𝒞_l as 𝒞_nl^t. Therefore {𝒞_1,⋯,𝒞_L,𝒞_l^t,𝒞_nl^t} is a partition of the states of the MDP. There should exists at least one state c∈⋃_i=1,i≠ l^+∞𝒞_i ∪𝒞_nl^t which is next to a state c'∈𝒞_l ∪𝒞_l^t. We can always change the action in state c such that state c can access the set 𝒞_l ∪𝒞_l^t. After the modification, state c will be a transient state which has access to 𝒞_l. The states which communicate with c will also be transient states which have access to 𝒞_l.

We update the partition of states since the policy is changed. According to the above description, the set 𝒞_l won't change, while the cardinality of 𝒞_l^t will be strictly increasing. Hence, by repeating the above operation for finite times, every state of the MDP will be partitioned in either 𝒞_l or 𝒞_l^t. The Markov chain generated by the modified policy has 𝒞_l as its only closed communication class, and the modified policy is the F_l we request.

Since the actions of states in 𝒞_l are the same for policy F and F_l, the steady-state distribution and the average cost corresponding to policy F starting from state c∈𝒞_l are the same as those under policy F_l.





§ PROOF OF THEOREM 1



In order to prove Theorem 1, we will first prove a lemma showing that the mapping from F to Z_F=(P_F,D_F) has a partially linear property in the first subsection. In the second subsection, we will prove that the set ℛ is a convex polygon, whose vertices are all obtained by deterministic scheduling policies, and the policies corresponding to adjacent vertices of ℛ take different actions in only one state. In the third subsection, we will prove that the set ℒ is piecewise linear, decreasing, and convex, whose vertices are obtained by deterministic scheduling policies, and the policies corresponding to adjacent vertices of ℒ take different actions in only one state.

In correspondence with Theorem 1, conclusion 1) in the theorem is proven in Subsection B, conclusion 2) is proven in Subsection C, and conclusion 3) and 4) are proven by combining results in Subsection B and C.



 §.§ Partially Linear Property of Scheduling Policies



F and F' are two policies different only when q[n]=q, i.e., these two matrices are different only in the (q+1)th row. Denote F”=(1-ϵ)F+ϵF' where 0≤ϵ≤ 1. Then1) There exists a certain 0≤ϵ'≤ 1 so that P_F”=(1-ϵ')P_F+ϵ' P_F' and D_F”=(1-ϵ')D_F+ϵ' D_F'. Furthermore, parameter ϵ' is a continuous non-decreasing function of ϵ.2) When ϵ changes from 0 to 1, point Z_F” moves on the line segment Z_FZ_F' from Z_F to Z_F'.



In the following, the two conclusions of the lemma will be proven one by one.

1) According to the definition of H_F and p_F, we have that if F”=(1-ϵ)F+ϵF', then H_F”=(1-ϵ)H_F+ϵH_F' and p_F”=(1-ϵ)p_F+ϵp_F'. Set ΔH=H_F'-H_F and Δp=p_F'-p_F. Since F and F' are different only in the (q+1)th row, it can be derived that the (q+1)th column of ΔH is the only column that can contain non-zero elements, and the (q+1)th element of Δp is its only non-zero element. Therefore ΔH can be expressed as [0,⋯,δ_q,⋯,0], where δ_q is its (q+1)th column, and Δp can be expressed as [0,⋯,ζ_q,⋯,0]^T, where ζ_q is its (q+1)th element. Based on this, we set

    H_F^-1=[
    h_0^T, h_1^T, ⋯, h_Q^T
    ]^T.

Hence

    (H_F^-1ΔH)H_F^-1=[
    [ (h_0^Tδ_q)h_q^T; (h_1^Tδ_q)h_q^T;               ⋮; (h_Q^Tδ_q)h_q^T ]].


By mathematical induction, we can prove that for i≥ 1,

    (H_F^-1ΔH)^iH_F^-1
    
    =   [
    [ (h_0^Tδ_q)(h_q^Tδ_q)^i-1h_q^T; (h_1^Tδ_q)(h_q^Tδ_q)^i-1h_q^T;                             ⋮; (h_Q^Tδ_q)(h_q^Tδ_q)^i-1h_q^T ]]
    
    =   (h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1

and

    Δp^TH_F^-1(H_F^-1ΔH)^i-1
    
    =   ζ_q(h_q^Tδ_q)^i-1h_q^T.


Therefore,

    (H_F+ϵΔH)^-1
    
    =   ∑_i=0^+∞ (-ϵ)^i(H_F^-1ΔH)^iH_F^-1
    
    =   H_F^-1
    +∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1.


We have P_F=p_F^TH_F^-1c and D_F=1/E_ad^TH_F^-1c. Hence

    P_F”-P_F/P_F'-P_F
    
    =   (p_F+ϵΔp)^T(H_F+ϵΔH)^-1c-p_F^TH_F^-1c/(p_F+Δp)^T(H_F+ΔH)^-1c-p_F^TH_F^-1c
    
    =   [ p_F^T[(H_F+ϵΔH)^-1-H_F^-1]c;         +ϵΔp^T(H_F+ϵΔH)^-1c ]/[ p_F^T[(H_F+ΔH)^-1-H_F^-1]c;          +Δp^T(H_F+ΔH)^-1c ]
    
    =   [ p_F^T[∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1]c;          -Δp^T[∑_i=1^+∞ (-ϵ)^i(H_F^-1ΔH)^i-1H_F^-1]c ]/[ p_F^T[∑_i=1^+∞(-1)^i(h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1]c;          -Δp^T[∑_i=1^+∞ (-1)^i(H_F^-1ΔH)^i-1H_F^-1]c ]
    
    =   [ ∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1p_F^T(H_F^-1ΔH)H_F^-1c;            -∑_i=1^+∞ (-ϵ)^iζ_q(h_q^Tδ_q)^i-1h_q^Tc ]/[ ∑_i=1^+∞(-1)^i(h_q^Tδ_q)^i-1p_F^T(H_F^-1ΔH)H_F^-1c;            -∑_i=1^+∞ (-1)^iζ_q(h_q^Tδ_q)^i-1h_q^Tc ]
    
    =   ∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1/∑_i=1^+∞(-1)^i(h_q^Tδ_q)^i-1
    
    =   ϵ+ϵh_q^Tδ_q/1+ϵh_q^Tδ_q

and

    D_F”-D_F/D_F'-D_F
    
    =   d^T(H_F+ϵΔH)^-1c-d^TH_F^-1c/d^T(H_F+ΔH)^-1c-d^TH_F^-1c
    
    =   d^T(∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1)c/d^T(∑_i=1^+∞(-1)^i(h_q^Tδ_q)^i-1(H_F^-1ΔH)H_F^-1)c
    
    =   ∑_i=1^+∞(-ϵ)^i(h_q^Tδ_q)^i-1/∑_i=1^+∞(-1)^i(h_q^Tδ_q)^i-1
    
    =   ϵ+ϵh_q^Tδ_q/1+ϵh_q^Tδ_q.

Hence P_F”-P_F/P_F'-P_F=D_F”-D_F/D_F'-D_F=ϵ+ϵh_q^Tδ_q/1+ϵh_q^Tδ_q=ϵ', so that P_F”=(1-ϵ')P_F+ϵ' P_F' and D_F”=(1-ϵ')D_F+ϵ' D_F'. Furthermore, it can be seen that ϵ'=ϵ+ϵh_q^Tδ_q/1+ϵh_q^Tδ_q is a continuous nondecreasing function.

2) From the first part, we proved P_F”-P_F/P_F'-P_F=D_F”-D_F/D_F'-D_F=ϵ' and ϵ' is a continuous non-decreasing function of ϵ. When ϵ=0, we have ϵ'=0. When ϵ=1, we have ϵ'=1. Therefore when ϵ changes from 0 to 1, the point (P_F”,D_F”) moves on the line segment from (P_F,D_F) to (P_F',D_F'). The slope of the line can be expressed as

    D_F'-D_F/P_F'-P_F=1/E_ad^T(H_F+ΔH)^-1c-1/E_ad^TH_F^-1c/
    (p_F+Δp)^T(H_F+ΔH)^-1c-p_F^TH_F^-1c
    
    
    
    
    
    =   1/E_ad^TH_F^-1ΔHH_F^-1c/p_F^TH_F^-1ΔHH_F^-1c-ζ_qh_q^Tc=d^TH_F^-1δ_q/E_a (p_F^TH_F^-1δ_q-ζ_q).





 §.§ Properties of set ℛ

In this subsection, we will prove that ℛ, the set of all feasible points in the delay-power plane, is a convex polygon whose vertices are all obtained by deterministic scheduling policies. Moreover, the policies corresponding to adjacent vertices of ℛ take different actions in only one state.



Define 𝒞=conv {Z_F | F∈ℱ_D } as the convex hull of points corresponding to deterministic scheduling policies in the delay-power plane. Hence we will show that ℛ is a convex polygon whose vertices are all obtained by deterministic scheduling policies by proving ℛ=𝒞.

The proof is made up of three parts. In Part I, we will prove ℛ⊆𝒞 by the construction method. Part II is the most difficult part. We will first define the concepts of basic polygons and compound polygons, then prove their convexity, based on which ℛ⊇𝒞 can be proven. By combining the results from Part I and II, we will have ℛ=𝒞. Finally, in Part III, it will be shown that policies corresponding to adjacent vertices of ℛ are different in only one state.

Part I. Prove ℛ⊆𝒞

For any probabilistic policy F where 0<f_q^*,s^*<1, we construct

    F'=
    
    f'_q,s=1     q=q^*,s=s^*
    
    f'_q,s=0     q=q^*,s ≠ s^*
    
    f'_q,s=f_q,s   else

and

    F”=
    
    f”_q,s=0     q=q^*,s=s^*
    
    f”_q,s=f_q,s/1-f_q^*,s^*    q=q^*,s ≠ s^*
    
    f”_q,s=f_q,s   else.


Since 0 ≤f_q,s/1-f_q^*,s^*≤ 1, and the fact that whenever f_q,s=0, it must holds that f'_q,s=f”_q,s=0, we can conclude that policies F' and F” are feasible. It can be seen that F=f_q^*,s^*F'+(1-f_q^*,s^*)F”. Since F is a convex combination of policy F' and policy F”, also F' and F” are different only in the (q^*+1)th row, from Lemma <ref>, we know that Z_F is a convex combination of Z_F' and Z_F”. Note that f'_q^*,s^* and f”_q^*,s^* are integers. Also, in matrices F' and F”, no new decimal elements are going to be introduced. Hence in finite steps, the point Z_F can be expressed as the convex combination of points corresponding to deterministic scheduling policies. That is to say Z_F∈𝒞. From the arbitrariness of F, we have ℛ⊆𝒞.

Part II. Prove ℛ⊇𝒞

In this part, we will begin with the concepts of basic polygons and compound polygons in Part II.0. Then we will prove that basic polygons and compound polygons are convex in Part II.1 and Part II.2 respectively. Based on the above results, we will prove ℛ⊇𝒞 in Part II.3.

Part II.0 The Concepts of Basic Polygons and Compound Polygons

For two deterministic policies F and F' which are different in K states, namely q_1,⋯,q_K, define
F_b_1,b_2,⋯,b_K(q,:)=
(1-b_k)F(q,:)+b_kF'(q,:)     q=q_k,
F(q,:)     q≠ q_1,⋯,q_K,
where 0 ≤ b_k ≤ 1 for all k. Thus F_0,0,⋯,0=F, and F_1,1,⋯,1=F'. With more b_k close to 0, the policy is more like F. With more b_k close to 1, the policy is more like F'. For policies F_b_1,⋯,b_k,⋯,b_K and F_b_1,⋯,b_k',⋯,b_K where b_k ≠ b_k', since they are different in only one state, according to Lemma <ref>, the delay-power point corresponding to their convex combination Z_ϵF_b_1,⋯,b_k,⋯,b_K + (1-ϵ)F_b_1,⋯,b_k',⋯,b_K is the convex combination of Z_F_b_1,⋯,b_k,⋯,b_K and Z_F_b_1,⋯,b_k',⋯,b_K. However, for two policies which are different in more than one state, the delay-power points corresponding to policies of their convex combination are not necessarily the convex combination of delay-power points corresponding to themselves. Therefore, we introduce the concept of generated polygon for the delay-power region of point set corresponding to policies which are convex combinations of the two policies. We plot Z_F_b_1,⋯,b_K, where b_k=0 or 1 for all 1≤ k ≤ K, and connect the points whose corresponding policies are different in only one state. Therefore any point on any line segment can be obtained by a certain policy. We define the figure as a polygon generated by F and F'. The red polygon in  <ref> and the polygon in  <ref> are demonstrations where F and F' are different in 2 and 3 states respectfully. If K=2, we call the polygon a basic polygon. If K>2, we call it a compound polygon. As demonstrated in  <ref>, a compound polygon contains multiple basic polygons.

Part II.1 Prove a Basic Polygon is Convex and Any Point Inside a Basic Polygon can be Obtained by a Policy



For better visuality, in  <ref>, we simplify the notation Z_F_b_1,b_2 as b_1,b_2. By considering all possible relative positions of Z_F_0,0, Z_F_0,1, Z_F_1,0, and Z_F_1,1, there are 3 possible shapes of basic polygons in total, as shown in  <ref>-<ref> respectfully. We name them as the normal shape, the boomerang shape, and the butterfly shape. The degenerate cases such as triangles, line segments and points are considered included in the above three cases. Besides F_b_1,b_2 with integral b_1,b_2 and the line segments connecting them, in the figures we also plot the points corresponding to policy F_b_1,b_2 where one of b_1,b_2 is integer and the other one is decimal. We connect the points corresponding to policies which have the same b_1 or b_2 with dashed lines. As demonstrated in  <ref>, we draw line segments Z_F_b_1,0Z_F_b_1,1 where b_1=0.1,0.2,⋯,0.9 and Z_F_0,b_2Z_F_1,b_2 where b_2=0.1,0.2,⋯,0.9. For any specific b_1 and b_2, the point Z_F_b_1,b_2 should be on both Z_F_b_1,0Z_F_b_1,1 and Z_F_0,b_2Z_F_1,b_2. Because of the existence of Z_F_b_1,b_2, line segments Z_F_b_1,0Z_F_b_1,1 and Z_F_0,b_2Z_F_1,b_2 should always have an intersection point for any specific b_1 and b_2. However, if there exist line segments outside the polygon, there exist b_1 and b_2 whose line segments don't intersect. Therefore, in the boomerang shape, there will always exist b_1 and b_2 whose line segments don't intersect. In the butterfly shape, there will exist b_1 and b_2 whose line segments don't intersect except the case that all the line segments are inside the basic polygon, as shown in  <ref>, which is named as the slender butterfly shape. In the slender butterfly shape, there exists a specific b_1^* such that Z_F_b_1^*,0Z_F_b_1^*,1 degenerates into a point, or there exists a specific b_2^* such that Z_F_0,b_2^*Z_F_1,b_2^* degenerates into a point. Without loss of generality, we assume it is the b_1^* case. It means that under policy F_b_1^*,b_2, state q_2, the state corresponding to b_2, is a transient state. For b_1∈(b_1^*-ϵ,b_1^*+ϵ) when ϵ is small enough, the Markov chain applying policy F_b_1,b_2 also has q_2 as a transient state, therefore Z_F_b_1,0Z_F_b_1,1 also degenerates into a point. Thus Z_F_0,0Z_F_1,0 and Z_F_0,1Z_F_1,1 overlap, which means the slender butterfly shape always degenerates to a line segment, which can also be considered as a normal shape. Since the normal shape is the only possible shape of a basic polygon, the basic polygon is convex. Since the transition from the point Z_F_0,0 to Z_F_1,1 is termwise monotone and continuous, every point inside the basic polygon can be obtained by a policy.

Part II.2 Prove a Compound Polygon is Convex

For any two deterministic policies F and F', if the compound polygon generated by them is not convex, then there must exist two vertices whose connecting line is outside the compound polygon, as demonstrated by Z_1 Z_2 in  <ref>. Therefore, there must also exist two vertices who are connecting to the same point and their connecting line is outside the compound polygon, as demonstrated by Z_1 Z_3. The policies corresponding to these two vertices must be different in only two states based on previous conclusions, therefore there must be a basic polygon generated by them, as demonstrated in  <ref> by the filled polygon. Since Z_1 Z_3 is outside the compound polygon, it is for sure that Z_1 Z_3 is outside the basic polygon too. This is impossible because basic polygons are always convex. Hence we can conclude that all generated compound polygons are convex.

Part II.3 Prove ℛ⊇𝒞

For arbitrary point C∈𝒞, it will fall into one of the compound polygons, because otherwise, there will be at least one point corresponding to a deterministic policy outside any compound polygons. All compound polygons can be covered by basic polygons, therefore C is inside at least one basic polygon. Since any point inside a basic polygon can be obtained by a policy, the point C∈ℛ. From the arbitrariness of C, we have ℛ⊇𝒞.

From Part II.1 and Part II.2, it can be proven that ℛ=𝒞. Since there are only finite deterministic policies in total, the set ℛ is a convex polygon with its vertices all obtained by deterministic scheduling policies.

Part III. Adjacent Vertices of ℛ

For any two adjacent vertices Z_F and Z_F' of ℛ, if F and F' are different in more than one state, the polygon generated by them is convex. If the line segment Z_FZ_F' is inside the generated polygon, Z_F and Z_F' are impossible to be adjacent. If the line segment Z_FZ_F' is on the boundary of the generated polygon, there will be other vertices between them, then Z_F and Z_F' are still not adjacent. Therefore, we can conclude that policies F and F' are deterministic and different in only one state.



 §.§ Properties of set ℒ

In this subsection, we will prove that the optimal delay-power tradeoff curve ℒ is piecewise linear, decreasing, and convex. The vertices of the curve are obtained by deterministic scheduling policies. Moreover, the policies corresponding to adjacent vertices of ℒ take different actions in only one state.


Monotonicity:

Since ℒ={(P,D)∈ℛ|∀(P',D')∈ℛ, either P'≥ P or D'≥ D}, for any (P_1,D_1),(P_2,D_2)∈ℒ where P_1<P_2, we should have D_1≥ D_2. Therefore ℒ is decreasing.

Convexity:

Since ℛ is a convex polygon, for any (P_1,D_1),(P_2,D_2)∈ℒ, their convex combination is (θ P_1+(1-θ) P_2,θ D_1+(1-θ) D_2)∈ℛ. Hence there exists a point (P_θ,D_θ) on ℒ where P_θ = θ P_1+(1-θ) P_2, and D_θ≤θ D_1+(1-θ) D_2. Therefore ℒ is convex.

Piecewise Linearity:

Since ℛ is a convex polygon, it can be expressed as the intersection of a finite number of halfspaces, i.e., ℛ=⋂_i=1^I{(P,D)|a_i P+b_i D ≥ c_i}. We divide (a_i,b_i,c_i) into 2 categories according to the value of a_i and b_i as (a_i^+,b_i^+,c_i^+) for i=1,⋯,I^+ if a_i>0 and b_i>0, and (a_i^-,b_i^-,c_i^-) for i=1,⋯,I^- if a_i≤ 0 or b_i≤ 0. We have I=I^++I^- and I^+,I^->0. Then ℛ=⋂_i=1^I^+{(P,D)|a_i^+ P+b_i^+ D ≥ c_i^+}∩⋂_i=1^I^-{(P,D)|a_i^- P+b_i^- D ≥ c_i^-}. For 1≤ l ≤ I^+, define ℒ_l={(P,D)|a_l^+ P+b_l^+ D = c_l^+}∩⋂_i=1,i≠ l^I^+{(P,D)|a_i^+ P+b_i^+ D ≥ c_i^+}∩⋂_i=1^I^-{(P,D)|a_i^- P+b_i^- D ≥ c_i^-}.

For all (P,D)∈ℒ_l, we have (P,D)∈ℛ. For all (P',D')∈ℛ, since a_l^+ P'+b_l^+ D' ≥ c_l^+=a_l^+ P+b_l^+ D, it should hold that P'≥ P or D'≥ D. According to the definition of ℒ, we have (P,D)∈ℒ. Therefore ℒ_l ⊆ℒ.

For all (P,D)∈ℒ, we consider three cases: 1) If a_i^+ P+b_i^+ D > c_i^+ for all 1 ≤ i ≤ I^+ and a_i^- P+b_i^- D > c_i^- for all b_i^->0, set ϵ=min_b_i>0a_i P+b_i D-c_i/b_i so that a_i P+b_i (D-ϵ) ≥ c_i for all b_i>0. Since (P,D)∈ℛ, for all b_i≤ 0 a_i P+b_i D ≥ c_i, therefore a_i P+b_i (D-ϵ) ≥ c_i for all b_i≤ 0. Hence (P,D-ϵ)∈ℛ, which is against the definition of ℒ. 2) If a_i^+ P+b_i^+ D > c_i^+ for all 1 ≤ i ≤ I^+ and a_i^- P+b_i^- D > c_i^- for all a_i^->0, set ϵ=min_a_i>0a_i P+b_i D-c_i/a_i so that a_i (P-ϵ)+b_i D ≥ c_i for all a_i>0. Since (P,D)∈ℛ, for all a_i≤ 0 a_i P+b_i D ≥ c_i, therefore a_i (P-ϵ)+b_i D ≥ c_i for all a_i≤ 0. Hence (P-ϵ,D)∈ℛ, which is against the definition of ℒ. 3) If a_i^+ P+b_i^+ D > c_i^+ for all 1 ≤ i ≤ I^+, and there exists i^* and j^* such that a_i^*^-≤0, b_i^*^->0, a_j^*^->0, b_j^*^-≤0, a_i^*^- P+b_i^*^- D = c_i^*^-, a_j^*^- P+b_j^*^- D = c_j^*^-. For all (P',D')∈ℛ, either P'≥ P, D'≥ D or P'≤ P, D'≤ D. If there exists P'<P and D'<D, then (P,D) is against the definition of ℒ. If P'≤ P and D'≤ D for all (P',D'), since for all 1 ≤ i ≤ I^+, we have a_i^+ P+b_i^+ D > c_i^+, therefore a_i^+ P'+b_i^+ D' > c_i^+. Hence ℒ_i∩ℛ=∅, which is against the condition. From the above three cases, for all (P,D)∈ℒ, there exists at least one certain l^* such that a_l^*^+ P+b_l^*^+ D = c_l^*^+, which means (P,D)∈ℒ_l^*.

From above we can see that ℒ=⋃_l=1^I^+ℒ_l. Therefore ℒ is piecewise linear.

Properties of Vertices of ℒ:

The vertices of ℒ are also the vertices of ℛ, and adjacent vertices of ℒ are also adjacent vertices of ℛ. From the results in Section B, vertices of ℒ are obtained by deterministic scheduling policies, and the policies corresponding to adjacent vertices of ℒ are different in only one state.





§ PROOF OF THEOREM 2



From the literature, it is proven that there exists an optimal deterministic stationary policy. Therefore, in the proof, we only consider deterministic policies. Let s(q) denote the transmitting packet number when q[n]=q. Define

    h^(m+1)(q,s)
    
    =    q+ μ P_s+∑_a=0^A α_a[h^(m)(q-s+a)-h^(m)(a)].


In the following, we will apply a nested induction method to prove the theorem, which utilizes the policy iteration algorithm for Markov Decision Processes. For a Markov Decision Process considering an average cost, the policy iteration algorithm, which is shown in Algorithm <ref>, can always converge to the optimal scheduling policy in finite steps, which is proven in <cit.> and <cit.>. In the algorithm, the function h^(m)(q) will in the final converge to h(q), which is normally known as the potential function or the bias function of the Markov Decision Process. The function h(q) can be interpreted as the expected total difference between the cost starting from a specific state and the stationary cost.

We sketch the proof as follows. Initially, we assign h^(0)(q) as a strictly convex function in q. Then in Part I, it will be demonstrated by the mathematical induction method that, in the policy improvement step of the policy iteration algorithm, for any m, if h^(m)(q) is strictly convex in q, then s^(m+1)(q) has the threshold-based property. On the other hand, in Part II, we show that in the policy evaluation step of the policy iteration algorithm, if s^(m+1)(q) has the threshold-based property, then h^(m+1)(q) is strictly convex in q. Based on the above derivations, we can prove the required conclusion by mathematical induction.



Part I. The Policy Improvement Step: Convexity of h^(m)(q) in q → threshold-based property of s^(m+1)(q)

Assume h^(m)(q) is strictly convex in q. In the following, we will show that s^(m+1)(q) has the threshold-based property.


  * For a feasible policy, we have s^(m+1)(0)=0, and s^(m+1)(1)=0 or 1. Therefore s^(m+1)(q+1)-s^(m+1)(q)=0 or 1 when q=0.

  * Define s_1=s^(m+1)(q_1) for a specific q_1. According to the Policy Improvement step, we have inequalities

    h^(m+1)(q_1,s_1) 
    ≤    h^(m+1)(q_1,s_1-δ), ∀ 0≤δ≤ s_1,
        h^(m+1)(q_1,s_1) 
    ≤    h^(m+1)(q_1,s_1+δ), ∀ 0≤δ≤ S-s_1.


Since h^(m)(q) is strictly convex in q, we have

    h^(m)(q_1+1-s_1+a)-h^(m)(q_1-s_1+a)
    
    <     h^(m)(q_1+1-(s_1-δ)+a)
        -h^(m)(q_1-(s_1-δ)+a), 0≤ a≤ A.


Since P_s is strictly convex, we have

    P_s_1+1-P_s_1<P_s_1+1+δ-P_s_1+δ.

From (<ref>) and (<ref>), we can obtain that

    h^(m+1)(q_1+1,s_1)
    
    <     h^(m+1)(q_1+1,s_1-δ), ∀ 0 ≤δ≤ s_1.


From (<ref>) and (<ref>), we can obtain that

    h^(m+1)(q_1+1,s_1+1)
    
    <     h^(m+1)(q_1+1,s_1+1+δ), ∀ 0 ≤δ≤ S-s_1-1.


From (<ref>) and (<ref>), it is shown that s^(m+1)(q_1+1) can only be s_1 or s_1+1. That is to say, we have s^(m+1)(q_1+1)-s^(m+1)(q_1)=0 or 1.


From the above derivations, we prove by mathematical induction that s^(m+1)(q) has the threshold-based property.

Part II. The Policy Evaluation Step: Threshold-based property of s^(m+1)(q) → convexity of h^(m+1)(q) in q

Assume s^(m+1)(q) has the threshold-based property. We continue to use the same notation as in Part I, i.e., define s_1=s^(m+1)(q_1) for a specific q_1, and s^(m+1)(q_1+1)=s_1 or s_1+1.


  * If s^(m+1)(q_1+1)=s_1,

    h^(m+1)(q_1+1)-h^(m+1)(q_1)
    ≤    h^(m+1)(q_1+1, s_1+1)-h^(m+1)(q_1,s_1)
    
    =      (q_1+1)+ μ P_s_1+1
        +∑_a=0^A α_a[h^(m)((q_1+1)-(s_1+1)+a)-h^(m)(a)]
        -[ q_1+ μ P_s_1+∑_a=0^A α_a[h^(m)(q_1-s_1+a)-h^(m)(a)]
    
    =     1+μ (P_s_1+1-P_s_1).

On the other hand,

    h^(m+1)(q_1+1)-h^(m+1)(q_1)
    
    >    h^(m+1)(q_1+1,s_1)-h^(m+1)(q_1,s_1-1)
    
    =    (q_1+1)+μ P_s_1
        +∑_a=0^A α_a[h^(m)((q_1+1)-s_1+a)-h^(m)(a)]
        -[q_1+ μ P_s_1-1
        +∑_a=0^A α_a[h^(m)(q_1-(s_1-1)+a)-h^(m)(a)]
    
    =    1+μ (P_s_1-P_s_1-1).


  * If s^(m+1)(q_1+1)=s_1+1,

    h^(m+1)(q_1+1)-h^(m+1)(q_1)
    
    =    (q_1+1)+ μ P_s_1+1
        +∑_a=0^A α_a[h^(m)((q_1+1)-(s_1+1)+a)-h^(m)(a)]
        -[q_1+ μ P_s_1+∑_a=0^A α_a[h^(m)(q_1-s_1+a)-h^(m)(a)]
    
    =   1+ μ (P_s_1+1-P_s_1).



In conclusion, for any specific q_1, we have

    1+μ(P_s_1-P_s_1-1) < h^(m+1)(q_1+1)-h^(m+1)(q_1) ≤
        1+μ(P_s_1+1-P_s_1).

That is to say, h^(m+1)(q+1)-h^(m+1)(q) is strictly increasing. Therefore, we have h^(m+1)(q) is strictly convex in q.

Based on our assumption for the initial value h^(0)(q), as well as the derivations in Part I and II, it is proven by mathematical induction that s^(m)(q) holds the threshold-based property for all m ≥ 1. Since s^(m)(q) converges to the optimal policy s(q) for sure in finite steps, the optimal policy s(q) will also hold the threshold-based property.



IEEEtran



