# Explicit Solution of the Average-Cost Optimality Equation for a Pest-Control Problem

Authors: Epaminondas G. Kyriakidis
Journal: Advances in Decision Sciences
 (2011)

---

## Abstract

We introduce a Markov decision process in continuous time for the optimal control of a simple symmetrical immigration-emigration process by the introduction of total catastrophes. It is proved that a particular control-limit policy is average cost optimal within the class of all stationary policies by verifying that the relative values of this policy are the solution of the corresponding optimality equation.


---

## Body

## 1. Introduction

The term “Markov decision process” was introduced by Bellman [1] for the description of a stochastic process controlled by a sequence of actions. During the last fifty years, the Markov decision process has been the subject of remarkable research activity. It is called discrete-time Markov decision process or semi-Markov decision process if the times between consecutive decision epochs are equal or random, respectively. The Markov decision process in continuous time is a special semi-Markov decision process if the times between consecutive decision epochs are exponentially distributed. Collections of results with some emphasis to the theoretical aspects of  Markov decision processes are given in the books of Derman [2], Ross [3], Whittle [4, 5], Puterman [6], and Sennott [7]. The computational aspects of Markov decision processes can be found in detail in the books of Puterman [6] and Tijms [8].The most widely used optimization criteria in a Markov decision process are the minimization of the finite-horizon expected cost, the minimization of the infinite-horizon total expected discounted cost, and the minimization of the long-run expected average cost per unit time. An intuitively appealing class of policies is the class of stationary policies. A policy is said to be stationary if, at each decision epoch, it chooses one action which depends only on the current state of the process. Although an optimal discounted-cost stationary policy exists if some mild conditions hold (see, e.g., [3] Section 6.2), there are cases in which an optimal average-cost policy does not exist (see [3] pages 142-143). When the state space is denumerable, there are two approaches for obtaining sufficient conditions that guarantee the existence of optimal average-cost stationary policy. The first approach gives sufficient conditions in terms of the solution of the optimality equation for the discounted-cost problem (see, e.g., [3] Theorem 6.18). The second approach relates the solution of the optimality equation for the average-cost problem (i.e., the relative values of the average-cost optimal policy) directly to the solution of the optimality equation of the discounted-cost problem (see, e.g., Miller [9]). Bather [10] gave sufficient conditions which guarantee that a particular stationary policy is average-cost optimal using unbounded solutions of the optimality equation. Note that Hordijk and Van der Duyn Schouten [11] studied the Markov decision drift process, which unifies the above three types of Markov decision processes, and followed the second approach in dealing with the problem of the existence of a stationary average-cost optimal policy.In many problems, it is intuitively reasonable that the optimal policy initiates the controlling action if and only if the state of the process (e.g., number of customers in a queue, degree of deterioration of a machine, content of a buffer, size of a biological population) exceeds a critical number. Such a policy is known as a control-limit policy, and the critical number is called the control-limit number. The proof of the optimality of a control-limit policy is often a difficult problem and depends on the particular model. A standard method that sometimes leads to the proof of the optimality of a control-limit policy is the method of successive approximations. This method first establishes, by induction on the length of the horizon, the optimality of a control-limit policy for the corresponding finite-horizon discounted cost problem. Then, this structural property is transferred to the infinite-horizon discounted cost problem, and, finally to the average-cost problem. We refer to a machine replacement model (see Derman [2] pages 121–125), where this method has been used.In the present paper, we present a Markov decision process in continuous time for the optimal control of a symmetrical immigration-emigration process through total catastrophes that annihilate the population size. It is assumed that the population is harmful and causes a cost that is proportional to its size. The cost of the operation of the mechanism that introduces the catastrophes is proportional to the rate at which catastrophes occur. In this model, it is possible, following the method of successive approximations, to prove that the discounted-cost optimal policy is of control-limit type, and this structural property is transferred to the average-cost problem. However, in the present paper, we will prove that a particular control-limit policy is average-cost optimal directly without using the discounted-cost problem. This is possible if we apply Bather’s [10] general results. Specifically, we will show that (i) a particular control-limit policy satisfies the average-cost optimality equation and (ii) some mild conditions on the cost rates and transition rates are satisfied. Bather’s theory has been applied to two other models (see Kyriakidis and Abakuks [12] and Kyriakidis [13]) in which a simple immigration-birth process and a simple immigration process are controlled through total catastrophes and through the introduction of a predator, respectively. The main contribution of the present work is the presentation of a third application of Bather’s theory. The solution of the optimality equation in this application contains linear and geometric terms with respect to the population size in contrast with the solutions of the optimality equations in the models studied in [12, 13] which contain linear and quadratic terms.The rest of the paper is organized as follows. The model is presented is Section2. In Section 3, the average-cost optimal policy within the restricted class of control-limit policies is found, and in Section 4, it is verified that this policy is average-cost optimal within the wider class of all stationary policies. Numerical results that compare the optimal policy of the present problem with the optimal policy of the problem in which a simple immigration process is controlled through total catastrophes are presented in Section 5. In Section 6, we consider the case in which the immigration rate is not equal to the emigration rate, and we give a condition that guarantees the optimality of the policy which always introduces catastrophes. In Section 7, we summarize the results of the paper.


## 2. The Model

Consider a population of individuals which grow in a habitat with infinite capacity according to a simple symmetrical immigration-emigration process. Letν denote the immigration and the emigration rate. We suppose that the individuals are harmful. For example, the individuals may be insects which destroy a crop or spread a disease. We refer to such individuals as pests. Assume that the rate at which damage is caused by the pests is proportional to their population size. Defining the unit of cost to be the cost per unit time of the damage caused by each pest, it follows that the cost of the damage caused by the pests is i per unit time, where i is the current population size.The pest population may be controlled by some action which introduces total catastrophes. When such a catastrophe occurs, the population size of the pests is instantaneously reduced to zero. Letu be the control variable, where u is the rate at which catastrophes occur. Assume that the unit of time has been chosen in such a way that the available values of u are restricted to the closed interval [0, 1] so that if the maximal level of control is being applied,then catastrophes occur at an average rate of one per unit time and the length of time until the occurrence of a catastrophe is exponentially distributed with unit mean. The controlling action gives rise to costs due to labour, materials, risk, and so forth. Let the cost of taking controlling action u be ku per unit time, where k>0. A stationary policy is defined by a sequence {ui}, where ui∈[0,1] is the level of control applied whenever the process is in state i, i≥1.If the stationary policyui, i≥0, is employed, our assumptions imply that we have a continuous time Markov chain model for the population growth of the pests with the state space S={0,1,2,…} and the following transition rates:(2.1)TransitionRatei→i+1,ν(i≥0),i→i-1,ν(i≥2),i→0,ui(i≥2),1→0,ν+u1.The expected long-run average cost per unit time of a policyui, i≥0  is defined as the limit as t→∞ of the expected cost incurred in the time interval [0,t] divided by t, given that the policy ui, i≥0  is employed. We aim to find a stationary policy which minimises the expected long-run average cost per unit time among all stationary policies. An intuitively appealing class of policies is P≡{Px:x=1,2,…}, where Px is the stationary policy according to which ui=0, 1≤i≤x-1, and ui=1, i≥x. Thus, Px is a policy of “bang-bang” type, where controlling action is not taken as long as the population size is less than x, but controlling action is taken at the maximal possible level whenever the population size is greater than or equal to x.We refer to Px as a control-limit policy. In Section 3, the optimal policy Px* within P is found, and in Section 4, the optimality of Px* within the wider class of all stationary policies is established using Bather’s [10] general results.Bather’s theory has also been applied to two other pest-control models (see [12, 13]). It has not been applied to any other problem for the optimal control of a denumerable Markov chain in continuous time. Note that the present model is a special case of a more general model that was studied in [14]. In that paper, it was assumed that the immigration and emigration rates were not necessarily equal and the cost rate caused by i pests was equal to di, where {di} is a nondecreasing sequence such that di→∞, as i→∞, and di≤Aim for some constant A>0 and integer m. The characterization of the form of the optimal policy was achieved in that work by the standard method of successive approximations that we describe in Section 1. The approach that we follow in the present paper is direct, since it does not use discounted programming. It includes only the solution of the corresponding average-cost optimality equation and the verification of certain conditions on the transition rates and on the cost rates. It also enables us, as we will see in Section 3, (i) to obtain a measure of the advantage of starting the process in state i≥0 rather than in some other state j≥0 when using the optimal policy and (ii) to obtain some interesting inequalities for the minimum average cost and the optimal critical value x*.


## 3. The Optimal Policy within the ClassP

The equilibrium probabilitiesπi, i=0,1,… under the policy Px, x≥1  satisfy the following balance equations:(3.1)2νπi=νπi-1+νπi+1,1≤i≤x-1,(2ν+1)πi=νπi-1+νπi+1,i≥x.The above equations together with the normalising condition∑i=0∞πi=1 yield(3.2)πi=2(1-ρ)[(ρ-1)i+x-ρ(x-1)](1-ρ)2x2+(1-ρ2)x+2ρ,0≤i≤x-1,πi=2(1-ρ)ρi-x+1(1-ρ)2x2+(1-ρ2)x+2ρ,i≥x,
where, ρ=(2ν+1-4ν+1)/(2ν).Using a well-known result (see, e.g., Theorem 5.10 in Ross [3]), the average cost gx under the policy Px can be expressed in terms of the equilibrium probabilities πi, i=0,1,… and the cost rates under Px as follows:(3.3)gx=∑i=0x-1πii+∑i=x∞πi(i+k).
Substituting (3.2) into (3.3), we obtain(3.4)gx=(1-ρ)3x3+3ρ(1-ρ)2x2+(1-ρ)(2ρ2+5ρ-1)x+6ρ2+6kρ(1-ρ)3(1-ρ)[(1-ρ)2x2+(1-ρ2)x+2ρ].Proposition 3.1.
There exists a policyPx* that is optimal within the class P. The appropriate value of x* is equal to θ+1, where θ is the integer part of the unique positive root of the polynomial
(3.5)A(x)=(1-ρ)3x4+4(1-ρ)2x3+(ρ-1)(ρ2-2ρ-5)x2+2(1-ρ)(2ρ+1-6kρ)x-12kρ,x≥0.Proof.
Using the above expression forgx we find for x≥1 that gx+1-gx is equal to A(x) multiplied by a positive quantity. Temporarily, treat x as a continuous real variable in the interval [0,∞). Note that A′′(x)>0, x≥0, since 0<ρ<1.Hence, A(x), x≥0  is strictly convex. The convexity of A(x), the inequality A(0)=-12kρ<0, and the fact that A(x)→∞, as x→∞  imply that the equation A(x)=0 has a unique positive root r and A(x)<0(0≤x<r), A(x)>0(x>r). It follows that the sequence gx, x=1,2,… attains its minimum at the integer x*=θ+1, where θ is the integer part of r.


## 4. Verification of Optimality

According to the results of Bather [10] the policy Px* is optimal within the class of all stationary policies if there exists a constant g and a sequence of nonnegative numbers {hi}, i=0,1,2,… such that(4.1)g=min⁡0≤u≤1{i+ku+νhi+1+uh0+νhi-1-(2ν+u)hi},i≥1,(4.2)g=νh1-νh0,(4.3)g=i+νhi+1+νhi-1-2νhi,1≤i≤x*-1,(4.4)g=i+k+νhi+1+νhi-1+h0-(2ν+1)hi,i≥x*,
and each stationary policy satisfies certain conditions on the cost rates and transition rates. Equation (4.1) is referred as the optimality equation. The cost structure and transition rates for the present problem are such that all Bather’s conditions are clearly satisfied, except for the following one, which needs careful attention.Given any stationary policy, letci be the cost rate in state i and qi the sum of the transition rates out of state i, i≥0. For every stationary policy, there must exist a positive, decreasing sequence {ϕi} and a positive integer n such that ∑i=n∞ϕi=∞ and(4.5)ci≥qihiϕi,i≥n.
Note that if the (4.1)–(4.4) and the condition (4.5) are satisfied, then the constant g turns out to be the minimum average cost. Thus, to verify the optimality of Px*, we choose g=gx*, so that from(3.4)(4.6)g=(1-ρ)3(x*)3+3ρ(1-ρ)2(x*)2+(1-ρ)(2ρ2+5ρ-1)x*+6ρ2+6kρ(1-ρ)3(1-ρ)[(1-ρ)2(x*)2+(1-ρ2)x*+2ρ],find a sequence(hi) such that (4.1)–(4.4) are satisfied, and then, for every stationary policy, find a sequence {ϕi} and an integer n such that condition (4.5) is satisfied. Let(4.7)h0=0.
The unique solution of the difference equations (4.3) and (4.4), given the conditions (4.2) and (4.7) and the expression (4.6) for g, is given by(4.8)hi=-16νi3+g2νi2+3g+16νi,0≤i≤x*,(4.9)hi=i+k-g+cρi,i≥x*-1,
where(4.10)c=[-(x*)3+3g(x*)2+(3g+1-6ν)x*-6ν(k-g)]6νρx*.Lemma 4.1.
The sequence{hi}, i=0,1,… defined by (4.8) and (4.9) is nonnegative and increasing.Proof.
From the expression (4.8), we have
(4.11)hi+1-hi=(i+1)(2g-i)2ν,0≤i≤x*-1.
Therefore to prove that the sequence {hi}, 0≤i≤x*, is nonnegative and increasing, it is sufficient to show that
(4.12)x*-1<2g.
Given the expression (4.6) for g, it can be easily verified that the inequality A(x*-1)≤0, which follows from the proof of Proposition 3.1, implies the above inequality. Hence, {hi}, 0≤i≤x*, is nonnegative and increasing. From the expression (4.9), we have
(4.13)Δhi≡hi+1-hi=1-c(1-ρ)ρi,i≥x*-1.
If c<0, then Δhi>0, i≥x*-1, since ρ<1, and hence {hi}, i≥x*-1 is increasing. If c>0, then {Δhi}, i≥x*-1 is increasing in i. Note that it has been proved that Δhx*-1=hx*-hx*-1>0. Hence, Δhi>0, i≥x*-1 and consequently, {hi}, i≥x*-1, is increasing.The function to be minimised on the right-hand side of (4.1) is linear function of u. Hence, the minimum is achieved either at u=0 or at u=1. Since  {hi} is solution of (4.3) and (4.4), to prove that (4.1) is satisfied, we need to check that(4.14)i+νhi+1+νhi-1-2νhi≤i+k+νhi+1+νhi-1+h0-(2ν+1)hi,1≤i≤x*-1,i+k+νhi+1+νhi-1+h0-(2ν+1)hi≤i+νhi+1+νhi-1-2νhi,i≥x*,
which simplify to(4.15)hi≤k,1≤i≤x*-1,(4.16)hi≥k,i≥x*.Using the result of Lemma4.1, we deduce that the inequalities (4.16) hold if and only if hx*≥k, which using (4.8) with i=x* can be written equivalently as(4.17)(x*)3-x*-6νk3x*(x*+1)≤g.
Substituting g from (4.6) and ν from the relation(4.18)ν=ρ(1-ρ)2,
the inequality (4.17) reduces to A(x*)≥0, which follows from the proof of Proposition 3.1.Ifx*>1, then we have to check that (4.15) holds, which again using the result of Lemma 4.1 is true if and only if hx*-1≤k. Using (4.8) with i=x*-1 the last inequality is equivalent to
(4.19)g≤(x*)3-3(x*)2+2x*+6νk3x*(x*-1).
Substituting for g from (4.6) and ν from (4.18), the above inequality reduces to A(x*-1)≤0, which follows from the proof of Proposition 3.1.Thus, it has been proved that the sequence{hi}, i≥0, defined by (4.8) and (4.9), satisfies (4.1). To prove the extra condition (4.5), let n=x* and
(4.20)ϕi=[(2ν+1)(i+k-g+cρi)]-1,i≥x*.
The fact that the sequence {ϕi}, i≥x*  is positive and decreasing with ∑i=n∞ϕi=∞ is immediate from its definition and Lemma 4.1. For every stationary policy f and every state i, i≥x*, we have that ci≥i and qi≤2ν+1. Hence, the sequence {ϕi} will satisfy (4.5) for all stationary policies if
(4.21)i≥(2ν+1)(i+k-g+cρi)ϕi,i≥x*.
The sequence {ϕi} as defined in (4.20) satisfies the above inequalities.The proof of the following proposition, which is the main result of the paper, has been completed.Proposition 4.2.
The policyPx* is optimal within the class of all stationary policies.Remark 4.3.
The method that we use in the present work for proving the optimality ofPx* enables us to compute the difference hi-hj for any states i,j≥0. This difference is equal to the difference in total expected costs over an infinitely long period of time by starting in state i rather than in state j when using the policy Px* (see Chapter 3 in Tijms’s book [8]).Remark 4.4.
The inequalities (4.17) and (4.19) imply that the minimum average cost g is bounded below and above by two rational functions of the optimal critical point x*. Note also that from (4.17) and (4.19), we deduce that x* is bounded above by the square root of 1+12νk.


## 5. Numerical Results

In Table1, we present for different values of ν and k the critical number x* for the present model and the critical number x′ for the simpler model in which a simple immigration process is controlled through total catastrophes (see Kyriakidis and Abakuks [12]). The value of x* is equal to θ+1, where θ is the integer part of the unique positive root of A(x)=0, while x′ is found from (2.9) in [12]. In Table 2, we present the corresponding minimum average costs gx* and gx′ (see (4) and (3.5) in [12]).Table 1
The critical numbersx*, x′.
ν∖k151020500.51,12,23,34,46,711,13,34,45,67,952,15,46,68,1012,18103,16,58,810,1315,23203,17,59,913,1519,29507,19,512,1016,1724,37Table 2
The minimum average costsgx*, gx′.
ν∖k151020500.50.63, 0.831.19, 1.901.55, 2.782.26, 4.632.90, 6.6311.00, 1.501.63, 3.002.10, 4.202.71, 6.003.80, 9.6052.31, 5.833.34, 8.444.10, 10.915.12, 14.676.92, 22.52103.28, 10.914.50, 14.005.42, 17.116.67, 22.098.92, 32.82204.63, 20.956.05, 24.407.17, 28.148.69, 34.4311.48, 48.69507.44, 50.988.99, 54.7310.38, 59.0812.35, 66.9616.04, 86.39From Table1, we see that the critical points x* and x′ are nondecreasing as k increases, for fixed ν. This is intuitively reasonable, since it seems preferable to avoid introducing catastrophes if the cost of their introduction take large values. From this table we can see that the critical points x* and x′ are nondecreasing as ν increases for fixed k.We also observe that for k∈{1,5,10}, the critical value x* is greater or equal to the critical value x′, while for k∈{20,50}, the critical value x* is smaller or equal to the critical value x′. This can be explained intuitively, since, in the model of the present paper, for large values of k, it seems preferable to initiate the mechanism that introduces catastrophes when the population size is relatively small, because the emigrations of pests may reduce their size below the critical point before a catastrophe occurs. Consequently, in this case, the catastrophe mechanism, which causes high costs, stops. From Table 2, we see that for fixed value of ν, the minimum average costs gx* and gx′ increase as k increases. From this table we can also see that, for fixed value of k, the minimum average costs gx* and gx′ increase as ν increases. We also observe that in all cases, gx* is considerably smaller than gx′. This is intuitively reasonable, since the emigration of the individuals causes a considerable reduction of the cost that they cause.


## 6. Control of the Asymmetric Process

Consider the same model as the one introduced in Section1 with the following modification: the emigration rate of the pests is μ, where μ is different from the immigration rate ν. As stated in Section 2, the optimality of a control-limit policy can be proved through the discounted-cost problem (see [14]). However, in this case, it is not possible to repeat the approach that we developed in the case in which ν is equal to μ. This is due to the fact that it is difficult to minimize analytically with respect to x  the average cost gx, x≥1 of the control-limit policy Px, since it is given by(6.1)gx=Num(x)Den(x),x≥1,
where(6.2)Num(x)=βx-1[(1-β)2(1-r)2(r-β)x2+(r-1)(1-β)(3βr-1-r-β)x+2(r-β)(r2β2+r+β-3rβ)+2kr(1-β)3(1-r)]+2β(1-r)3,(6.3)Den(x)=2(1-β)(1-r)[βx-1[(β-r)(β-1)(1-r)x+(r-β)(1-rβ)]+(1-r)2],(6.4)r=(ν+μ+1-(ν-μ)2+2(ν+μ)+1)(2μ),β=νμ.
Nevertheless, it can be shown by arguments similar to those presented in Section 4 that if(6.5)k≤[ν+(μ-ν)(μr-ν)](1-r)+(μr-ν)r(1-r)[νr+μr(1-r)],then the policyP1 is optimal, since the corresponding optimality equation is satisfied with g=g1 and(6.6)hi=i+ν-μ+k-g1+(μ+g1-ν-k)(μν-1r)i,i≥0.


## 7. Discussion

A widely used criterion for the optimal control of a stochastic process is the minimization of the expected long-run average cost per unit time. A usual method in the literature to prove that the optimal policy has a specific structure is to show that the solution of the corresponding average-cost optimality equation possess specific properties such as monotonicity or convexity. This is usually achieved through the corresponding finite-horizon and infinite-horizon discounted cost problems, since, in general, it is difficult to solve explicitly the average-cost optimality equation.In the present paper, we present a problem for controlling a denumerable Markov chain in continuous time in which it is possible to solve explicitly the average-cost optimality equation. Consequently, a particular stationary policy is proved to be average-cost optimal, since in this problem, some extra conditions on the cost rates and on the transition rates are valid.



---

*Source: 617812-2011-05-30.xml*