# Optimality of Multichannel Myopic Sensing in the Presence of Sensing Error for Opportunistic Spectrum Access

Authors: Xiaofeng Jiang; Hongsheng Xi
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The optimization problem for the performance of opportunistic spectrum access is considered in this study. A user, with the limited sensing capacity, has opportunistic access to a communication system with multiple channels. The user can only choose several channels to sense and decides whether to access these channels based on the sensing information in each time slot. Meanwhile, the presence of sensing error is considered. A reward is obtained when the user accesses a channel. The objective is to maximize the expected (discounted or average) reward accrued over an infinite horizon. This problem can be formulated as a partially observable Markov decision process. This study shows the optimality of the simple and robust myopic policy which focuses on maximizing the immediate reward. The results show that the myopic policy is optimal in the case of practical interest.


---

## Body

## 1. Introduction

There is a significant increase in the demand for radio spectrum with the emergence of new applications and the compelling need for mobile services in recent years. This is partly due to the increasing interest of consumers in convenient and ubiquitous wireless services, and the interest has been driving the evolution of wireless networks to high speed data networks. However, ever since the 1920s, in order to avoid the serious interference in wireless services, the wireless providers have been required to apply an exclusive license from the government. Today, it is becoming very difficult to find vacant bands to either deploy new services or to enhance the existing ones with most of the spectrum being already allocated [1]. On the other hand, not every channel in every band is in use all the time; a large number of vacant spectrum holes can be discovered in the spectrum [2]. A technique for opportunistic spectrum access can effectively utilize these spectrum holes.The spectrum sensing for detecting spectrum holes is the precondition for opportunistic spectrum access. However, the existing spectrum sensing techniques has to face one main challenge: wideband sensing which is hard to be implemented for the main reason of hardware limitations [3]. The user usually uses a tunable narrowband bandpass filter at the radio frequency (RF) front-end to sense one channel at a time due to the costliness of a wideband RF front-end. Consequently, it is a lot of time delay for detecting all channels. Meng et al. [4] study this problem with the method of compressive sensing based on the sparse observations of sensing information. Equipped with frequency selective filters, the sparse sensing information vectors of multiple channels are linearly combined and compressed. Multiple channels thus can be sensed simultaneously. However, it is used in the case of less practical interest due to the requirements of sparse observations and frequency selective filters. The basic theory of compressive sensing is given in the work of [5–8]. Some other studies focus on the reliability of sensing information. Different SNR estimations and channel fading environments are considered in [9, 10] to improve the reliability of sensing information. Chen [11] studies the optimum number of collaborative users to get the tradeoff of the reliability and the complexity. The Byzantine attacks which come from malicious users and carry false sensing data are taken into account in [12].The studies of [13–16] also exploit a method to solve the problem of wideband sensing by estimating the information of all channels with only a small amount of sensing results. The sensing procedure is modeled as a partially observed Markov decision process (POMDP). Zhao et al. [13] propose this idea and a myopic sensing method. Wang et al. [14] exploit the impact of the rateless code. Lingcen et al. [15] modify the cost function of POMDP with the switching time.We consider the communication system where a user has opportunistic access to multiple channels like the model of [13] but is limited to sensing and transmitting only on several channels at a given time due to its hardware limitation. Meanwhile, the presence of sensing error is also considered. We explore the problem to maximize the performance of opportunistic access when the past observations and the knowledge of the stochastic properties of these channels are given. This problem can be described as a partially observable Markov decision process since the user does not have full knowledge of the availabilities of all channels. We examine the optimality of the myopic policy for this problem in this study for the reason that the myopic policy is very simple and robust. Specially, we show that the myopic policy is optimal in the case of practical interest. Ahmad et al. [16] also study the optimality of the myopic sensing. However, we have discovered that the study of [16] is only suitable for the special case where the one-channel myopic sensing and the absence of sensing error are considered. If we consider the multichannel myopic sensing or the presence of sensing error, the study of [16] cannot hold its conclusion. The reason is that the mathematic method of the proof of [16] is very special for the case of one-channel myopic sensing, and Lemmas 2, 3, 4, and 5 of [16] cannot be improved to prove the optimality under the other conditions. We propose the proof of the optimality of multichannel myopic sensing in the presence of sensing error. Our mathematic method is rigorous and quite different from the method of [16]; we use two functions to give the proof, and the method is generally effective for such issues.The rest of this paper is organized as follows. We formulate the problem in Section2 and give the definition of the myopic policy in Section 3. We prove the optimality of the myopic policy in Section 4 and extend the results from the finite horizon to the infinite horizon. The numerical results of the performance comparison of the myopic policy and the optimal policy are given in Section 5, and the conclusion is drawn in Section 6.


## 2. System Model

Consider a spectrum consisting ofN independent and statistically identical wireless channels; each channel has two states {0(occupied),1(idle)}, and the state transition is given by a two-state discrete time Markov chain shown in Figure 1. It is supposed that these channels evolve according to a synchronous time slot structure indexed by t, where t=1,2,…,T. Specially, the states of all channels at time t are denoted by S(t)=[S1(t),…,SN(t)], where Sn(t)∈{0,1}.Figure 1
State transition of channels.We consider a user seeking the spectrum holes in these channels for opportunistic access. At the beginning of the time slott, the user selects a set A1(t) of channels to sense and a set A2(t) of channels to access, where A2(t)⊆A1(t). However, due to hardware limitation, |A1(t)| and |A2(t)| are usually much smaller than N. The user can only sense the channels in A1(t) and does not have the states of all channels S(t), when a decision is made at time t. Consequently, the spectrum is not fully observable to the users. For clarity, we use a(t)={A1(t),A2(t)} to denote the action of the user at time t and use hA1(t)(t)=[hi1(t),…,hi|A1(t)|(t)] to denote the sensing information of channels, where hA1(t)(t)∈{0,1}|A1(t)| and ik is the index of the channel in A1(t). Specially, we cannot guarantee the absolute reliability of the sensing information in the presence of sensing error; the detection and false alarm probabilities should be taken into account. Here, the detection probability denoted by pdik(t) and the false alarm probability denoted by pfik(t) [17] are the conditional probabilities that the state of the channel ik is actually 0(occupied) when the observations are 0(occupied) and 1(idle), respectively.For making the optimal decision, a sufficient statistic of this system denoted byΛ(t)=[λ1(t),…,λN(t)] is given, where λn(t) is the conditional probability that the channel n is idle at the beginning of the time slot t given all past observations and actions, and this conditional probability is called the idle conditional probability. Due to the Markovian property of the channels, the future idle conditional probability is only a function of the current idle conditional probability and the action.Proposition 1.
The relationship betweenΛ(t) and Λ(t+1) can be given by (3).Proof.
We first consider case 1 thatn∈A1(t) and hn(t)=1 to simplify the proof; the events Sn(t+1)=1, Sn(t)=1, Sn(t)=0, and hn(t)=1 are denoted by A, B1, B2, and C, respectively. The value of λn(t+1) in case 1 can be replaced by P{A∣C}; then we can get
(1)P{A∣C}=∑i={1,2}‍P{A,Bi∣C}=∑i={1,2}‍P{Bi,C}P{C}P{A,Bi,C}P{Bi,C}=∑i={1,2}‍P{Bi∣C}P{A∣Bi,C}.
SinceA is independent of C when Bi has been determined, we can get
(2)P{A∣C}=∑i={1,2}‍P{Bi∣C}P{A∣Bi}=p11(1-pfn(t))+p01pfn(t)(3)λn(t+1)={P{Sn(t+1)=1∣hn(t)=1}ifn∈A1(t),hn(t)=1P{Sn(t+1)=1∣hn(t)=0}ifn∈A1(t),hn(t)=0P{Sn(t+1)=1∣λn(t)}ifn∉A1(t)={P{Sn(t+1)=1∣Sn(t)=1}×P{Sn(t)=1∣hn(t)=1}+P{Sn(t+1)=1∣Sn(t)=0}×P{Sn(t)=0∣hn(t)=1}ifn∈A1(t),hn(t)=1P{Sn(t+1)=1∣Sn(t)=1}×P{Sn(t)=1∣hn(t)=0}+P{Sn(t+1)=1∣Sn(t)=0}×P{Sn(t)=0∣hn(t)=0}ifn∈A1(t),hn(t)=0P{Sn(t+1)=1∣Sn(t)=1}×P{Sn(t)=1∣λn(t)}+P{Sn(t+1)=1∣Sn(t)=0}×P{Sn(t)=0∣λn(t)}ifn∉A1(t)={p11(1-pfn(t))+p01pfn(t)ifn∈A1(t),hn(t)=1p11(1-pdn(t))+p01pdn(t)ifn∈A1(t),hn(t)=0p11λn(t)+p01(1-λn(t))ifn∉A1(t).
The proofs of the other cases are similar.The objective of the user is to maximize its total (discounted or average) expected reward; letJαπ(Λ(1)) and Jπ(Λ(1)) [18] denote the rewards, respectively. Here, π denotes the policy of the user, α denotes the discounted factor, Λ(1) is the initial probability distribution of all channels, and EΛ(1)π represents the mathematical expectation which is determined by the initial probability distribution Λ(1) and the policy π. Consequently, Jαπ(Λ(1)) and Jπ(Λ(1)) denote the discounted and average reward with the initial probability distribution Λ(1) and the policy π, respectively.An optimal policy should maximize the reward of the user, and this optimization problem can be formally defined as follows:(4)maxπJαπ(Λ(1))=maxπEΛ(1)π[limT→+∞∑t=1T‍αt-1r(Λ(t),a(t))],maxπJπ(Λ(1))=maxπlimsupT→+∞1TEΛ(1)π[∑t=1T‍r(Λ(t),a(t))],
where r(Λ(t),a(t)) denotes the immediate reward when the user implements the action a(t), and we think that each channel to be accessed brings 1 unit of reward; thus r(Λ(t),a(t))=|A2(t)|. However, there is a selection problem of A2(t). Without loss of generality and for the greedy approach, all the channels whose states are sensed as 1 in A1(t) are selected into A2(t).Then, we can give a recursive expression of the reward function:(5)RT(Λ(T))=maxa(T)E[r(Λ(T),a(T))]Rt(Λ(t))=maxa(t)E[r(Λ(t),a(t))+αRt+1(Λ(t+1))]=maxa(t){∑i∈A1(t)‍λi(t)+α×∑A2(t)⊆A1(t)‍[(∏j∈A2(t)‍λj(t))×(∏k∉A2(t),k∈A1(t)‍(1-λk(t)))×Rt+1(Λ(t+1)∣a(t))(∏j∈A2(t)‍λj(t))]∑i∈A1(t)‍},
where E[r(Λ(t),a(t))] denotes the mathematical expectation of the immediate reward in the time slot t, Rt(Λ(t)) denotes the maximum expected reward that is accrued from time t to T. Specially, R1(Λ(1))=maxπJαπ(Λ(1)) when T→+∞. This proposition is proved in Section 4.3.


## 3. Myopic Policy

The myopic policy is essentially a greedy policy which maximizes the immediate expected reward in each time slot and ignores the future reward; this greedy policy has the minimal time complexity and computational complexity. The expression of the myopic policy can be given by(6)a(t)=argmaxa(t)E[r(Λ(t),a(t))]=argmaxa(t)∑i∈A1(t)‍λi(t).
We can discover that the channels which have the |A1(t)| largest conditional probabilities in Λ(t) are selected into A1(t) by the myopic policy. Consequently, the successive update of the idle conditional probability vector Λ(t) can determine the action of the myopic policy at time t.In particular, if1-pfn(t) is larger than all the idle conditional probabilities and 1-pdn(t) is smaller than all the idle conditional probabilities for any n, the myopic policy requires only the initial condition Λ(1) but not the precise values of {Λ(2),Λ(3),…}. To give an explanation, we first simplify the expression of (3) by defining a function f(x)=p11x+p01(1-x):
(7)λn(t+1)={f(1-pfn(t))ifn∈A1(t),hn(t)=1f(1-pdn(t))ifn∈A1(t),hn(t)=0f(λn(t))ifn∉A1(t).
Due to the monotonicity of f(x), f(x) is a monotonically increasing function when p11≥p01. The ordering of the idle conditional probabilities can be preserved when they are updated for the reason that f(λi(t))≥f(λj(t)) if λi(t)≥λj(t). If a channel is selected into A1(t), its idle conditional probability will become 1-pfn(t) when it is observed as 1, or 1-pdn(t) when the observation is 0. That is, the channel has the largest idle conditional probability if it is observed as 1, or the smallest idle conditional probability if it is observed as 0. The myopic policy can create a list which preserves the ordering of the idle conditional probabilities according to the initial condition Λ(1). After each update in each time slot, the channels which are not observed do not change the list, the channels which are observed as 1 are selected into A2(t) and moved to the top of the list, and the channels which are observed as 0 are moved to the bottom of the list. Consequently, the myopic policy does not require the precise values of the updated idle conditional probabilities in this case.We have an opposite situation whenp11<p01, f(x) is a monotonically decreasing function. The ordering of the idle conditional probabilities should be reversed when they are updated for the reason that f(λi(t))≥f(λj(t)) if λi(t)≤λj(t). The myopic policy also creates a list which preserve the ordering of the idle conditional probabilities. After each update in each time slot, the channels which are not observed reverse their locations, the channels which are observed as 1 are moved to the bottom of the list, and the channels which are observed as 0 are moved to the top of the list. Consequently, the myopic policy also does not require the precise values of the updated idle conditional probabilities in this case.


## 4. Optimality of Myopic Policy

In order to show the optimality of the myopic policy, we first define two functions which can denote the expected rewards obtained by the myopic policy and the arbitrary policy:(8)Ut(Λ)=Ut({λ1,…,λN})=(λN-|A1U|+1+⋯+λN)+α×∑A2U⊆A1U‍[(∏j∈A2U‍λj)(∏k∉A2U,k∈A1U‍(1-λk))×Ut+1(⋃‍{f(1-pfj)∣j∈A2U}{f(1-pdk)∣k∉A2U,k∈A1U}⋃‍{f(λi)∣i∉A1U}⋃‍{f(1-pfj)∣j∈A2U})(∏j∈A2U‍λj)(∏k∉A2U,k∈A1U‍(1-λk))]UT({λ1,…,λN})=λN-|A1U|+1+⋯+λN,
where Ut denotes the expected total reward obtained by the myopic policy from time t on. Λ denotes the sequence of the idle conditional probabilities of all channels; it is reordered to {λ1,…,λN} by Ut and λ1≤⋯≤λN. A1U denotes the set {N-|A1U|+1,…,N} of channels which have been chosen to sense by the myopic policy. A2U denotes the set of channels which have been chosen to access:
(9)Wt(Λ)=Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})=(λi1+⋯+λi|A1W|)+α×∑A2W⊆A1W‍[(∏j∈A2W‍λj)(∏k∉A2W,k∈A1W‍(1-λk))×Ut+1(⋃‍{f(1-pdk)∣k∉A2W,k∈A1W}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W})(∏j∈A2W‍λj)(∏k∉A2W,k∈A1W‍(1-λk))]WT({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})=λi1+⋯+λi|A1W|,
where  denotes the expected total reward obtained by the arbitrary policy at time t and the myopic policy from time t+1 on. Λ denotes the sequence of the idle conditional probabilities of all channels. The channels corresponding to its last entries {λi1,…,λi|A1W|} are selected into A1W. The arbitrary set A1W is corresponding to the arbitrary policy. A1W denotes the set {i1,…,i|A1W|} of channels which have been chosen to sense by the arbitrary policy. A2W denotes the set of channels which have been chosen to access.In particular,(10)Wt({λ1,…,λN})=Ut(Λ).Theorem 2.
WhenT is finite, the optimality of the myopic policy at times 1,2,…,T is equivalent to
(11)Wt(Λ)≤Ut(Λ)
for any A1W and t=1,2,…,T.Proof.
We first prove the sufficiency inductively. The myopic policy is optimal at timeT for the reasons that UT is larger than any WT and WT obtained by the arbitrary policy.
Then, we suppose that the myopic policy is optimal at timet+1. We have that Wt is larger than the reward obtained by the same policy at time t and the arbitrary policy from time t+1 due to the induction hypothesis, and the immediate reward obtained by the myopic policy is the largest. Consequently, Ut is larger than any Wt. Ut is thus larger than the reward obtained by the arbitrary policy. The myopic policy is optimal at time t. The proof of the sufficiency is complete.
The proof of the necessity can also be obtained due to the optimality of the myopic policy.Lemma 3.
U
t and Wt are N variable functions which are polynomial of order 1 for t=1,…,T.Proof.
We prove this by induction over timet. UT and WT are polynomial of order 1 due to their definitions.
We suppose thatUt+1 and Wt+1 are polynomial of order 1. We have that Ut+1({f(1-pdk)∣k∉A2U,k∈A1U}⋃‍{f(λi)∣i∉A1U}⋃‍{f(1-pfj)∣j∈A2U}) and Ut+1({f(1-pdk)∣k∉A2W,k∈A1W}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W}) are polynomial of order 1 for the reason that f is a linear function. Consequently, Ut and Wt are polynomial of order 1. The proof is complete.


### 4.1. The Case ofp11≥p01

Assumption 4.
The transition probabilitiesp11 and p01 are such that p11≥p01.
The functionf is monotonically increasing under Assumption 4. For any x,y∈[0,1] and x≤y, we have f(0)≤f(x)≤f(y)≤f(1).Assumption 5.
We assume that for any discounted factorα∈[0,1] and all the idle conditional probabilities, the detection probability pd and the false alarm probability pf are such that
(12)1+α∑A2⊆A1‍[(∏j∈A2‍λj)×(∏k∉A2,k∈A1‍(1-λk))(pd-pf-1)]≥0.
For
(13)∑A2⊆A1‍[(∏j∈A2‍λj)(∏k∉A2,k∈A1‍(1-λk))]=1,
we can rewrite Assumption 5 as follows
(14)1+α(pd-pf-1)≥0⟹pd-pf≥1-1α.
Assumption5 is used to limit the reliability of the sensing information; we cannot make the optimal decision if the information is very unreliable. pd equals 1 and pf equals 0 in the absence of sensing error; Assumption 5 is always true.Theorem 6.
The myopic policy is optimal under Assumptions4 and 5 when T is finite.
To prove this theorem, one should show thatUt is larger than any Wt for t=1,…,T according to Theorem 2. One proves this inductively. Given that Ui is larger than any Wi for i=t+1,…,T, one wants to show that Ut is larger than any Wt. This relies on a number of lemmas introduced below.Lemma 7.
For allλx≥λy, x,y∈A1W, one has
(15)Wt({λj1,…,λjN-|A1W|,…,λx,λy,…})=Wt({λj1,…,λjN-|A1W|,…,λy,λx,…}).Lemma 8.
For anyλj1≤⋯≤λx≤λy≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, one has
(16)Wt({…,λx,λy,…,λi1,…,λi|A1W|})=Wt({…,λy,λx,…,λi1,…,λi|A1W|}).Proof.
Lemmas7 and 8 are true according to the definition of Wt.Lemma 9.
One has(17)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].Proof.
We use LHS and RHS to denote the left-hand side and the right-hand side of the equation, respectively. We can prove thatWt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|}) is the first-order function of λjN-|A1W| and λi1 according to Lemma 3. Consequently, we can suppose that
(18)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})=aλjN-|A1W|+bλi1+cλjN-|A1W|λi1+d,
where a, b, c, and d are irrelevant with λjN-|A1W| and λi1. Consequently, we have that
(19)LHS=(aλjN-|A1W|+bλi1+cλjN-|A1W|λi1+d)-(aλi1+bλjN-|A1W|+cλjN-|A1W|λi1+d)=(a-b)(λjN-|A1W|-λi1),(20)RHS=(λi1-λjN-|A1W|)×[(a0+b1+c0×1+d)-(a1+b0+c0×1+d)]=(a-b)(λjN-|A1W|-λi1)=LHS.
The proof is complete.Lemma 10.
Consider Assumption4. One has
(21)Ut({λz1,λ1,…,λN-1})-Ut({λ1,…,λi,λz2,λi+1,…,λN-1})≥λz1-λz2
for any λz1≤λ1≤⋯≤λz2≤⋯≤λN-1.Proof.
We use LHS to denote the left-hand side of the inequality. We usefn(x) to denote f(f(⋯f(x)⋯)):
(22)fn(x)=(p11-p01)nx+(p11-p01)n-1p01+⋯+p01fn(x)-fn(y)=(p11-p01)n(x-y).
Consequently, we have
(23)fn(x)-fn(y)≥⋯≥f(x)-f(y)≥x-y
for any x≤y. Therefore, we have
(24)LHS≥(λi-λz2)+(λi-1-λi)+⋯+(λz1-λ1)≥λz1-λz2.Lemma 11.
Consider Assumptions4 and 5. For any λj1≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, if λjN-|A1W|≥λi1, one has
(25)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|}).Proof.
The inequality is true at timeT. We have the following equation for any time t<T according to Lemma 9:
(26)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].
Because λjN-|A1W|≥λi1, λi1-λjN-|A1W|≤0, we use LHS to denote Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|}). According to the definition of Wt, we have
(27)LHS=1+α×∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×({f(1-pdjN-|A1W|)}Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∉A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(1-pfi1)})-Ut+1({f(1-pdjN-|A1W|)}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(1)}{f(1-pdjN-|A1W|)}){f(1-pdjN-|A1W|)})(∏j∈A2W-{i1}‍λj)].
According to Lemma10, we have
(28)LHS≥1+α∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×((0-(1-pdjN-|A1W|))+(1-pfi1-1))(∏j∈A2W-{i1}‍λj)].
Consequently, LHS≥0 under Assumption 5:
(29)(λi1-λjN-|A1W|)LHS≤0.
The proof is complete.Now we can give the proof of Theorem6 with Lemmas 7, 8, and 11.Proof.
W
T
≤
U
T due to their definitions. For any time t<T, λj1≤⋯≤λjN-|A1W|, λi1≤⋯≤λi|A1W|, and λ1≤⋯≤λN, we have
(30)Wt({λ1,…,λi-1,λi+1,…,λN,λi})≤Wt({λ1,…,λi-1,λi+1,…,λN-1,λi,λN})≤Wt({λ1,…,λi-1,λi,λi+1,…,λN})=Ut({λ1,…λN}),Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λi|A1W|-1,λi|A1W|,λi|A1W|+1,……,λi1-1,λi1,λi1+1,…,λi|A1W|-1,λi|A1W|,λi|A1W|+1,…})=Wt({λ1,…λN})=Ut({λ1,…λN}).
The inequalities are true due to Lemmas 7, 8, and 11. Consequently, Wt≤Ut at time t=1,…,T. The myopic policy is optimal according to Theorem 2. The proof is complete.


### 4.2. The Case ofp11≤p01

Assumption 12.
The transition probabilitiesp11 and p01 are such that p11≤p01.
The functionf is monotonically decreasing under Assumption 12. For any x,y∈[0,1] and x≤y, we have f(1)≤f(y)≤f(x)≤f(0).Assumption 13.
We assume that, for all the idle conditional probabilities, the discounted factorα is such that
(31)1-α∑A2⊆A1‍[(∏k∉A2,k∈A1‍(1-λk))|A1|(1-α)(∏j∈A2‍λj)×(∏k∉A2,k∈A1‍(1-λk))|A1|(1-α)]≥0.
Like Assumption 5, we can rewrite Assumption 13 as follows:
(32)1-α|A1|(1-α)≥0⟹α≤1(1+|A1|).Theorem 14.
The myopic policy is optimal under Assumptions12 and 13 when T is finite.Lemma 15.
Consider Assumptions12 and 13. For any λj1≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, if λjN-|A1W|≥λi1, one has
(33)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|}).Proof.
The inequality is true at timeT. We have the following equation for any time t<T according to Lemma 9:
(34)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].
Because λjN-|A1W|≥λi1, λi1-λjN-|A1W|≤0, we use LHS to denote Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|}). According to the definition of Wt, we have
(35)LHS=1+α×∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×(⋃‍{f(1-pdjN-|A1W|)})Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{A1W-{i1}f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(0)}{f(1-pfi1)})-Ut+1(⋃‍⋃‍{f(1-pdjN-|A1W|)}{f(1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}(f(1-pfj)j∈A2W)}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(1-pdjN-|A1W|)}))(∏j∈A2W-{i1}‍λj)].
We have the following inequalities due to the definition ofUt:
(36)Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(0)}{f(1-pfi1)})≥0(37)Ut+1({f(1-pdjN-|A1W|)}{f(1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(1-pdjN-|A1W|)})≤|A1W|(1+α1+⋯+αT-t)≤|A1W|(1+α1+⋯+α+∞)=|A1W|(1-α).
Then, we have(38)LHS≥1+α∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×(0-|A1W|(1-α))].
Consequently,LHS≥0 under Assumption 13. 									(39)(λi1-λjN-|A1W|)LHS≤0.
The proof is complete.Now we can give the proof of Theorem14 with Lemmas 7, 8, and 15. The proof of Theorem 14 is similar with the proof of Theorem 6.


### 4.3. The Case ofT→+∞

We discuss the optimality of the myopic policy in above subsections whenT is finite; now we consider the extensions of results when T is infinite.Theorem 16.
If the myopic policy is optimal whenT is finite, it is optimal when T is infinite.Proof.
(40)
max
π
J
α
π
(
Λ
(
1
)
)
=
max
π
E
Λ
(
1
)
π
[
lim
T
→
+
∞
∑
t
=
1
T
‍
α
t
-
1
r
(
Λ
(
t
)
,
a
(
t
)
)
]
=
max
π
lim
T
→
+
∞
E
Λ
(
1
)
π
[
∑
t
=
1
T
‍
α
t
-
1
r
(
Λ
(
t
)
,
a
(
t
)
)
]
=
max
π
lim
T
→
+
∞
J
T
π
(
Λ
(
1
)
)
,
where JTπ(Λ(1)) denotes EΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))] only in this proof.
For(41)∑t=1T‍αt-1r(Λ(t),a(t))≤|A1|(1+α+⋯+αT-1)≤|A1|(1+α+⋯+α+∞)=|A1|(1-α),
we can use the bounded convergence theorem to interchange limT→+∞ and EΛ(1)π. Then, we consider the relationship of limT→+∞ and maxπ, and two sequences are given as follows:Sequence 1:{J1π(Λ(1)),J2π(Λ(1)),…}Sequence 2:{maxπJ1π(Λ(1)),maxπJ2π(Λ(1)),…}.
We have the following inequalities:(42)EΛ(1)π[∑t=1T+1‍αt-1r(Λ(t),a(t))]≥EΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))]⟹JT+1π(Λ(1))≥JTπ(Λ(1))maxπJT+1π(Λ(1))≥JT+1π′(Λ(1))≥JTπ′(Λ(1))⟹maxπJT+1π(Λ(1))≥maxπJTπ(Λ(1)),
where π′ denotes argmaxπJTπ(Λ(1)). And for any T, we have
(43)JTπ(Λ(1))≤|A1|(1-α)maxπJTπ(Λ(1))≤|A1|(1-α).
Consequently, Sequences 1 and 2 are monotonically increasing and bounded. We can conclude that Sequences 1 and 2 have finite limits due to the monotone convergence theorem. We thus have
(44)limT→+∞maxπJTπ(Λ(1))-limT→+∞JTπ(Λ(1))=limT→+∞(maxπJTπ(Λ(1))-JTπ(Λ(1)))≥0
for any policy π and T. Therefore, we have
(45)limT→+∞maxπJTπ(Λ(1))≥maxπlimT→+∞JTπ(Λ(1)).
For maxπJTπ(Λ(1))∈{JTπ(Λ(1))∣π}, we have
(46)limT→+∞maxπJTπ(Λ(1))≤maxπlimT→+∞JTπ(Λ(1)).
We can conclude that
(47)limT→+∞maxπJTπ(Λ(1))=maxπlimT→+∞JTπ(Λ(1)).
Consequently, we have
(48)maxπJαπ(Λ(1))=limT→+∞maxπJTπ(Λ(1))=limT→+∞maxπEΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))]=limT→+∞R1(Λ(1)).
The myopic policy is thus optimal when T is infinite if the myopic policy is optimal when T is finite. R1(Λ(1)) has been defined in Section 2.
Then, we consider the uniqueness of the optimal policy. Letπ* be the myopic policy, and a*(t)={A1*(t),A2*(t)} is the action at time t; we have
(49)maxπJαπ(Λ(1))=limT→+∞maxπJTπ(Λ(1))=limT→+∞JTπ*(Λ(1))=limT→+∞EΛ(1)π*[∑t=1T‍αt-1r(Λ(t),a*(t))]=∑i∈A1*(1)‍λi+α×∑A2*(1)⊆A1*(1)‍[(∏j∈A2*(1)‍λj(1))×(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))×limT→+∞EΛ(2)π*×[∑t=2T‍αt-2r(Λ(2),a*(2)∣a*(1))](∏j∈A2*(1)‍λj(1))].
For
(50)limT→+∞EΛ(2)π*[∑t=2T‍αt-2r(Λ(2),a*(2)∣a*(1))]=limT→+∞JT-1π*(Λ(2)∣a*(1))=limT→+∞JTπ*(Λ(2)∣a*(1))=Jαπ*(Λ(2)∣a*(1)),
we have
(51)Jαπ*(Λ(1))=∑i∈A1*(1)‍λi+α×∑A2*(1)⊆A1*(1)‍[(∏j∈A2*(1)‍λj(1))×(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))×Jαπ*(Λ(2)∣a*(1))(∏j∈A2*(1)‍λj(1))(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))].
The above equation is the dynamic programming equation for the infinite horizon discounted reward problem. The uniqueness of the optimal policy can be proved due to the uniqueness of the dynamic programming solution.
The proof is complete.Theorem 17.
If the myopic policy is optimal for the discounted reward, it is optimal for the average reward.Proof.
We first consider the Blackwell optimality [19, pp. 336–341] of the optimal policy for the discounted reward. The sequence of {α1,α2,…} is given, and α1≤α2≤⋯≤1, limk→+∞αk=1. For
(52)(1-αk)Jαkπ(Λ(1))≤(1-αk)|A1|(1+αk+αk2+⋯)=|A1||Jαkπ(Λ)-Jαkπ(Λ(1))|≤|0-|A1|(1+αk+αk2+⋯)|=|A1|(1-αk),
we can give the definition of J(Λ(1)) and h(Λ) due to the boundedness of (1-αk)Jαkπ(Λ(1)) and |Jαkπ(Λ)-Jαkπ(Λ(1))|:
(53)J(Λ(1))=maxπlimk→+∞(1-αk)Jαkπ(Λ(1))h(Λ)=maxπlimk→+∞(Jαkπ(Λ)-Jαkπ(Λ(1)))
for any Λ.Then, we can give the average cost optimality equation (ACOE) [20]. Here, we calculate the reward:
(54)J(Λ(1))+hπ(Λ(1))=maxπlimk→+∞[(1-αk)Jαkπ(Λ(1))+(Jαkπ(Λ(1))-Jαkπ(Λ(1)))]=maxπlimk→+∞[(1-αk)Jαkπ(Λ(1))].For(55)Jαkπ(Λ(1))=∑i∈A1(1)‍λi+α×∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×Jαπ(Λ(2)∣a(1))(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))],Jαkπ(Λ(1))=∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))Jαkπ(Λ(1))],
we have
(56)J(Λ(1))+hπ(Λ(1))=maxπlimk→+∞[Jαkπ(Λ(1))-αkJαkπ(Λ(1))]=maxπlimk→+∞[∑i∈A1(1)‍λi+αk×∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×(Jαkπ(Λ(2)∣a(1))-Jαkπ(Λ(1)))∑i∈A1(1)‍(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))]∑i∈A1(1)‍λi+αk(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))].Consequently, we have(57)J(Λ(1))+hπ(Λ(1))=maxπ[∑i∈A1(1)‍λi+∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×hπ(Λ(2))(∏j∈A2(1)‍λj(1))]].We thus can conclude that the stationary deterministic policy realizing the pointwise maximum on the right-hand side of the ACOE is the average optimal policy due to the boundedness ofhπ(Λ(1)), and J(Λ(1)) is the maximum average expected reward [20, Theorems 4.1–4.3].For(58)J(Λ(1))=maxπlimk→+∞(1-αk)Jαkπ(Λ(1)),
the optimal policy for the discounted reward can maximize J(Λ(1)). Consequently, the myopic policy is optimal for the average reward when it is optimal for the discounted reward. The proof is complete.


## 4.1. The Case ofp11≥p01

Assumption 4.
The transition probabilitiesp11 and p01 are such that p11≥p01.
The functionf is monotonically increasing under Assumption 4. For any x,y∈[0,1] and x≤y, we have f(0)≤f(x)≤f(y)≤f(1).Assumption 5.
We assume that for any discounted factorα∈[0,1] and all the idle conditional probabilities, the detection probability pd and the false alarm probability pf are such that
(12)1+α∑A2⊆A1‍[(∏j∈A2‍λj)×(∏k∉A2,k∈A1‍(1-λk))(pd-pf-1)]≥0.
For
(13)∑A2⊆A1‍[(∏j∈A2‍λj)(∏k∉A2,k∈A1‍(1-λk))]=1,
we can rewrite Assumption 5 as follows
(14)1+α(pd-pf-1)≥0⟹pd-pf≥1-1α.
Assumption5 is used to limit the reliability of the sensing information; we cannot make the optimal decision if the information is very unreliable. pd equals 1 and pf equals 0 in the absence of sensing error; Assumption 5 is always true.Theorem 6.
The myopic policy is optimal under Assumptions4 and 5 when T is finite.
To prove this theorem, one should show thatUt is larger than any Wt for t=1,…,T according to Theorem 2. One proves this inductively. Given that Ui is larger than any Wi for i=t+1,…,T, one wants to show that Ut is larger than any Wt. This relies on a number of lemmas introduced below.Lemma 7.
For allλx≥λy, x,y∈A1W, one has
(15)Wt({λj1,…,λjN-|A1W|,…,λx,λy,…})=Wt({λj1,…,λjN-|A1W|,…,λy,λx,…}).Lemma 8.
For anyλj1≤⋯≤λx≤λy≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, one has
(16)Wt({…,λx,λy,…,λi1,…,λi|A1W|})=Wt({…,λy,λx,…,λi1,…,λi|A1W|}).Proof.
Lemmas7 and 8 are true according to the definition of Wt.Lemma 9.
One has(17)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].Proof.
We use LHS and RHS to denote the left-hand side and the right-hand side of the equation, respectively. We can prove thatWt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|}) is the first-order function of λjN-|A1W| and λi1 according to Lemma 3. Consequently, we can suppose that
(18)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})=aλjN-|A1W|+bλi1+cλjN-|A1W|λi1+d,
where a, b, c, and d are irrelevant with λjN-|A1W| and λi1. Consequently, we have that
(19)LHS=(aλjN-|A1W|+bλi1+cλjN-|A1W|λi1+d)-(aλi1+bλjN-|A1W|+cλjN-|A1W|λi1+d)=(a-b)(λjN-|A1W|-λi1),(20)RHS=(λi1-λjN-|A1W|)×[(a0+b1+c0×1+d)-(a1+b0+c0×1+d)]=(a-b)(λjN-|A1W|-λi1)=LHS.
The proof is complete.Lemma 10.
Consider Assumption4. One has
(21)Ut({λz1,λ1,…,λN-1})-Ut({λ1,…,λi,λz2,λi+1,…,λN-1})≥λz1-λz2
for any λz1≤λ1≤⋯≤λz2≤⋯≤λN-1.Proof.
We use LHS to denote the left-hand side of the inequality. We usefn(x) to denote f(f(⋯f(x)⋯)):
(22)fn(x)=(p11-p01)nx+(p11-p01)n-1p01+⋯+p01fn(x)-fn(y)=(p11-p01)n(x-y).
Consequently, we have
(23)fn(x)-fn(y)≥⋯≥f(x)-f(y)≥x-y
for any x≤y. Therefore, we have
(24)LHS≥(λi-λz2)+(λi-1-λi)+⋯+(λz1-λ1)≥λz1-λz2.Lemma 11.
Consider Assumptions4 and 5. For any λj1≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, if λjN-|A1W|≥λi1, one has
(25)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|}).Proof.
The inequality is true at timeT. We have the following equation for any time t<T according to Lemma 9:
(26)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].
Because λjN-|A1W|≥λi1, λi1-λjN-|A1W|≤0, we use LHS to denote Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|}). According to the definition of Wt, we have
(27)LHS=1+α×∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×({f(1-pdjN-|A1W|)}Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∉A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(1-pfi1)})-Ut+1({f(1-pdjN-|A1W|)}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(1)}{f(1-pdjN-|A1W|)}){f(1-pdjN-|A1W|)})(∏j∈A2W-{i1}‍λj)].
According to Lemma10, we have
(28)LHS≥1+α∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×((0-(1-pdjN-|A1W|))+(1-pfi1-1))(∏j∈A2W-{i1}‍λj)].
Consequently, LHS≥0 under Assumption 5:
(29)(λi1-λjN-|A1W|)LHS≤0.
The proof is complete.Now we can give the proof of Theorem6 with Lemmas 7, 8, and 11.Proof.
W
T
≤
U
T due to their definitions. For any time t<T, λj1≤⋯≤λjN-|A1W|, λi1≤⋯≤λi|A1W|, and λ1≤⋯≤λN, we have
(30)Wt({λ1,…,λi-1,λi+1,…,λN,λi})≤Wt({λ1,…,λi-1,λi+1,…,λN-1,λi,λN})≤Wt({λ1,…,λi-1,λi,λi+1,…,λN})=Ut({λ1,…λN}),Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λi|A1W|-1,λi|A1W|,λi|A1W|+1,……,λi1-1,λi1,λi1+1,…,λi|A1W|-1,λi|A1W|,λi|A1W|+1,…})=Wt({λ1,…λN})=Ut({λ1,…λN}).
The inequalities are true due to Lemmas 7, 8, and 11. Consequently, Wt≤Ut at time t=1,…,T. The myopic policy is optimal according to Theorem 2. The proof is complete.


## 4.2. The Case ofp11≤p01

Assumption 12.
The transition probabilitiesp11 and p01 are such that p11≤p01.
The functionf is monotonically decreasing under Assumption 12. For any x,y∈[0,1] and x≤y, we have f(1)≤f(y)≤f(x)≤f(0).Assumption 13.
We assume that, for all the idle conditional probabilities, the discounted factorα is such that
(31)1-α∑A2⊆A1‍[(∏k∉A2,k∈A1‍(1-λk))|A1|(1-α)(∏j∈A2‍λj)×(∏k∉A2,k∈A1‍(1-λk))|A1|(1-α)]≥0.
Like Assumption 5, we can rewrite Assumption 13 as follows:
(32)1-α|A1|(1-α)≥0⟹α≤1(1+|A1|).Theorem 14.
The myopic policy is optimal under Assumptions12 and 13 when T is finite.Lemma 15.
Consider Assumptions12 and 13. For any λj1≤⋯≤λjN-|A1W| and λi1≤⋯≤λi|A1W|, if λjN-|A1W|≥λi1, one has
(33)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})≤Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|}).Proof.
The inequality is true at timeT. We have the following equation for any time t<T according to Lemma 9:
(34)Wt({λj1,…,λjN-|A1W|,λi1,…,λi|A1W|})-Wt({λj1,…,λi1,λjN-|A1W|,…,λi|A1W|})=(λi1-λjN-|A1W|)×[Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|})].
Because λjN-|A1W|≥λi1, λi1-λjN-|A1W|≤0, we use LHS to denote Wt({λj1,…,0,1,…,λi|A1W|})-Wt({λj1,…,1,0,…,λi|A1W|}). According to the definition of Wt, we have
(35)LHS=1+α×∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×(⋃‍{f(1-pdjN-|A1W|)})Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{A1W-{i1}f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(0)}{f(1-pfi1)})-Ut+1(⋃‍⋃‍{f(1-pdjN-|A1W|)}{f(1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}(f(1-pfj)j∈A2W)}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(1-pdjN-|A1W|)}))(∏j∈A2W-{i1}‍λj)].
We have the following inequalities due to the definition ofUt:
(36)Ut+1({f(1-pfi1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(0)}{f(1-pfi1)})≥0(37)Ut+1({f(1-pdjN-|A1W|)}{f(1)}⋃‍{f(1-pfj)∣j∈A2W-{i1}}⋃‍{f(λi)∣i∉A1W}⋃‍{f(1-pdk)∣k∉A2W,k∈A1W-{i1}}⋃‍{f(1-pdjN-|A1W|)})≤|A1W|(1+α1+⋯+αT-t)≤|A1W|(1+α1+⋯+α+∞)=|A1W|(1-α).
Then, we have(38)LHS≥1+α∑A2W⊆A1W‍[(∏j∈A2W-{i1}‍λj)×(∏k∉A2W,k∈A1W-{i1}‍(1-λk))×(0-|A1W|(1-α))].
Consequently,LHS≥0 under Assumption 13. 									(39)(λi1-λjN-|A1W|)LHS≤0.
The proof is complete.Now we can give the proof of Theorem14 with Lemmas 7, 8, and 15. The proof of Theorem 14 is similar with the proof of Theorem 6.


## 4.3. The Case ofT→+∞

We discuss the optimality of the myopic policy in above subsections whenT is finite; now we consider the extensions of results when T is infinite.Theorem 16.
If the myopic policy is optimal whenT is finite, it is optimal when T is infinite.Proof.
(40)
max
π
J
α
π
(
Λ
(
1
)
)
=
max
π
E
Λ
(
1
)
π
[
lim
T
→
+
∞
∑
t
=
1
T
‍
α
t
-
1
r
(
Λ
(
t
)
,
a
(
t
)
)
]
=
max
π
lim
T
→
+
∞
E
Λ
(
1
)
π
[
∑
t
=
1
T
‍
α
t
-
1
r
(
Λ
(
t
)
,
a
(
t
)
)
]
=
max
π
lim
T
→
+
∞
J
T
π
(
Λ
(
1
)
)
,
where JTπ(Λ(1)) denotes EΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))] only in this proof.
For(41)∑t=1T‍αt-1r(Λ(t),a(t))≤|A1|(1+α+⋯+αT-1)≤|A1|(1+α+⋯+α+∞)=|A1|(1-α),
we can use the bounded convergence theorem to interchange limT→+∞ and EΛ(1)π. Then, we consider the relationship of limT→+∞ and maxπ, and two sequences are given as follows:Sequence 1:{J1π(Λ(1)),J2π(Λ(1)),…}Sequence 2:{maxπJ1π(Λ(1)),maxπJ2π(Λ(1)),…}.
We have the following inequalities:(42)EΛ(1)π[∑t=1T+1‍αt-1r(Λ(t),a(t))]≥EΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))]⟹JT+1π(Λ(1))≥JTπ(Λ(1))maxπJT+1π(Λ(1))≥JT+1π′(Λ(1))≥JTπ′(Λ(1))⟹maxπJT+1π(Λ(1))≥maxπJTπ(Λ(1)),
where π′ denotes argmaxπJTπ(Λ(1)). And for any T, we have
(43)JTπ(Λ(1))≤|A1|(1-α)maxπJTπ(Λ(1))≤|A1|(1-α).
Consequently, Sequences 1 and 2 are monotonically increasing and bounded. We can conclude that Sequences 1 and 2 have finite limits due to the monotone convergence theorem. We thus have
(44)limT→+∞maxπJTπ(Λ(1))-limT→+∞JTπ(Λ(1))=limT→+∞(maxπJTπ(Λ(1))-JTπ(Λ(1)))≥0
for any policy π and T. Therefore, we have
(45)limT→+∞maxπJTπ(Λ(1))≥maxπlimT→+∞JTπ(Λ(1)).
For maxπJTπ(Λ(1))∈{JTπ(Λ(1))∣π}, we have
(46)limT→+∞maxπJTπ(Λ(1))≤maxπlimT→+∞JTπ(Λ(1)).
We can conclude that
(47)limT→+∞maxπJTπ(Λ(1))=maxπlimT→+∞JTπ(Λ(1)).
Consequently, we have
(48)maxπJαπ(Λ(1))=limT→+∞maxπJTπ(Λ(1))=limT→+∞maxπEΛ(1)π[∑t=1T‍αt-1r(Λ(t),a(t))]=limT→+∞R1(Λ(1)).
The myopic policy is thus optimal when T is infinite if the myopic policy is optimal when T is finite. R1(Λ(1)) has been defined in Section 2.
Then, we consider the uniqueness of the optimal policy. Letπ* be the myopic policy, and a*(t)={A1*(t),A2*(t)} is the action at time t; we have
(49)maxπJαπ(Λ(1))=limT→+∞maxπJTπ(Λ(1))=limT→+∞JTπ*(Λ(1))=limT→+∞EΛ(1)π*[∑t=1T‍αt-1r(Λ(t),a*(t))]=∑i∈A1*(1)‍λi+α×∑A2*(1)⊆A1*(1)‍[(∏j∈A2*(1)‍λj(1))×(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))×limT→+∞EΛ(2)π*×[∑t=2T‍αt-2r(Λ(2),a*(2)∣a*(1))](∏j∈A2*(1)‍λj(1))].
For
(50)limT→+∞EΛ(2)π*[∑t=2T‍αt-2r(Λ(2),a*(2)∣a*(1))]=limT→+∞JT-1π*(Λ(2)∣a*(1))=limT→+∞JTπ*(Λ(2)∣a*(1))=Jαπ*(Λ(2)∣a*(1)),
we have
(51)Jαπ*(Λ(1))=∑i∈A1*(1)‍λi+α×∑A2*(1)⊆A1*(1)‍[(∏j∈A2*(1)‍λj(1))×(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))×Jαπ*(Λ(2)∣a*(1))(∏j∈A2*(1)‍λj(1))(∏k∉A2*(1),k∈A1*(1)‍(1-λk(1)))].
The above equation is the dynamic programming equation for the infinite horizon discounted reward problem. The uniqueness of the optimal policy can be proved due to the uniqueness of the dynamic programming solution.
The proof is complete.Theorem 17.
If the myopic policy is optimal for the discounted reward, it is optimal for the average reward.Proof.
We first consider the Blackwell optimality [19, pp. 336–341] of the optimal policy for the discounted reward. The sequence of {α1,α2,…} is given, and α1≤α2≤⋯≤1, limk→+∞αk=1. For
(52)(1-αk)Jαkπ(Λ(1))≤(1-αk)|A1|(1+αk+αk2+⋯)=|A1||Jαkπ(Λ)-Jαkπ(Λ(1))|≤|0-|A1|(1+αk+αk2+⋯)|=|A1|(1-αk),
we can give the definition of J(Λ(1)) and h(Λ) due to the boundedness of (1-αk)Jαkπ(Λ(1)) and |Jαkπ(Λ)-Jαkπ(Λ(1))|:
(53)J(Λ(1))=maxπlimk→+∞(1-αk)Jαkπ(Λ(1))h(Λ)=maxπlimk→+∞(Jαkπ(Λ)-Jαkπ(Λ(1)))
for any Λ.Then, we can give the average cost optimality equation (ACOE) [20]. Here, we calculate the reward:
(54)J(Λ(1))+hπ(Λ(1))=maxπlimk→+∞[(1-αk)Jαkπ(Λ(1))+(Jαkπ(Λ(1))-Jαkπ(Λ(1)))]=maxπlimk→+∞[(1-αk)Jαkπ(Λ(1))].For(55)Jαkπ(Λ(1))=∑i∈A1(1)‍λi+α×∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×Jαπ(Λ(2)∣a(1))(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))],Jαkπ(Λ(1))=∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))Jαkπ(Λ(1))],
we have
(56)J(Λ(1))+hπ(Λ(1))=maxπlimk→+∞[Jαkπ(Λ(1))-αkJαkπ(Λ(1))]=maxπlimk→+∞[∑i∈A1(1)‍λi+αk×∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×(Jαkπ(Λ(2)∣a(1))-Jαkπ(Λ(1)))∑i∈A1(1)‍(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))]∑i∈A1(1)‍λi+αk(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))].Consequently, we have(57)J(Λ(1))+hπ(Λ(1))=maxπ[∑i∈A1(1)‍λi+∑A2(1)⊆A1(1)‍[(∏j∈A2(1)‍λj(1))×(∏k∉A2(1),k∈A1(1)‍(1-λk(1)))×hπ(Λ(2))(∏j∈A2(1)‍λj(1))]].We thus can conclude that the stationary deterministic policy realizing the pointwise maximum on the right-hand side of the ACOE is the average optimal policy due to the boundedness ofhπ(Λ(1)), and J(Λ(1)) is the maximum average expected reward [20, Theorems 4.1–4.3].For(58)J(Λ(1))=maxπlimk→+∞(1-αk)Jαkπ(Λ(1)),
the optimal policy for the discounted reward can maximize J(Λ(1)). Consequently, the myopic policy is optimal for the average reward when it is optimal for the discounted reward. The proof is complete.


## 5. Numerical Results

We consider twenty independent channels with the same bandwidthB=1 and transition probabilities {p11,p01}. The sensing capacity of the user who transmits the data on these channels is limited to C; that is, the user can sense C channels in a sensing procedure. The transition probabilities are set as follows: p11=0.8 and p01=0.5 when p11≥p01, p11=0.3 and p01=0.5 when p11≤p01. The detection probability pd equals 0.9, and the false alarm probability pf equals 0.05. We present the numerical results to evaluate the performance of the optimal policy (OP) which is the dynamic programming solution and the myopic policy (MP).We first use the throughput of the policies to evaluate the performance. The above subfigure of Figure2 shows the performance comparison of OP and MP when p11≥p01. The myopic policy is the optimal policy in this case for the reason that Assumptions 4 and 5 are met. We observe that the performance of OP is similar with MP’s. The following subfigure shows the performance comparison of OP and MP when p11≤p01. We observe that there is a large difference between OP and MP with the growth of the sensing capacity C. The reason is that Assumption 13 is not met. For example, the curves of MP and OP at α=0.1 separate when C equals 11 for the reason that α≥1/(1+C).Figure 2
Performance comparison of OP and MP whenp11≥p01 and p11≤p01.Then, we use the collision probabilities which are the probabilities which the user accesses occupied channels to evaluate the performance. The collision probability is the key metric which measures the interference caused by the user. Figure3 gives us similar results of Figure 2. The above subfigure shows the collision probabilities of OP and MP when p11≥p01. We observe that they have the same collision probabilities for the reason that the myopic policy is the optimal policy. The following subfigure shows the collision probabilities of OP and MP when p11≤p01. The myopic policies at α=0.1,0.3,0.6 have the same collision probabilities for the reason that they are the same policy. On the other hand, the optimal policies are different at different α.Figure 3
The comparison of collision probabilities of OP and MP whenp11≥p01 and p11≤p01.At last, we also give the comparison of the time complexity of OP and MP in Table1. Since p11, p01, and α do not make impact on the time complexity of the policies, we mainly consider the variation of the sensing capacity. The first column of the table is the sensing capacity. The second and third columns show the time overhead of OP and MP, respectively, and the unit is second. The time overhead of MP is nearly 0 as MP does not need to calculate any parameter. In particular, the time overhead of OP is also almost 0 when the sensing capacity is 20 for the reason that OP can directly choose the channels which are observed as 1(idle). From Table 1, we can find that the time complexity of MP is much smaller than OP’s.Table 1
Comparison of time complexity of OP and MP.
C
Optimal policy
Myopic policy
1
1217.44
0.12
2
1012.68
0.03
4
697.82
0.07
6
473.34
0.06
8
334.71
0.01
10
198.34
0.05
12
127.3
0.11
14
79.57
0.06
16
39.12
0.07
18
22.37
0.02
20
0.07
0.08


## 6. Conclusion

We show the optimality of the simple and robust myopic policy for the infinite horizon discounted and average reward criteria in the case where the stochastic evolution of channels can be modeled as the independent and identically distributed two-state Markov chains. The myopic policy is optimal when the state transitions are positively correlated and the detection probability and the false alarm probability are limited. The myopic policy is also optimal when the state transitions are negatively correlated and the discounted factor is limited.



---

*Source: 791789-2013-09-26.xml*