A Survey of

Blackwell optimality

Arie Hordijk University of Leiden, Mathematical Institute, P.O. Box 9512, 2300 RA Leiden, The Netherlands E-mail: hordijk@math.leidenuniv.nl

Alexander A. Yushkevich University of North Carolina at Charlotte, Department of Mathematics, Charlotte, NC 28223, USA E-mail: aayushke@email.uncc.edu

1. Finite models

In this introductory section we consider Blackwell optimality in Controlled Markov Processes (CMPs) with finite state and action spaces; for brevity,we call them finite models. We introduce the basic definitions, the Laurent-expansion technique, the lexicographical policy improvement, and the Blackwell optimality equation, which were developed at the early stage of the study of sensitive criteria in CMPs. We also mention some extensions and generalizations obtained afterwards for the case of a finite state space.

1.1 Definition and existence of Blackwell optimal policies. We consider an infinite horizon CMP with a finite state space 𝕏, a finite action space 𝔸, action sets 𝔸(x) = A_{x}, transition probabilities p_{xy}(a) = p(y|x, a), and reward function r(x, a) (x ∈ X, a ∈ A_{x}, y ∈ X). Let m be the number of states in 𝕏.

We refer to Chapter 1 for definitions of various policies, of probability distributions and expectations corresponding to them, and notations. We also use the notation

(1)  𝕂 = {(x, a) : a ∈ 𝔸(x), x ∈ 𝕏},

so that, in particular,

(2)  P^{a}f(x) = ∑_{y∈𝕏} p_{xy}(a)f(y),  (x, a) ∈ 𝕂.

For every discount factor β ∈ (0, 1) the expected total reward

(3)  v(x, π, β) = v_{β}(x, π) := 𝔼_{x}^{π} [∑_{t=0}^{∞} β^{t}r(x_{t}, a_{t})]

converges absolutely and uniformly in the initial state x and policy π, so that the value function

V (x, β) = V_{β}(x) := sup_{π∈Π} v_{β}(x, π), x ∈ X

is well defined and finite. Following Blackwell [3], in this chapter we say that a policy π is β-optimal if v_{β}(x, π) = V_{β}(x) for all x ∈ X (not to confuse with ϵ-optimal policies, for which v_{β}(π) ≥ V_{β} − ϵ; in this chapter we do not use them).

In the case of a stationary policy φ ∈ Π^{s} it is convenient to write (3) in matrix notations. In that case we have an m × m transition matrix P (φ) = P^{φ} with entries p_{xy}(φ(x)) = p_{xy}^{φ}, and (3) can be written in the form

(4)  v_{β}(φ) = v_{β}^{φ} = ∑_{t=0}^{∞} (βP^{φ})^{t}r^{φ} = (I − βP^{φ})^{−1}r^{φ}

where r^{φ} is a vector with entries r(x, φ(x)), x ∈ 𝕏 (formula (4) has sense also for complex β with |β| < 1), (in the notation (2) P^{φ}f(x) = P^{φ(x)}f(x)). For every β ∈ (0, 1) there exists a β-optimal policy φ_{β} ∈ Π^{s}; namely, one may set

φ_{β}(x) = argmax_{a∈A_{x}}[r(x, a) + β ∑_{y∈X} P^{a}v_{β}(x)], x ∈ 𝕏.

In the important case of undiscounted rewards, when β = 1, the total expected reward in general diverges, and the simplest performance measure is the average expected reward w(x, π) = w^{π}(x) (see Chapter 1). For a stationary policy φ

(5)  w^{φ} = lim_{n→∞} \frac{1}{n} ∑_{t=0}^{n−1} (P^{φ})^{t}r^{φ} = Q^{φ}r^{φ} = lim_{β↑1}(1 − β)v_{β}^{φ},

where Q^{φ} = Q(φ) is the stationary matrix

(6)  Q^{φ} = lim_{N→∞} \frac{1}{N + 1} ∑_{t=0}^{N} (P^{φ})^{t}, and Q^{φ}P^{φ} = P^{φ}Q^{φ} = Q^{φ}.

The last expression for w^{φ} in (5) follows from (3) and the fact that Cesaro summability of a divergent series implies its Abel summability to the same limit. Howard [26] proved the existence of average optimal policies in finite CMPs with the class Π^{s} of admissible policies, and developed a policy improvement algorithm to find them, related with his name. Almost at the same time Wagner [41] determined that such policies are average optimal in the class Π too.

However, the average reward criterion is unsensitive, underselective since it is entirely determined by the arbitrarily far tail of the rewards; in accordance with this criterion, two policies providing rewards 100 + 0 + 0 + ⋯ and 0 + 0 + 0 + ⋯ are equally good (or bad). Blackwell [3] in his study of finite CMPs introduced a much more sensitive concept of optimality, that bears now his name, and proved the existence of stationary policies optimal in this new sense.

Definition 1. A policy π is said to be Blackwell optimal, if π is β-optimal for all values of β in an interval β_{0} < β < 1.

A stationary Blackwell optimal policy φ is average optimal. Indeed, there exists a stationary average optimal policy ψ, and by (5)

w^{ψ} = lim_{β↑1}(1 − β)v_{β}^{ψ} ≤ lim_{β↑1}(1 − β)v_{β}^{φ} = w^{φ},

so that w^{φ} = w^{ψ}. Since the last limit is the same for all Blackwell optimal policies, stationary or not (as follows from Definition 1), and since by Theorem 2 below there is a stationary Blackwell optimal policy, every Blackwell optimal policy π ∈ Π is average optimal.

Theorem 2 In finite CMP there exists a stationary Blackwell optimal policy.

Proof. Since for every positive β < 1 there exists a β-optimal policy φ_{β} ∈ Π^{s}, and because the set Π^{s} of stationary policies is finite together with 𝕏 and 𝔸, there exists a stationary policy φ which is β-optimal for all β = β_{n} where β_{n} ↑ 1. We claim that φ is Blackwell optimal.

Suppose the contrary. Then, because 𝕏 and Π^{s} are finite sets, there are a state x_{0}, a policy ψ ∈ Π^{s}, and a sequence γ_{n} ↑ 1 such that

v_{β}^{φ}(x_{0}) < v_{β}^{ψ}(x_{0}) for β = γ_{n}, γ_{n} ↑ 1.

On the other hand, by the selection of φ

v_{β}^{φ}(x_{0}) ≥ v_{β}^{ψ}(x_{0}) for β = β_{n} ↑ 1.

It follows that the function

f(β) = v_{β}^{φ}(x_{0}) − v_{β}^{ψ}(x_{0})

defined for all complex β with |β| < 1 takes on the value 0 at an infinite sequence of different points z_{n} ↑ 1, and takes on nonzero values at the points γ_{n} ↑ 1.

By using Cramer’s rule to compute the inverse matrix, we find that each entry of (I − βP^{φ})^{−1} is a rational function of β, and the same is true with ψ in place of φ. Therefore and by (4), f(β) is a rational function of the complex variable β in the circle |β| < 1 (and hence on the whole complex plane). A rational function cannot have infinitely many different zeros z_{n} if it is not an identical zero. The obtained contradiction proves that φ is Blackwell optimal.

The above proof is a purely existence argument, without any indication how to find a Blackwell optimal policy φ. Blackwell’s original proof also did not provide a complete algorithm to obtain φ, but it contained some essential elements in this direction. Blackwell used, besides the limiting matrix Q^{φ}, the deviation matrix D^{φ} corresponding to φ ∈ Π^{s}. If the Markov chain with the transition matrix P^{φ} is aperiodic, then

(7)  D^{φ} = ∑_{t=0}^{∞}[(P^{φ})^{t} − Q^{φ}],

and the above series converges geometrically fast; in general

(7′)  D^{φ} = lim_{N→∞} \frac{1}{N + 1} ∑_{n=0}^{N} ∑_{t=0}^{n}[(P^{φ})^{t} − Q^{φ}].

An important property of this matrix is that D^{φ} is uniquely determined by the equations

D^{φ}Q^{φ} = Q^{φ}D^{φ} = 0, (8) D^{φ}(I − P^{φ}) = (I − P^{φ})D^{φ} = I − Q^{φ} (9)

(see, for instance, Kemeny and Snell [27]). Blackwell derived and utilized the expansion

(10)  v_{β}^{φ} = \frac{h_{−1}^{φ}}{1 − β} + h_{0}^{φ} + o(1)  as β ↑ 1,

where

(11)  h_{−1}^{φ} = Q^{φ}r^{φ},  h_{0}^{φ} = D^{φ}r^{φ},

and introduced the notion of a nearly optimal policy π ∈ Π. For such a policy V_{β}−v_{β}^{π} = o(1) as β ↑ 1.

The existence of a Blackwell optimal policy φ ∈ Π^{s} implies a similar expansion for the value function

(12)  V_{β}(x) = \frac{h_{−1}}{1 − β} + h_{0} + o(1)  as β ↑ 1.

It is easy to see using (12), that a policy π is average optimal iff v_{β}^{π} = h_{−1}/α + o(1/α), where α = 1 − β, and that π is nearly optimal iff v_{β}^{π} = h_{−1}/α + h_{0} + o(1).

1.2. Laurent series expansions and n-discount optimality. Average optimal and nearly optimal policies, as well as relations (10)-(12), are at the start of a chain of notions and equations developed by Miller and Veinott [30] and Veinott[38], which lead to a deeper insight into Blackwell optimal policies and to an algorithm to find them. We present their main ideas in a slightly modified form.

The approach is based on the Laurent series expansion of the resolvent

(13)  R_{β} = (I − βP)^{−1} = I + βP + β^{2}P^{2} + ⋯  (|β| < 1)

of a Markov chain with the transition kernel P in the neighborhood of the point β = 1. This expansion is a general fact known in functional analysis (see, for instance, [43]). In the particular case of an aperiodic Markov chain, it follows immediately from the geometric convergence of P^{t} to the limiting matrix Q. Indeed, the difference

R_{β} − \frac{1}{1 − β} Q = (I − Q) + β(P − Q) + β^{2}(P^{2} − Q) + ⋯,

in which ∥P^{n} − Q∥ ≤ Cγ^{n} for some γ < 1, is an analytic function of the complex variable β in the circle |β| < 1/γ (we use the norm in the space of (m × m)-matrices generated by the supremum norm in the space of m-vectors). The point β = 1 is inside this circle, thus R_{β} has the same singularity at the point β = 1 as \frac{1}{1−β} Q, i.e. has a single pole. Therefore in some ring 0 < |β − 1| < α_{0} a Laurent expansion

(14)  R_{β} = \frac{R_{−1}}{α} + R_{0} + R_{1}α + R_{2}α^{2} + ⋯,  α = 1 − β

holds. If the Markov chain is periodic, consider the least common multiple d of the periods of all its ergodic classes. The chain with a kernel P^{d} is then aperiodic, so that P^{nd} converges geometrically fast to a stochastic matrix Q̃ as n → ∞. Similar to the preceding argument, it follows that the infinite sum

R̃_{β} = I + β^{d}P + β^{2d}P^{2} + ⋯

is analytic in a circle |β|^{d} < 1/γ of a radius greater than 1, and thus has a simple pole at β = 1. Then the same is true for

R_{β} = (I + βP + ⋯ + β^{d−1}P^{d−1})R̃_{β}.

Instead of the Laurent series (14), one may write a similar series in powers of another small parameter ρ equivalent to α, which has the meaning of an interest rate:

(15)  ρ = \frac{1 − β}{β} = \frac{α}{1 − α},  β = \frac{1}{1 + ρ} = 1 − α.

Veinott [38] and most of the subsequent authors used series in ρ. Chitashvili [6][7][51] and following him Yushkevich [44]-[50] used series in α. We present both versions.

Theorem 3 In a finite CMP there exists a number β_{0} ∈ (0, 1) such that for every policy φ ∈ Π^{s}

(16)  v_{β}^{φ} = (1 + ρ) ∑_{n=−1}^{∞} h_{n}^{φ}ρ^{n} = ∑_{n=−1}^{∞} k_{n}^{φ}α^{n},  β_{0} < β < 1

where

(17)  h_{−1}^{φ} = k_{−1}^{φ} = Q^{φ}r^{φ} = w^{φ},  h_{0}^{φ} = k_{0}^{φ} = D^{φ}r^{φ}

(cf. (10) and (11)), and where for n ≥ 1

(18)  h_{n}^{φ} = (−D^{φ})^{n}h_{0}^{φ},  k_{n}^{φ} = (I − D^{φ})^{n}k_{0}^{φ}.

A similar expansion is valid for the value function

(19)  V_{β} = (1 + ρ) ∑_{n=−1}^{∞} h_{n}ρ^{n} = ∑_{n=−1}^{∞} k_{n}α^{n},  β_{0} < β < 1.

Proof. The existence and convergence of Laurent expansions (16) follow from expansions in powers of ρ or α of βR_{β}^{φ}, respectively R_{β}^{φ}, and from the formula v_{β}^{φ} = R_{β}^{φ}r^{φ} equivalent to (4). To get the coefficients (17)-(18), observe that by (4) v_{β}^{φ} = r^{φ} + βP^{φ}v_{β}^{φ}, so that by (15) and (16)

(1 + ρ) ∑_{−1}^{∞} h_{n}^{φ}ρ^{n} = r^{φ} + P^{φ} ∑_{−1}^{∞} h_{n}^{φ}ρ^{n}.

By the uniqueness of the coefficients of power series, this results in equations (to simplify writing, we temporarily skip the superscript φ):

(20)  h_{−1} = P h_{−1},
(21)  h_{0} + h_{−1} = r + P h_{0},
(22)  h_{n} + h_{n−1} = P h_{n}  (n ≥ 1).

From (6) and (20) by iteration and taking a limit, we find h_{−1} = Qh_{−1}. For the stationary matrix Q = QP = P Q, and a multiplication of (21) by Q gives Qh_{−1} = Qr, so that h_{−1} = Qr as in (17). A multiplication of (22) by Q provides Qh_{n} = 0 (n ≥ 0). Using this, the relation h_{−1} = Qh_{−1} and (8)-(9), we get after a multiplication of (21) by D = D^{φ}, that D(I −P)h_{0} +DQh_{−1} = Dr, or (I −Q)h_{0} = Dr, or finally h_{0} = Dr as in (17). Multiplying (22) by D, in a similar way we get D(I − P)h_{n} + Dh_{n−1} = 0, or h_{n} − Qh_{n} = −Dh_{n−1}, or h_{n} = −Dh_{n−1} (n ≥ 1), and this proves that h_{n} = (−D)^{n}h_{0} as in (18). Formulas (17)-(18) for k_{n}^{φ} follow absolutely similarly from equations k_{−1} = P k_{−1}, k_{0} + P k_{−1} = r + P k_{0} and k_{n} + P k_{n−1} = P k_{n} instead of (20)-(22).

Since the set Π^{s} is finite, we have the expansions (16) simultaneously for all φ ∈ Π^{s} in some interval (β_{0}, 1). Formula (19) follows now from Theorem 2.

Formulas of Theorem 3 are a generalization of (10) and (11). They stimulate a similar generalization of the average optimality and nearly optimality criteria. The following definition is due to Veinott [39].

Definition 4 For n ≥ 1, a policy π^{∗} ∈ Π is said to be n-discount optimal, if for every π ∈ Π

(23)  \underline{lim}_{β↑1} ρ^{−n}[v_{β}(π^{∗}) − v_{β}(π)] ≥ 0

(with α in place of ρ we have an equivalent condition).

By substituting in (23) a Blackwell optimal policy π, for which v_{β}(π) = V_{β} and v_{β}(π^{∗})− v_{β}(π) ≤ 0, one may see that in finite CMPs condition (23) is equivalent to a simpler (and formally stronger) condition

(24)  lim_{β↑1} ρ^{−n}[V_{β} − v_{β}(π^{∗})] = 0.

However, condition (23) appeared to be more suitable for an extension of sensitive criteria to denumerable and Borelian CMPs. To avoid confusion, mention that in literature 0discount optimal policies are sometimes called bias-optimal or 1-optimal; the latter name originates from Veinott [38]. Also, as seen from a comparison of (16) and (19), a stationary policy is Blackwell optimal iff it is n-discount optimal for every natural n, or, briefly speaking, is ∞-discount optimal.

A convenient description of n-discount optimal policies can be made in terms of sequences of coefficients of series (16) and (19) and a lexicographical ordering in spaces of them. Define

(25)  H^{φ} = {h_{−1}^{φ}, h_{0}^{φ}, …}, K^{φ} = {k_{−1}^{φ}, k_{0}^{φ}, …},

let H_{n}^{φ} and K_{n}^{φ} be the initial segments of H^{φ} and K^{φ} up to the n-th term, and let H, K, H_{n} and K_{n} have the same meaning for the series (19) (each h_{n}^{φ} etc. is an m-vector). For those sequences and segments we introduce a natural lexicographical ordering denoted by symbols ≻, ⪰, ⪯, ≺. So, H^{φ} ≺ H^{ψ} means that H^{φ} ≠ H^{ψ}, and that there exists a number N < ∞ and a state x_{0} ∈ 𝕏, such that H_{N−1}^{φ} = H_{N−1}^{ψ} (if N ≥ 0), and h_{N}^{φ}(x_{0}) < h_{N}^{ψ}(x_{0}) while h_{N}^{φ}(x) ≤ h_{N}^{ψ}(x) for all other x ∈ 𝕏. The relation H^{φ} ⪯ H^{ψ} means that either H^{φ} = H^{ψ} or H^{φ} ≺ H^{ψ}. The relations H^{ψ} ≻ H^{φ} and H^{ψ} ⪰ H^{φ} are equivalent to H^{φ} ≺ H^{ψ} and H^{φ} ⪯ H^{ψ}.

With this notation we have H^{φ} ⪯ H and K^{φ} ⪯ K for every φ ∈ Π^{s}, and the policy φ is n-discount optimal (or Blackwell optimal) iff H_{n}^{φ} = H_{n} or K_{n}^{φ} = K_{n} (respectively, if H^{φ} = H or K^{φ} = K).

The following theorem due to Veinott [39] shows that in finite CMPs the n-th discount optimality of a stationary policy for large values of n coincides with its Blackwell optimality. Let Φ_{n} be the subset of Π^{s} consisting of all stationary n-discount optimal policies (n ≥ −1), and let Φ_{∞} be the set of all Blackwell optimal policies in Π^{s}. Evidently,

Φ_{−1} ⊃ Φ_{0} ⊃ Φ_{1} ⊃ ⋯, Φ_{∞} = ⋂_{n} Φ_{n}.

Theorem 5 In finite CMPs with m ≥ 2 states

Φ_{m−1} = Φ_{m} = … = Φ_{∞}.

Proof. It is sufficient to show that Φ_{m−1} = Φ_{∞}. Consider any policy φ ∈ Φ_{m−1}. We have H_{m−1}^{φ} = H_{m−1}, or in more detail

(26)  h_{n}^{φ} = h_{n},  n = −1, 0, 1, …, m − 1.

Since m ≥ 2, both h_{0} and h_{1} are present in (26). We claim that m column m-vectors h_{0}, h_{1}, …, h_{m−1} are linearly dependent. It is sufficient to show that m row vectors of the corresponding square matrix are linearly dependent; these rows are {h_{0}(x), …, h_{m−1}(x)} = {h_{0}^{φ}(x), …, h_{m−1}^{φ}(x)}, x ∈ 𝕏. In fact even the infinite sequences

(27)  {h_{0}^{φ}(x), h_{1}^{φ}(x), …, h_{t}^{φ}(x), …},  x ∈ 𝕏

are linearly dependent. Indeed, in the finite Markov chain generated by P^{φ} there exists a stationary distribution {μ(x), x ∈ 𝕏}. The total discounted expected reward corresponding to the initial distribution μ and policy φ is equal to

(28)  v_{β}^{φ}(μ) := ∑_{x∈𝕏} μ(x)v_{β}^{φ}(x) = ∑_{x∈𝕏} μ(x) 𝔼_{x}^{φ} ∑_{t=0}^{∞} β^{t}r(x_{t}, φ(x_{t})) =

= ∑_{t=0}^{∞} β^{t} ∑_{x∈𝕏} μ(x) 𝔼_{x}^{φ} r(x_{t}, φ(x_{t})) = ∑_{t=0}^{∞} β^{t} 𝔼_{μ}^{φ} r(x_{t}, φ(x_{t})).

Here the ℙ_{μ}^{φ}-distribution of x_{t} does not depend on t because μ is a stationary distribution, and hence the factor at β^{t} in (28) is some constant C. Thus

(29)  v_{β}^{φ}(μ) = C ∑_{t=0}^{∞} β^{t} = \frac{C}{1 − β} = C \frac{1 + ρ}{ρ} = (1 + ρ) [\frac{C}{ρ} + ∑_{n=0}^{∞} 0 · ρ^{n}]

(cf. (15)). On the other hand, by (28) and (16),

v_{β}^{φ}(μ) = (1 + ρ) ∑_{n=−1}^{∞} ρ^{n} ∑_{x∈𝕏} μ(x)h_{n}^{φ}(x).

A comparison with (29) together with the uniqueness of the Laurent coefficients show that ∑_{x} μ(x)h_{n}^{φ}(x) = 0 for all n ≥ 0, so that the sequences (27) are linearly dependent.

Now, by (18)

(30)  h_{n+1}^{φ} = −D^{φ}h_{n}^{φ},  h_{n+1} = −D^{ψ}h_{n}  (n = 0, 1, 2, …)

where ψ is a Blackwell optimal policy. Let t be the maximal integer such that the vectors h_{0} = h_{0}^{φ}, …, h_{t} = h_{t}^{φ} in (26) are linearly independent; such t ≥ 0 exists if only h_{0} ≠ 0, and as just proved, t < m − 1. If h_{0} = 0, then by (26) also h_{0}^{φ} = 0, and by (30) h_{n}^{φ} = 0 = h_{n} for all h ≥ 0, so that H^{φ} = H and φ ∈ Φ_{∞}. If there is the required t, then h_{t+1} = h_{t+1}^{φ} is a linear combination of h_{0} = h_{0}^{φ}, …, h_{t} = h_{t}^{φ}:

(31)  h_{t+1} = ∑_{i=0}^{t} C_{i}h_{i},  h_{t+1}^{φ} = ∑_{i=0}^{t} C_{i}h_{i}^{φ}.

Due to (30) multiplying the first identity by −D^{ψ} and the second by −D^{φ}, we only increase every subscript in (31) by 1, and since h_{i}^{φ} = h_{i} for 0 ≤ i ≤ t + 1, we get h_{t+2}^{φ} = h_{t+2}. Repeating this, by induction we get h_{n}^{φ} = h_{n} for every n ≥ 0, so that φ ∈ Φ_{∞}.

The sets Φ_{m−2} and Φ_{m−1} are in general different. The following example, taken from [39], confirms this statement. To make it more visual, we present it for m = 5.

Example 6. There are m = 5 states 1, 2, …, 5 with mandatory transitions 2 → 3 → 4 → 5, the state 5 is absorbing. In the state 1 there is a choice between two actions, which determine two stationary policies φ and ψ (see Fig. 1). Under φ we have a mandatory transition 1 → 2, under ψ transitions 1 → 1 and 1 → 2 are equally likely. The numbers under arrows indicate the rewards r(x, a). Mention that the rewards 2, −6, 6, −2 are the binomial coefficients of (A − B)^{m−2} = (A − B)^{3} multiplied by 2.

p_{11}(ψ)= \frac{1}{2} p_{12}(ψ)= \frac{1}{2}

p_{12}(φ)=1

Figure 1.

The expected rewards v_{β}^{φ} and v_{β}^{ψ} differ only at the initial state 1. For φ we have

v_{β}^{φ}(1) = 2 − 6β + 6β^{2} − 2β^{3} = 2(1 − β)^{3} = 2α^{3}.

For ψ, by the formula v_{β}^{ψ} = r^{ψ} + βP^{ψ}v_{β}^{ψ} (cf. (4)) we have the equation

v_{β}^{ψ} = 1 + β[\frac{1}{2}v_{β}^{ψ}(1) + \frac{1}{2}v_{β}^{ψ}(2)].

Thus

(2 − β)v_{β}^{ψ}(1) = 2 + βv_{β}^{ψ}(2),

where

βv_{β}^{ψ}(2) = β(−6 + 6β − 2β^{2}) = v_{β}^{φ}(1) − 2.

Hence

v_{β}^{ψ}(1) = \frac{v_{β}^{φ}(1)}{2 − β} = \frac{2α^{3}}{1 + α} = 2α^{3} − 2α^{4} + 2α^{5} − · · · .

This means that V_{β}(1) = 2α^{3}, that φ is Blackwell optimal, and that ψ is 3-discount optimal, but not 4-discount optimal. Thus Φ_{3} ≠ Φ_{4} = Φ_{∞}.

1.3. Lexicographical policy improvement and Blackwell optimality equation. Policy improvement is both a practical method to approach an optimal policy in CMPs and an important tool in their theory. Its essense is that if φ and ψ are two stationary policies, if π = ψφ^{∞} is a Markov policy coinciding with ψ at the first step of the control and coinciding with φ afterwards, and if π is better than φ, then ψ is also better than φ. This method, almost trivial for the discounted reward criterion with a fixed β < 1, was developed by Howard [26] for the average reward criterion. Howard used, besides the avarage reward w^{φ}(= h_{−1}^{φ}), a bias function, in fact connected with the term h_{0}^{φ} in the expansions (10) and (16). Blackwell [3] provided a rigorous proof that a slightly different version of Howard’s policy improvement method does converge. Miller and Veinott [30] have extended policy improvement to the case of Blackwell optimality, and Veinott [39] refined it using the classes Φ_{n}. We expose this topic in a modernized form, using an operator approach developed in Dekker and Hordijk [8] in the framework of CMPs with a countable state space 𝕏. To avoid additional formulas, we do all calculations in terms of ρ; in terms of α formulas are slightly different.

From the structure of π and (14) we have

v_{β}^{π} = r^{ψ} + βP^{ψ}v_{β}^{φ} = r^{ψ} + \frac{1}{1 + ρ}P^{ψ}v_{β}^{φ} = r^{ψ} + P^{ψ} ∑_{n=−1}^{∞} h_{n}^{φ}ρ^{n},

while

v_{β}^{φ} = h_{−1}^{φ}ρ^{−1} + ∑_{n=0}^{∞}(h_{n}^{φ} + h_{n−1}^{φ})ρ^{n}.

Subtracting, we get

(32) v_{β}^{π} − v_{β}^{φ} = (P^{ψ}h_{−1} − h_{−1})ρ^{−1} + (r^{ψ} + P^{ψ}h_{0} − h_{0} − h_{−1}) + ∑_{n=1}^{∞}(P^{ψ}h_{n} − h_{n} − h_{n−1})ρ^{n}

where it is understood that h_{n} = h_{n}^{φ}. By (18), the supremum norm ∥h_{n}^{φ}∥ is growing no more than geometrically fast with n.

It is convenient to introduce the space ℌ of all sequences H = {h_{n}, n ≥ −1} of mvectors satisfying this growth condition, and to treat the sequences of Laurent coefficients of the series (16), (32) etc. as elements of ℌ. In particular H^{φ} ∈ ℌ (see (25)), and in ℌ we consider the same lexicographical ordering as we have introduced in connection with H^{φ}. Also, it is convenient to define the spaces ℌ_{n} of finite collections H_{n} = {h_{t}, −1 ≤ t ≤ n} of m-vectors.

The right side of (32) defines an operator L^{ψ} in the spaces ℌ and ℌ_{n}. Since the matrix P^{ψ} has entries p_{xy}(a) with a = ψ(x), we express L^{ψ} through the corresponding operators L^{a} transforming functions (vectors) on 𝕏 into functions of pairs (x, a) on the state-action space 𝕂 defined in (1). We have

(L^{ψ}H)(x) = L^{ψ(x)}H(x), x ∈ 𝕏, (33) L^{a}H(x) = {ℓh_{−1}^{a}(x), ℓh_{0}^{a}(x), ℓh_{1}^{a}(x), …}, (x, a) ∈ 𝕂, (34) where according to (32)

(35)  \begin{aligned}ℓh_{−1}^{a}(x) & = P^{a}h_{−1}(x) − h_{−1}(x), \\ ℓh_{0}^{a}(x) & = r(x, a) + P^{a}h_{0}(x) − h_{0}(x) − h_{−1}(x), \\ ℓh_{n}^{a}(x) & = P^{a}h_{n}(x) − h_{n}(x) − h_{n−1}(x)  (n ≥ 1). \end{aligned}

The same formulas define L^{a} and L^{ψ}, as operators on ℌ_{n}.

Lemma 7 Let φ, ψ ∈ Π^{s}. If (L^{ψ}H^{φ})_{n+1} ⪰ 0 for some n ≥ −1, then H_{n}^{ψ} ⪰ H_{n}^{φ}. Moreover, if in addition (L^{ψ}H^{φ})_{n+1}(x_{0}) ≻ 0 at some x_{0} ∈ 𝕏, then H_{n}^{ψ}(x_{0}) ≻ H_{n}^{φ}(x_{0}). The same is true with the reverse inequality signs.

In particular, if L^{ψ}H^{φ} = 0, then H^{ψ} = H^{φ}.

Proof. The condition (L^{ψ}H^{φ})_{n} ⪰ 0 means that

(36)  v_{β}^{π} = v_{β}^{φ} + Q_{n}(ρ) + O(ρ^{n+1})

where Q_{n}(ρ) is a vector consisting of polynomials of degree ≤ n with lexicographically nonnegative coefficients, and where O(ρ^{n+1}) is uniform in x ∈ 𝕏 since 𝕏 and 𝔸 are finite sets (compare (32) with (33)-(35)). Consider policies π_{t} = ψ^{t}φ^{∞}, and let v(t) = v_{β}(π_{t}), so that, in particular, v(0) = v_{β}^{φ}, v(1) = v_{β}^{π}. We have

(37)  v(t + 1) = r^{ψ} + βP^{ψ}v(t),  t = 0, 1, 2, …

and by (36)

(38)  v(1) = v(0) + Q_{n} + R,

where the remainder R is of order ρ^{n+1}. From (37) and (38) by induction we get

v(t) = v(0) + (I + βP^{ψ} + (β^{2}P^{ψ})^{2} + ⋯ + (βP^{ψ})^{t−1})(Q_{n} + R), t ≥ 1.

(we use that r^{ψ} + βP^{ψ}v(0) = v(0) + Q_{n} + R according to (37) and (38)). Since β < 1, in the limit v(t) becomes v(∞) = v_{β}^{ψ}, so that

v_{β}^{ψ} = v_{β}^{φ} + ∑_{t=0}^{∞}(βP^{ψ})^{t}(Q_{n}(ρ) + R) = v_{β}^{φ} + R_{β}^{ψ}(Q_{n} + R).

Here Q_{n} ≥ 0 for small ρ > 0, R is of order O(ρ^{n+1}), and the resolvent R_{β}^{ψ} is of order O(1 + β + β^{2} + ⋯) = O(ρ^{−1}). This proves that H_{n−1}^{ψ} ⪰ H_{n−1}^{φ} if L^{ψ}H_{n}^{φ} ⪰ 0. Other assertions are proved in a similar way.

To proceed further, we need the lexicographical Bellman operator L in the spaces ℌ and ℌ_{n}:

(39)  LH(x) = max_{a∈𝔸_{x}} L^{a}H(x),  H ∈ ℌ, x ∈ 𝕏,

where the maximum is understood in the lexicographical sense ⪰; the same formula holds for H_{n} ∈ ℌ_{n}. This maximum always exists because the sets 𝔸_{x} are finite. Since one may use all combinations of actions in stationary policies, formula

(40)  LH = max_{ψ∈Π^{s}} L^{ψ}H

defines the same operator L.

If in (32) ψ = φ then π = ψφ^{∞} coincides with φ, and the left side of (32) is zero. Hence all the coefficients at the right side vanish, and this means that L^{φ}H^{φ} = 0 for every φ ∈ Π^{s}. Therefore LH^{φ} ≥ 0 for every φ ∈ Π^{s}. If LH^{φ} = 0, we say that φ is unimprovable; if LH_{n}^{φ} = 0, then φ is unimprovable of order n. The equation

(41)  LH = 0  H ∈ ℌ

is called the Blackwell optimality equation in the honor of Blackwell; the similar equation LH_{n} = 0 for H_{n} ∈ ℌ_{n} is the n-order optimality equation. Let H = {h_{n}} be the element of ℌ corresponding to the value function V_{β} (see (19)), and let H_{n} be the initial segments of H. We say that a stationary policy φ is conserving (or n-order conserving) if L^{φ}H = 0 (respectively, L^{φ}H_{n} = 0).

Theorem 8 A. The Blackwell optimality equation has a unique solution H^{∗} = max_{φ∈Π^{s}} H^{φ}.

A policy φ ∈ Π^{s} is Blackwell optimal iff H^{φ} = H^{∗}, and iff φ is a conserving policy. B. For every n ≥ −1, H_{n}^{∗} is uniquely determined by the equation LH_{n+1} = 0. A policy φ ∈ Π^{s} is n-discount optimal iff H_{n}^{φ} = H_{n}^{∗}, and is n-discount optimal if φ is (n + 1)-order conserving.

Proof. By Theorem 2 there exists a Blackwell optimal policy φ ∈ Π^{s}. Evidently, H^{φ} ⪰ H^{ψ}, ψ ∈ Π^{s} and φ is unimprovable, so that H^{φ} = H^{∗} := max_{ψ∈Π^{s}} H^{ψ}, and LH^{∗} = LH^{φ} = 0.

Since L^{φ}H^{φ} = 0, also L^{φ}H^{∗} = 0, and φ is conserving. In the part A it remains to prove that the solution of (41) is unique, and that a conserving stationary policy is Blackwell optimal. If ψ is conserving, then L^{ψ}H^{∗} = 0, hence L^{ψ}H^{φ} = 0 for a Blackwell optimal φ, therefore by Lemma 7 (applied to every n) H^{ψ} = H^{φ} = H^{∗}, so that ψ is Blackwell optimal too. Finally, suppose that H̃ is a solution to (41). By taking for each x ∈ 𝕏 a lexicographical maximizer a ∈ 𝔸_{x} of L^{a}H̃(x), we obtain a stationary policy ψ for which L^{ψ}H̃ = H̃. One may check (we omit the proof) that Lemma 7 is true for any H ∈ ℌ in place of H^{φ}, in particular, for H̃. It follows that H^{ψ} = H̃, and since LH^{ψ} = LH̃ = 0, the policy ψ is unimprovable. Hence ψ is Blackwell optimal, so that H̃ = H^{ψ} = H^{∗}.

The proof of part B is similar, with a reference to Lemma 7.

Policy improvement provides an algorithm to compute a Blackwell optimal policy in a finite CMP. Start with some φ ∈ Π^{s} and compute H_{m}^{φ} using formulas of Theorem 3 (here m is the number of states in 𝕏). Check the values of ℓ_{−1}^{a}h(x), (x, a) ∈ 𝕂. For a = φ(x) those values are zeros, and if ℓ^{a^{∗}}h_{−1}(x^{∗}) > 0 for some pair (x^{∗}, a^{∗}), then the policy

ψ(x) = \{ \begin{matrix}a^{∗} & if x = x^{∗}, \\ φ(x) & otherwise \end{matrix}

improves φ. If there are no such pairs (x^{∗}, a^{∗}), repeat the same procedure with ℓ^{a}h_{0} and the shrinked sets 𝔸_{0}(x) = {a ∈ 𝔸_{−1}(x), ℓ^{a}h_{−1}(x) = 0}, 𝕂_{0} = {(x, a) : a ∈ 𝔸_{0}(x), x ∈ 𝕏} (where 𝔸_{−1}(x) = 𝔸(x)). A policy ψ as above with ℓ^{a^{∗}}h_{0}(x^{∗}) > 0, (x^{∗}, a^{∗}) ∈ 𝕂 improves φ. If there are no such pairs (x^{∗}, a^{∗}), repeat the procedure with all subscripts increased by 1, etc., until either you get a better policy ψ, or reach the set 𝕂_{m}. In the latter case φ is (m − 1)-order discount optimal, and therefore Blackwell optimal by Theorem 5. Otherwise, proceed in the same way with the obtained policy ψ. Since the set Π^{s} is finite, this algorithm leads to a Blackwell optimal policy in a finite number of steps. In practice, one may improve φ simultaneously at several states x^{∗}.

On the other hand, the lexicographical policy improvement approach opens a new way to prove the existence of Blackwell optimal policies via a maximization of H^{φ} over all stationary policies φ and the related Blackwell optimality equation(41). The latter idea can be used in CMPs with an infinite state space 𝕏, in which the proof of Theorem 2, based on the fact that the set Π^{s} is finite, is inapplicable.

1.4. Extensions and generalizations. Veinott [39] introduced also the notion of naverage optimality in addition to the n-discount optimality. Let

v_{T}^{(1)}(x, π) = 𝔼_{x}^{π} [∑_{t=0}^{T −1} r(x_{t}, a_{t})]

and define recursively for n ≥ 1

v_{T}^{(n+1)}(x, π) = ∑_{t=1}^{T} v_{t}^{(n)}(x, π).

Then π^{∗} is n-average optimal if for every policy π

\underline{lim}_{T →∞} \frac{1}{T} [v_{T}^{(n+2)}(π^{∗}) − v_{T}^{(n+2)}(π)] ≥ 0.

Veinott[39],[40] and Sladky [34] showed that in a finite CMP a policy is n-discount optimal iff it is n-average optimal.

Chitashvili [6],[7],[51] extended results of Theorem 8 to more general models with a finite state space. In [6] he treated CMPs with arbitrary (indeed, compactified) action sets. He considered also what can be called (n, ϵ)-discount optimal policies; in their definition one should replace 0 by −ϵ in formula (23). In [7] he studied n-discount optimality in finite models with discount factors depending on the state x and action a: β(x, a) = c_{1}β + c_{2}β^{2} + ⋯ + c_{k}β^{k} where k and c_{i} are functions of (x, a). In this case the reward functions were of some specific average form. In [51] Theorem 8 is generalized to a finite model with two reward functions r(x, a) and c(x, a). More precisely,

v_{β}^{φ}(x) = 𝔼_{x}^{φ} [∑_{t=0}^{∞} β^{t}(r(x_{t}, a_{t}) + (1 − β)c(x_{t}, a_{t}))]

(in [51] Chitashvili considered only stationary policies). This expected discounted reward corresponds to an undiscounted reward

∑_{t=0}^{∞} r(x_{t}, a_{t}) + lim_{T →∞} \frac{1}{T} ∑_{t=0}^{T −1} c(x_{t}, a_{t}).

In that case all formulas related to Theorem 8 remain valid, with one exception: in equations (35) defining L^{a}, the term ℓh_{1} should be changed to

ℓh_{1}^{a}(x) = c(x, a) + P^{a}h_{1}(x) − h_{1}(x) − h_{0}(x)

(similar to the term ℓh_{0}).

As explained in the proof of Theorem 2, in finite CMPs the expected discounted reward v_{β}^{φ}(x) is a rational function of β. Hordijk e.a. [18] introduced a non-Archimedian ordered field of rational functions, used a simplex method in this field, and developed a linear programming method for the computation of β-optimal policies over the entire range (0,1) of the discount factor. In particular, their method allows to compute a Blackwell optimal policy. More precisely, for some m one may find numbers β_{0} := 0 < β_{1} < ⋯ < β_{m−1} < β_{m} := 1 and stationary policies φ_{1}, φ_{2}, …, φ_{m} such that φ_{j} is β-optimal for all β ∈ [β_{j−1}, β_{j}], 1 ≤ j ≤ m − 1, and φ_{m} is β-optimal in the interval [β_{m−1}, β_{m}) (which means that φ_{m} is Blackwell optimal).

In CMPs with constraints the controller wants to maximize expected (discounted) rewards while keeping other expected (discounted) costs in some given bounds. For such CMPs Altman e.a. [1] gave a constructive proof for the following (weaker) version of the result obtained in [18]. There exist numbers m and β_{j} as above such that for every j = 1, …, m either the constrained problem is not feasible in the open interval (β_{i−1}β_{j}) or the value function is a rational function of β in the closed interval [β_{j−1}, β_{j}], j ≤ m − 1 and [β_{m−1}, 1). Consequently, if the constrained problem is feasible in the neighborhood of β = 1, then v_{β} has a Laurent series expansion at β = 1.

As shown in the proof of Theorem 2, the limits of β-optimal policies, for β tending to 1, are Blackwell optimal. A counterexample in Hordijk and Spieksma [21] shows that in general this is not true in unichain CMPs with a finite state space and compact action sets. This disproves a conjecture in Cavazos-Cadena and Lasserre [4].

2. Denumerable state models

In this section we consider CMPs for which the state space 𝕏 is denumerable. There are many applications of controlled Markov chains for which it is natural to take an infinite number of states. An important class of models is that of open stochastic networks, used for the modelling of controlled communication systems.

Even in the case when the action space 𝔸 = {0, 1} consists of only two elements, but the state space 𝕏 is denumerable, the situation with Blackwell optimal policies is much more complicated than in finite models. It turns out that a Blackwell optimal policy may be not average optimal. A corresponding counterexample, based on the fact that the Cesaro lower limit of a sequence of numbers can be different from the Abel lower limit of the same sequence, was constructed by Flynn [52]. Also, there can be no Blackwell optimal policy not only in the sense of Definition 1, but also in the sense of a weaker Definition 12 given below, in which the interval (β_{0}, 1) may depend on the state x and the nonoptimal policy π. Maitra [53] presented such a counterexample, and in connection with it formulated this weaker definition.

The analysis of sensitive and Blackwell optimality for denumerable state models is mostly done under the following assumption.

Assumption 9 (a) Action sets 𝔸(x), x ∈ 𝕏, are compact metric sets.

(b) Transition probabilities p_{xy}(a) and rewards r(x, a) are continuous functions of a ∈ A(x) for all x, y ∈ 𝕏.

2.1. n-discount optimality The following Liapunov function condition introduced in Hordijk [17] implies, together with Assumption 9, the existence of a stationary n-discount optimal policy.

Assumption 10 There exist a state, say state 0, and nonnegative functions g_{0}, g_{1}, …, g_{n+1} on 𝕏 such that

(a) max_{a∈𝔸_{x}} |r(x, a)| ≤ g_{0}(x), x ∈ 𝕏,

(b) inf_{x∈𝕏} g_{0}(x) > 0,

g_{m}(x) + ∑_{y≠0} p_{xy}(a)g_{m+1}(y) ≤ g_{m+1}(x) for all a ∈ 𝔸, x ∈ 𝕏, m = 0, 1, …, n,

(c) P^{a}g_{n+1}(x) = ∑_{y∈𝕏} p_{xy}(a)g_{n+1}(y) is a continuous function of a ∈ 𝔸_{x}, x ∈ 𝕏.

It is easily seen that g_{m}(x) ≤ g_{m+1}(x), m = 0, 1, …, n, x ∈ 𝕏. Hence, by the dominated convergence theorem, it follows from (c) that P^{a}g_{m}(x) is a continuous function of a ∈ 𝔸_{x}, x ∈ 𝕏 also for m = 0, …, n.

In the case of a finite model, this assumption requires the accessibility of the state 0 under each stationary policy from each state. In the denumerable models it requires a strong version of recurrence to the state 0. More precisely, it assumes the finiteness under any policy of the n-th absolute moment of the total cost until the state 0 is reached, with immediate “cost” c(x, a) equal to |r(x, a)|∨1, (x, a) ∈ 𝕂. For simplicity, in [17] Assumption 10 is supposed to hold for all n. However, the proofs there remain true and provide sharper results if this assumption holds for a fixed n.

As shown in [17], Assumptions 9 and 10 imply for every φ ∈ Π^{s} a partial Laurent expansion of the form

(42)  v_{β}^{φ} = (1 + ρ) ∑_{k=−1}^{n} h_{k}^{φ}ρ^{k} + O(ρ^{n})

where O(ρ^{n}) is uniform in φ. Moreover, the coefficients h_{k}^{φ} are continuous in φ ∈ Π^{s} in the following topology. The space Π^{s} in the case of a denumerable 𝕏 is the Cartesian (direct) product ∏_{x∈𝕏} 𝔸(x), and we take in each 𝔸(x) the Borel topology of a metric space, and in

Π^{s} the product topology.

Using this continuity and the compactness of A(x), we can find for each x ∈ 𝕏 a lexicographically maximal element H_{n}^{∗}(x) = {h_{k}^{∗}(x), −1 ≤ k ≤ n} of H_{n}^{φ}(x) over all φ ∈ Π^{s}, and the corresponding maximizer φ_{x} (see Subsection 1.2 for the lexicographical ordering and notations). Clearly, then

\underline{lim}_{β↑1} ρ^{−(n−1)}[v_{β}(x, φ_{x}) − v_{β}(x, φ)] ≥ 0, x ∈ 𝕏

for any other φ ∈ Π^{s}, so that φ_{x} can be called (n − 1)-discount optimal in the class Π^{s} for the initial state x. However, in the proper n-dscount optimality the same policy should fit for all states x.

The following theorem derived in Hordijk [17] leads to this goal (in Hordijk and Sladky [20] it can be found with a different proof).

Theorem 11 Suppose Assumptions 9 and 10. Then there exist functions u_{−1}, u_{0}, …, u_{n} from 𝕏 to ℝ (u_{−1} is a constant) statisfying bounds

|u_{m}(x)| ≤ c_{m}g_{m}(x), m = 0, 1, …, n

for some constants c_{m}, and nonempty compact (in the product topology) sets

P_{−1} = Π^{s} ⊃ P_{0} ⊃ ⋯ ⊃ P_{n}

of stationary policies of the form P_{m} = ∏_{x∈𝕏} 𝔸_{m}(x) (𝔸_{−1}(x) = 𝔸(x)) with the following

property. Let U_{m} = {u_{−1}, …, u_{m}}. We have L^{φ}U_{m} ≤ 0 for every φ ∈ Π^{s} and m = −1, …, n, and φ ∈ P_{m} if and only if L^{φ}U_{m} = 0.

It is shown in [20] that φ ∈ P_{m+1} (m = −1, …, n − 1) if and only if φ is m-discount optimal in the class Π^{s} (this means that (23) holds for n = m for π^{∗} = φ and any π ∈ Π^{s}). If φ ∈ P_{m+1}, then the coefficients h_{k}^{φ}, −1 ≤ k ≤ m in (42) coincide with u_{k}, so that in Theorem 11 we have an analogue of the conserving property.

Also, we can conclude from the above results that the value function V_{β} has a partial Laurent expansion with the coefficients equal to the functions u_{m}. Hence

(43)  V_{β}(x) = (1 + ρ) [u_{−1}ρ^{−1} + u_{0}(x) + ∑_{k=1}^{m−1} u_{k}(x)ρ^{k}] + O(ρ^{m})  x ∈ 𝕏,

where u_{k} = h_{k}^{φ}, k = 1, …, m − 1 and φ ∈ P_{m+1}. For m = 1 this result is established in Cavazos-Cadena and Lasserre [4] under more restrictive recurrence conditions.

Hordijk and Sladky [20] also proved that m-discount optimality is equivalent to maverage optimality for m = 0, 1, …, n − 1 in denumerable CMPs satisfying Assumptions 9 and 10.

Let us now assume that Assumption 10 holds for all n ∈ ℕ. Then we have nonempty compact sets P_{n} for every n, and their intersection

P_{∞} = ⋂_{n=1}^{∞} P_{n}

is also a nonempty compact set in Π^{s}. A policy φ ∈ P_{∞} is n-discount optimal (in the class Π^{s}) for every n ∈ ℕ, and it is tempting to conjecture that φ is Blackwell optimal. However, in general this is not true. We return to this question in Section 2.2.

2.2. On Blackwell optimality in infinite state models. The original Blackwell definition (Definition 1) is too strong for the denumerable state CMPs, as we will see in the counterexample below. In the following definition it is weakened, and a policy satisfying Blackwell’s version is renamed into a strong Blackwell optimal policy. It is easy to see that in finite models both definitions coincide. Note that Veinott’s Definition 4 of n-discount optimality is stated in weak terms, applicable to general models.

Definition 12. For any set Π′ ⊂ Π a policy π^{∗} ∈ Π′ is said to be Blackwell optimal within the class Π′, if for every x ∈ 𝕏 and π ∈ Π there exists a number β_{0}(x, π) < 1 such that

v_{β}(x, π^{∗}) ≥ v_{β}(x, π) for all β ∈ (β_{0}(x, π), 1).

In the case Π′ = Π, π^{∗} is called Blackwell optimal.

Counterexample 13. The state space is

𝕏 = 𝕏_{0} ∪ 𝕏_{1} ∪ 𝕏_{2} ∪ ⋯

with

𝕏_{0} = {(0, 0)},
𝕏_{n} = {(n, 0), (n, 1, 1), …, (n, n, 1), (n, 1, 2), …, (n, n, 2)}.

The action sets are

\begin{matrix}A((0, 0)) = (0, 1, \frac{1}{2}, \frac{1}{3}, …\}, \\ A(n, 0)) = \{1, 2\}, A((n, i, j)) = \{1\} 1 ≤ i ≤ n, n ≥ 1 j = 1, 2. \end{matrix}

The transition probabilities are

p((1, 0)|(0, 0), \frac{1}{n}) = 1 − p((n, 0)|(0, 0), \frac{1}{n}) = 1 − 2^{−n}, n = 1, 2, …
p((1, 0)|(0, 0), 0) = 1,

and for n = 1, 2, … p((n, 1, 1)|(n, 0), 1) = p((n, 1, 2)|(n, 0), 2) = 1,

p((n, i + 1, 1)|(n, i, 1), 1) = p((n, i + 1, 2)|(n, i, 2), 1) = 1, 1 ≤ i ≤ n − 1,
p((n, 0)|(n, n, 1), 1) = p((n, 0)|(n, n, 2), 1) = 1.

The immediate rewards are

r((0, 0), a) = 1 ∀a ∈ A(0, 0),

and for n = 1, 2, …

r((n, 0), 2) = n, r((n, 0), 1) = 1,
r((n, i, 1), 1) = 1, r((n, i, 2), 1) = 0, 1 ≤ i ≤ n.

Note that this CMP satisfies assumption 9. Define φ_{k}, k = 1, 2, … as follows:

\begin{matrix}φ_{k}(0, 0) = \frac{1}{k} \\ φ_{1}(n, 0) = 1 and φ_{k}(n, 0) = 2 for k = 2, 3, …, n = 1, 2, 3, … \end{matrix}

It is easy to calculate that

v((n, 0), φ_{1}, β) = (1 − β)^{−1},

and

v((n, 0), φ_{k}, β) = n(1 − β^{n+1})^{−1} for n, k ≥ 2.

Hence

v((n, 0), φ_{1}, β) ≥ v((n, 0), φ_{k}, β)

if and only if β ≥ β_{n} with β_{n} being the unique solution of the equation 1+β +⋯+β^{n} = n in the interval 0 ≤ β ≤ 1. Since β_{n} is monotone increasing to 1 as n → ∞, there is no β_{0} < 1 such that for k ≥ 2,

v(x, φ_{1}, β) ≥ v(x, φ_{k}, β) for all β ∈ [β_{0}, 1) and all x ∈ 𝕏.

Hence φ_{1} is not a strongly Blackwell optimal policy. Clearly, for fixed initial state (n, 0), n ≥ 1 there is an β_{n} such that φ_{1} is discounted optimal for β ∈ [β_{n}, 1). This is not true for the state (0, 0). Indeed, for k ≥ 2

v((0, 0), φ_{1}, β) − v((0, 0), φ_{k}, β) =
β[(1 − β)^{−1} − (1 − 2^{−n})(1 − β)^{−1} − 2^{−n}n(1 − β^{n+1})^{−1}] =
β2^{−n}[(1 − β)^{−1} − n(1 − β^{n+1})^{−1}],

which is nonnegative if and only if β ≥ β_{k}. Thus φ_{1} is (weakly) Blackwell optimal in the class Π^{s}.

We next show that φ_{1} is Blackwell optimal in the class of randomized stationary policies, it is also optimal in the class of all policies. Since the set of states {(n, 0), (n, 1, 1), …, (n, n, 1), (n, 1, 2), …, (n, n, 2)} is a closed set under any policy, it follows from the results for finite models that φ_{1} is Blackwell optimal on this set in the class of all policies. This holds for all n ≥ 1. Hence it is sufficient to consider a policy φ which only randomizes in state (0, 0), say with probability p_{k} it takes action \frac{1}{k}. If φ takes action 1 in (n, 0) then v((n, 0), φ, β) = (1 − β)^{−1} = v((n, 0), φ_{1}, β), and for computing the difference between v((0, 0), φ_{1}, β) − v((0, 0), φ, β) we may as well set p_{n} = 0 in this case. So without loss of generality suppose φ(n, 0) = 2 if p_{n} > 0. Then

v((0, 0), φ, β) = 1 + β ∑_{k=2}^{∞} p_{k} (2^{−k} · \frac{k}{1 − β^{k+1}} + (1 − 2^{−k})\frac{1}{1 − β} )

= 1 + \frac{β}{1 − β} ∑_{k=2}^{∞} p_{k} (2^{−k} \frac{k}{1 + β + ⋯ + β^{k}} + (1 − 2^{−k})) .

On the other hand

v((0, 0), φ_{1}, β) = 1 + \frac{β}{1 − β} .

Hence,

\begin{aligned}f(β) := & \frac{1 − β}{β} (v((0, 0), φ_{1}, β) − v((0, 0), φ, β)) = \\ & ∑_{k=2}^{∞} p_{k} (2^{−k}(1 − \frac{k}{1 + β + ⋯ + β^{k}} )) . \end{aligned}

By dominated convergence

lim_{β↑1} f(β) = ∑_{k=2}^{∞} p_{k}2^{−k} · \frac{1}{k + 1}.

Consequently,

lim_{β↑1}(v((0, 0), φ_{1}, β) − v((0, 0), φ, β)) = \{ \begin{matrix}0 & if p_{k} = 0, k ≥ 2 \\ ∞ & otherwise, \end{matrix}

and φ_{1} dominates φ for β sufficiently close to 1. Hence φ_{1} is Blackwell optimal in the class of randomized stationary policies. With similar arguments it can be shown that it is Blackwell optimal in the class of all policies. However, φ_{1} is not a strong Blackwell optimal policy, since there does not exist a β_{0} < 1 such that v((n, 0), φ_{1}, β) = v((n, 0), β) for all n ≥ 1 and β_{0} < β < 1.

We now return to the question whether a policy φ ⊂ P_{∞} is Blackwell optimal (if Assumption 10 holds for all n). Take any policy ψ ∈ Π^{s} and initial state x ∈ 𝕏 and consider the infinite sequences H^{φ}(x) = {h_{k}^{φ}(x)} = {u_{k}(x)} and H^{ψ}(x) = {h_{k}^{ψ}(x)} (see (41) and Theorem 11). By this theorem, H_{m}^{φ}(x) ⪰ H_{m}^{ψ}(x) for every m ∈ ℕ, hence the same is true for the infinite sequences: H^{φ}(x) ⪰ H^{ψ}(x). Therefore either H^{φ}(x) = H^{ψ}(x), or there is an integer m such that

\begin{aligned}h_{k}^{φ}(x) & = h_{k}^{ψ}(x) for − 1 ≤ k ≤ m − 1, \\ h_{m}^{φ}(x) & > h_{m}^{ψ}(x). \end{aligned}

In the second case it follows from expansions (42) for φ and ψ with n = m + 1, that v_{β}^{φ}(x) > v_{β}^{ψ}(x) for all β in some interval (β_{0}(x, ψ), 1). The difficulty arises in the first case: there is no guarantee that v_{β}^{φ} and v_{β}^{ψ} have complete Laurent expansions of the form

v_{β}^{φ} = (1 + ρ) ∑_{−1}^{∞} h_{k}ρ^{k}. Indeed, they may not, as one may see from the following example.

Consider the one-server queue with a controllable Poisson arrival process as studied in Hordijk [17, Section 2.2]. It is shown there that Assumptions 9 and 10 are satisfied for a given n, if 𝔼 S^{n+1} < ∞, where S is the service time of one customer. Hence if 𝔼 S^{k} < ∞ for all k ∈ ℕ and the rewards r(x, a) are bounded by a polynomial in x, the set P_{∞} is nonempty. However, if the Laplace-Stieltjes transform of the service time

f(z) = ∫_{0}^{∞}e^{−zx}dF_{S}(x)

is not analytic at z = 0, then the complete Laurent expansion of discounted rewards does not exist for r(x, a) = 1{x = 0} and the Poisson arrival process with a positive parameter λ. Indeed, in this case we have a homogeneous random walk as described in Hordijk et al. [19, Section 2].

2.3. Operator theoretical approach to Blackwell optimality. A satisfactory theory of denumerable state model should contain as a special case the finite model. Assumption 10 is not suitable for this purpose. It presupposes a unichain CMP, while the theory of finite CMPs covers the multichain case too. So it is too restrictive. On the other hand, it does not guarantee the existence of complete Laurent expansions of discounted rewards under stationary policies, and henceforth is too weak to obtain the Blackwell optimality.

In Dekker and Hordijk [8] a theory of denumerable CMPs has been developed free of these inadequacies. The operator theoretical approach to Blackwell optimality is introduced there. In this approach a bounding function μ is used satisfying the condition μ(x) ≥ 1, x ∈ 𝕏. We relate with μ the Banach space V_{μ} of all real-valued functions f on 𝕏 with the finite μ-norm

∥f∥_{μ} = sup_{x∈𝕏} \frac{|f(x)|}{μ(x)}.

The associated operator norm is

∥T ∥_{μ} = sup_{f:∥f∥_{μ}≤1} ∥T f∥_{μ}

for any operator T : V_{μ} → V_{μ}. In the following “bounding assumption” the notations (1), (2), and also the notation

(44)  f̂(x) = sup_{a∈𝔸(x)} |f(x, a)|,  x ∈ 𝕏

for any function f on K, are used.

Assumption 14 For some constant C > 0

(a) ∥r̂∥_{μ} ≤ C,

(b) P^{a}μ(x) ≤ Cμ(x), (x, a) ∈ 𝕂.

In [8] the part (b) of the compactness-continuity Assumption 9 concerning the transition probabilities is strengthened to the following form.

Assumption 15 P^{a}f(x) is continuous in a ∈ 𝔸(x) for every f ∈ V_{μ} and x ∈ 𝕏.

Besides the bounding and compactness-continuity assumptions, we need also a condition to guarantee the Laurent series expansion for v_{β}^{φ}, φ ∈ Π^{s} (it should be pointed out that Assumption 10 implies Assumptions 14 and 15 with μ = const · g_{n}, but not the complete Laurent expansions). Dekker and Hordijk [8] introduced an ergodicity condition, renamed in Hordijk and Spieksma [22] into μ-geometric ergodicity in the case of a Markov chain, and into uniform μ-geometric ergodicity in the case of a CMP. Note that a CMP can be seen as a compact product set of Markov chains (see Hordijk [16]), and that therefore any ergodicity property of a CMP becomes a corresponding property of a Markov chain if CMP consists of a single chain. Since its introduction in [8], the μ-geometric ergodicity became also a new notion in the Markov processes literature, and has been intensively studied (see Meyn and Tweedie [29]). The uniform μ-geometric condition is

Assumption 16 For every φ ∈ Π^{s}, the t-th convolution P^{t}(φ) of the operator P (φ) converges to a limiting stochastic operator Q(φ) geometrically fast in the μ-norm, i.e. for some constants C < ∞ and γ < 1

(45)  ∥P^{t}(φ) − Q(φ∥_{μ} ≤ Cγ^{t},  φ ∈ Π^{s}, t ∈ ℕ.

Note that (45) requires the aperiodicity of all Markov chains with kernels P^{φ}. As shown in Hordijk and Yushkevich [24], the following weaker version of (45) suffices for the study of Blackwell optimality, which covers the case of periodic chains.

Assumption 16’ For some constants T, C < ∞ and γ < 1

(46)  ∥\frac{1}{T} ∑_{k=1}^{T} P^{k+t}(φ) − Q(φ)∥_{μ} ≤ Cγ^{t}, φ ∈ Π^{s}, t ∈ N.

Note that condition (46) (even with T independent of φ) is fulfilled in any finite CMP (because it is true for a finite Markov chain, and the number of Markov chains corresponding to stationary policies is finite). In a denumerable Markov chain, this condition implies the existence of the deviation operator analoguous to the deviation matrix considered in Section 1.1. The following lemma is indeed a general fact on operators in Banach spaces with a convergent resolvent. We state it in the context of the μ-norm and operators P (φ).

Lemma 17 Assumption 16’ implies the existence of the stationary operator Q(φ) = Q^{φ} and the deviation operator D(φ) = D^{φ} as defined in (6) and (7’) (the limits are understood in the μ-norm). Moreover, the equations in (6) for Q^{φ} and in (8)-(9) for D^{φ} are satisfied.

We have seen in Section 1.2 that in the case of a finite state space the resolvent

(47)  R_{β}(P) = R(ρ, P) = ∑_{t=0}^{∞} (\frac{P}{1 + ρ})^{t} = ∑_{t=0}^{∞}(βP)^{t} = (I − βP)^{−1}

of the transition operator P has a Laurent series expansion in the neighborhood of ρ = 0, reflected in formulas (13) and (16)-(18) together with v_{β}^{φ} = R_{β}(P^{φ})r^{φ}, implied by equations (6) and (8)-(9). The same expansion remains true in the case of a Markov chain on a general state space 𝕏, if there is a geometric convergence (46).

Lemma 18 If Assumption 16’ holds, then there exists a number ρ_{0} > 0 such that for all complex values of ρ in the ring 0 < |ρ| < ρ_{0}

(48)  R(ρ, P^{φ}) = (1 + ρ) [\frac{Q^{φ}}{ρ} + ∑_{n=0}^{∞}(−ρ)^{n}(D^{φ})^{n+1}] ,

where Q^{φ} and D^{φ} are the same bounded (in the μ-norm) operators as in Lemma 17.

Proof. Essentially, it is the same algebra based on equations (8)-(9) as in the proof of Theorem 3. However, there we knew beforehand that the resolvent has a simple pole at ρ = 0. To avoid this, one may check by direct algebra that the series (48) (which converges in some ring 0 < |ρ| < ρ_{0}, because the operator D^{φ} is bounded) defines an operator inverse to I − βP (see (47)). Indeed, we have according to (8)-(9) and (6) (and omitting the index φ)

\begin{matrix}(1 + ρ) & [\frac{Q}{ρ} + ∑_{0}^{∞}(−ρ^{n})(D)^{n+1}] (I − \frac{P}{1 + ρ}) = \\ = & [\frac{Q}{ρ} + ∑_{0}^{∞}(−ρ)^{n}D^{n+1}] [(I − P) + ρI] = \\ = & Q + ∑_{0}^{∞}(−ρ)^{n}D^{n+1}(I − P) + ∑_{0}^{∞}(−1)^{n}(ρD)^{n+1} = \\ = & Q + ∑_{0}^{∞}(−ρ)^{n}D^{n}(I − Q) − ∑_{1}^{∞}(−ρ)^{n}D^{n} = \\ = & Q + I − ∑_{0}^{∞}(−ρ)^{n}D^{n}Q = Q + I − Q = I, \end{matrix}

and the same holds if we multiply in the reverse order.

To proceed further, we need to extend the space ℌ and operators in it, introduced in Section 1.3, to the case of a countable state space 𝕏 and the Banach space V_{μ} of functions on 𝕏. Clearly, instead of sequences of Laurent coefficents we may consider the Laurent series themselves.

Definition 19 (a) The linear space ℌ_{μ} consists of all Laurent series of the form

h := h(x) = h(x, ρ) = ∑_{n=−1}^{∞} h_{n}(x)ρ^{n}, h_{n} ∈ V_{μ}, x ∈ 𝕏

in the complex variable ρ with coefficients satisfying the geometric growth condition

\overline{lim}_{n→∞} ∥h_{n}∥μ^{\frac{1}{n}} < ∞.

(b) For every ψ ∈ Π^{s}, operators L^{ψ} and U^{ψ} in the space ℌ_{μ} are given by the formulas

(49)  \begin{aligned}L^{ψ}h & = r^{ψ} + P^{ψ}h − (1 + ρ)h  h ∈ ℌ_{μ}, \\ U^{ψ} & = \frac{ρ}{1 + ρ}R(ρ, P^{ψ}). \end{aligned}

We use in ℌ_{μ} the lexicographical ordering defined in Section 1.2 for the sequences of their coefficients H = {h_{−1}, h_{0,...}}. Clearly, if H′ ⪯ H′′, or equivalently h′ ⪯ h′′, then h′(x, ρ) ⪯ h′′(x, ρ) for all positive sufficiently small ρ, etc. Note that the definition (49) of L^{ψ} is consistent with formulas (33)-(35).

Lemma 20 Suppose Assumption 16’. Then for every φ ∈ Π^{S} the formulas (16)-(18) of Theorem 3 are valid, with coefficients h_{n}^{φ} (or k_{n}^{φ}) ∈ V_{μ}. If Assumption 16 holds (or if T in Assumption 16’ is the same for all φ), then

\overline{lim}_{n→∞} [ sup_{φ∈Π^{s}} ∥h_{n}^{φ}∥]^{\frac{1}{n}} < ∞.

This lemma is a direct consequence of the formula v_{β}^{φ} = R(ρ, P^{φ})r^{φ} and Lemma 18. The

corresponding element of ℌ_{μ} we denote h^{φ} = ∑_{−1}^{∞} h_{n}^{φ}ρ^{n}, so that

v_{β}^{φ} = (1 + ρ)h^{φ}.

The following comparison lemma is an extension to denumerable models of a result derived by Veinott [39] for finite models.

Lemma 21 (Comparison lemma) Suppose Assumptions 9,14,15 and 16′. Then for every h ∈ ℌ_{μ} and ψ ∈ Π^{s} there exists ρ_{0} > 0 such that

h^{ψ} − h = \frac{1}{ρ}U^{ψ}L^{ψ}h, 0 < |ρ| < ρ_{0}.

Central in the analysis of [8] is the following lemma which is the key lemma in the operator theoretical approach.

Lemma 22 (Key lemma) Under assumptions of Lemma 21, for every ψ ∈ Π^{s} the operator U^{ψ} is a positive operator: if h ∈ ℌ_{μ}, h ⪰ 0 then U^{ψ}h ⪰ 0 (if h ⪯ 0 then U^{ψ}h ⪯ 0). Moreover, if h ⪰ 0 and h(x_{0}) ≻ 0 for some x_{0} ∈ 𝕏, then Uh(x_{0}) ≻ 0.

The key lemma together with the comparison lemma yield the lexicographical policy improvement approach for the denumerable models (cf. Lemma 7 for finite models). For the average criterion in finite models policy improvement was developed by Howard [26] and Blackwell [3] and for the sensitive criteria in those models by Veinott [39]. In their honor we call it Howard-Blackwell-Veinott policy improvement.

In finite models policy improvement is a constructive way to find a Blackwell optimal policy, as sketched in Section 1.3. In infinite state space models this algorithm is not sufficient, since the improvements may not terminate in a finite number of steps. Lemmas 21-22 provide also for finite models an approach to Blackwell optimality different from that of Blackwell and Veinott.

The following theorem gives several equivalent formulations of Blackwell optimality in the class Π^{s} of stationary policies. Its proof is rather a direct consequence of the comparison and key lemmas. We refer to formulas (39)-(41) and Theorem 8 for notations, terminology and a comparison with the case of a finite model.

Theorem 23 Suppose Assumptions 9,14,15 and 16’. Then the following statements concerning a policy φ ∈ Π^{s} are equivalent:

(a) φ is Blackwell optimal within the class Π^{s};

(b) h^{φ} ⪰ h^{ψ} for every ψ ∈ Π^{s};

(c) h^{φ} is a solution of the Blackwell optimality equation Lh = 0;

(d) L^{φ}h = 0 for a solution h of the equation Lh = 0 (i.e. φ is a conserving policy). Moreover, the solution of the equation Lh = 0 (if any) is unique.

It is shown in [8] that under continuity and uniform μ-geometric ergodicity assumptions, P^{φ}μ, Q^{φ}μ and D^{φ}μ are continuous functions of φ on the compact Π^{s} (in the product topology). This, together with the bounding assumption, implies the continuity in φ of the Laurent coefficients h_{n}^{φ}(x) given by formulas (17) and (18). This, together with a diagonal process on the countable set X, allows to get a maximizer h^{φ} = max_{ψ} h^{ψ}, ψ ∈ Π^{s} as in

part (b) of Theorem 23. By this theorem, φ is Blackwell optimal in the class Π^{s}, and the Blackwell optimality equation has a solution. A technical proof given in [8] shows that φ is Blackwell optimal also in the class Π of all policies (versions of this proof for Borel models can be found in [44], [50] and [25]). Thus, the following result holds.

Theorem 24 In a denumerable state space model satisfying Assumptions 9 and 14-16 there exists a Blackwell optimal policy.

A related question is whether a limit φ of β-optimal policies φ_{β} (if the limit exists as β ↑ 1) is Blackwell optimal. Under weaker assumptions than above, it is shown in Hordijk [17], that such φ is 0-discount optimal. Under another set of assumptions, which can be shown to be more restrictive than Hordijk’s conditions, the same result is obtained by Cavazos-Cadena and Lasserre [4]. On the other hand, Hordijk and Spieksma [21] have constructed an example in which the limiting policy φ is not 1-discount optimal, so a fortiori not Blackwell optimal.

Lasserre [28], starting from the ideas developed in [8], obtained the existence of a policy Blackwell optimal within Π^{s} (and hence, according to [8], in the class Π too) without the policy improvement, making use of more results in the spectral theory of bounded linear operators.

Yushkevich [47] has shown how one may get the existence of Blackwell optimal policies in denumerable models with periodic chains by perturbing them into aperiodic models. In this work, besides Assumption 9, the boundedness of the reward function r was assumed, as well as the following condition taken from Tijms [37]: there are a number ϵ > 0 and an integer T such that for every φ ∈ Π^{s} there exists a state y_{T} = y(φ) such that

∑_{t=1}^{T} ℙ_{x}^{φ}{x_{t} = y} ≥ ϵ, x ∈ X.

In fact, we get the most general results if we use Assumptions 16 (and 16’) in a nonuniform way; this is true for the above results except the continuity of Q(φ) and D(φ). So, for Theorem 23 the following weak versions of Assumptions 16 and 16’ are sufficient.

Assumption 16(w) For every φ ∈ Π^{s}, there exist constants C(φ) < ∞ and γ(φ) < 1 such that

∥P^{t}(φ) − Q(φ)∥_{μ} ≤ C(φ)γ^{t}(φ).

Assumption 16’(w) For every φ ∈ Π^{s}, there exist T (φ), C(φ) and γ(φ) < 1 such that

∥\frac{1}{T (φ)} ∑_{k=1}^{T (φ} P^{k+t}(φ) − Q(φ)∥_{μ} ≤ C(φ)γ^{t}(φ).

For continuity of Q(φ) and D(φ) in φ and therefore for Theorem 24 we need the uniform Assumption 16 (or 16’).

2.4. Recurrence conditions for Blackwell optimality. In [10] recurrence conditions are introduced which imply the existence of complete Laurent series and of Blackwell optimal policies. Starting in Ross [31], recurrence conditions have been extensively used and studied in undiscounted nonfinite CMPs.

The first analysis based on the notion of ‘simultaneous Doeblin condition’, can be found in Hordijk [16]. Many equivalent formulations of this condition have been derived. We refer to [16], Federgruen, Hordijk and Tijms [13], [14], Thomas [36], Hernández-Lerma, Montes-de-Oca, Cavazos-Cadena [15], Hordijk and Spieksma [22], Dekker, Hordijk and Spieksma [11]. We present here some of the results which appeared in the last of these papers.

The taboo transition matrix _{M}P with taboo set M ⊂ X is defined by

Mp_{xy} = \{ \begin{matrix}p_{xy} & y ∉ M \\ 0 & y ∈ M, \end{matrix}

with the convention that _{M}P^{t} is the t-fold matrix-product of _{M}P, and _{M}P^{0} = I, with I the identity-matrix. The uniform μ-geometric recurrence condition (in the weak form) is

Assumption 25 There is a finite set M and constants c < ∞ and γ < 1 such that

∥ _{M}P^{t}(φ)∥_{μ} < cγ^{t}, t = 0, 1, …, φ ∈ Π^{S}.

For the special case μ = e, where e the function with e(x) = 1 for all x ∈ X, uniform μ-geometric recurrence is equivalent to the simultaneous Doeblin condition (see Hordijk [17], Theorem 11.3 and especially relation (11.3.2)). The generalization from e to a general (mostly unbounded) bounding function μ is important. It gives not only results for unbounded reward functions (see the bounding Assumption 14), but also covers the class of CMP satisfying the uniform μ-geometric recurrence condition for a suitable chosen μ which is essentially larger than that of satisfying the simultaneous Doeblin condition. Indeed, let τ be the recurrence time to the set M, then

{τ > t} = {x_{k} ∉ M, 1 ≤ k ≤ t}.

Hence,

ℙ_{x}^{φ}{τ > t} = (_{M}P^{t}(φ)e) (x)

and under Assumption 25,

𝔼_{x}^{φ} τ = ∑_{t=0}^{∞} ℙ_{x}\{τ > t\} = ∑_{t=0}^{∞} (_{M}P^{t}(φ)e) (x) ≤ \frac{c}{1 − γ} · μ(x).

Consequently, if μ is bounded then the expected recurrence time is bounded in the starting state. Clearly, this does not hold for most queueing models. See Spieksma [35] for CMPs, especially controlled queues, which do satisfy the uniform μ-geometric recurrence condition.

Let ν(φ) denote the number of closed classes in the Markov chain with transition probabilities P (φ). A set B(φ) ⊂ X is called a set of ‘reference states’ if it contains precisely one state from each closed class and no other states.

An apparently stronger version of Assumption 25 is

Assumption 25’ There is a finite set M and constants c < ∞ and γ < 1 such that for every φ ∈ Π^{s} there exists a reference set B(φ) ⊂ M, and moreover

∥ _{B(φ)}P^{t}(φ)∥_{μ} < cγ^{t}, t = 0, 1, ….

In [11] it is shown that Assumption 25, together with the continuity of v(φ) as function of φ, is equivalent to Assumption 25’. Dekker and Hordijk [10] analyzed and proved the existence of Laurent expansions and Blackwell optimality under Assumption 25’.

It was Hordijk’s conjecture that (uniform) μ-geometric ergodicity is equivalent to (uniform) μ-geometric recurrence. This was proved in Hordijk and Spieksma [22] for one Markov chain and has been generalized for the unichain case to general Borel state space by Meyn and Tweedie [29]. For CMPs the equivalence is more complicated , it can be found in Dekker, Hordijk and Spieksma [11].

Note that for the finite model ν(φ) is automatically continuous since Π^{S} is a finite set. Moreover, in Assumption 25 we may take M = 𝕏; then _{M}P is the zero matrix. Therefore Assumption 25, and hence also Assumption 25’, are always fulfilled in finite models, also in the multichain case.

One might ask whether Assumption 25’ can be weakened. Using the existence and continuity of the Laurent expansion of the discounted rewards, one may show that for the operator theoretical approach of Dekker and Hordijk the Assumption 25’ is also necessary (see Lasserre [28], Spieksma [35]).

Let us conclude this section with pointing out the relation between the Assumptions 10 and 25.

First, Assumption 10 is more restrictive, since it assumes the existence of one state which is accessible from all other states under each policy, i.e. the unichain case, whereas Assumption 25 allows a finite number of closed sets. Let us assume the unichain case (note that in the unichain case ν(φ) ≡ 1 and so it is continuous), then Assumption 25 implies Assumption 25’ and with B(φ) = {0} we have

∥ _{0}P^{t}(φ)∥_{μ} < cγ^{t}, t = 0, 1, …

with c < ∞ and γ < 1. Define

μ̃ = sup_{φ} ∑_{t=0}^{∞} _{0}P^{t}(φ)μ.

Then,

μ +_{0} P (φ)μ̃ ≤ μ̃ ∀φ ∈ Π^{S}

and

0P (φ)μ̃ ≤ μ̃ − μ ≤ \{1 − \frac{1 − γ}{c} \} μ̃

and

(50)  μ̃ +_{0} P (φ)μ̃ ≤ μ̃.

with μ̃ = \frac{c}{1−γ} μ̃. Since μ ≤ μ̃ ≤ \frac{c}{1−γ} μ, Assumption 14 for μ implies the same assumption for μ̃. By using (50) recursively, it is easily seen that Assumption 10 is satisfied for

g_{n} = (\frac{c}{1 − γ} )^{n+1} μ̃.

Hence for the unichain case Assumption 25 implies Assumption 10.

With a slightly more involved argument one may show that Assumption 25 is equivalent to

(51)  s(φ) := ∑_{t=0}^{∞} _{M}P^{t}(φ)μ ≤ c_{1}μ,

for some constant c_{1} and all φ ∈ Π^{S}. Indeed (cf. [10]), (51) implies that

MP (φ)s(φ) = s(φ) − μ ≤ (1 − \frac{1}{c_{1}} ) s(φ).

Choose γ_{1} < 1 and let t_{0} be such that (1 − \frac{1}{c_{1}} )^{t_{0}} c_{1} < γ_{1}; then

MP^{t_{0}}(φ)μ ≤ _{M}P^{t_{0}}(φ)s(φ) ≤ (1 − \frac{1}{c_{1}} )^{t_{0}} s(φ) ≤ γ_{1}μ.

Let c_{1} = sup_{φ} _{M}P (φ)μ, c = (c_{1} ∨ 1)^{t_{0}}γ_{1}^{−1} and γ = γ_{1}^{1/t_{0}}. Then γ < 1, and for kt_{0} ≤ t <

(k + 1)t_{0}, k ≥ 0 we have

\begin{aligned}∥ _{M}P^{t}(φ)∥_{μ} & ≤ ∥ _{M}P^{kt_{0}}(φ)∥_{μ}∥ _{M}P^{t−kt_{0}}(φ)∥_{μ} \\ & ≤ γ_{1}^{k}c_{1}^{t−kt_{0}} ≤ cγ^{t}. \end{aligned}

Hence Assumption 25 is satisfied with c < ∞ and γ < 1.

Remark. The Laurent series expansion of the discounted rewards and the existence of strong Blackwell optimal policies for semi-Markov decision chains with a finite number of states and actions has been established in Denardo [12]. Similar results under related recurrence conditions have been obtained for the denumerable state model in Dekker and Hordijk [9].

3. Borel state models

In this section we consider Blackwell optimality in CMPs with a Borel state space. We formulate the existence results, describe distinctive features of the approach to Borel models, state recurrence conditions which imply less verifiable uniform ergodicity and integrability assumptions.

3.1. Existence of Blackwell optimal policies. The study of Blackwell optimality in Borelian models was started by Yushkevich [44,48] and continued by Hordijk and Yushkevich [24], [25]. An extended summary of results obtained in [48] can be found in [50]. A related paper is Yushkevich [49], where the compactness of the policy space is treated.

An advance in the direction of Borel models appeared possible in the case when the transition probabilities are given by transition densities. This is a common case in models with a continous state space. We also need the corresponding versions of the compactnesscontinuity Assumption 9 and either of the uniform geometric ergodicity Assumption 16 or of recurrence conditions implying Assumption 16. Models with a bounded reward function and a strong minorant or simultaneous Doeblin-Doob condition were treated in [48]; the particular case of finite action sets 𝔸(x) was studied before that in [44]. In models with unbounded rewards considered in [24][25], one needs a stronger version of the bounding Assumption 14, and the ergodicity or recurrence conditions should be stated in the terms of μ-norms; also a technical uniform integrability condition is needed in the absence of recurrence conditions.

To avoid repetitions, we first state the more general results obtained in [24][25]. Before stating the whole set of conditions, we introduce notations related to transition densities and randomized stationary policies; the formulas will become meaningful under subsequent assumptions. There is a reference measure m(dx) on the space 𝕏, and we often write dx instead of m(dx). The transition probabilities p(Y | x, a) are determined by transition densities p(x, a, y) so that (for measurable Y ⊂ 𝕏)

p(Y | x, a) = ∫_{Y} p(x, a, y)m(dy), (x, a) ∈ 𝕂.

Similar to (44), we denote (because the maximum exists)

p̂(x, y) = max_{a∈𝔸(x)} p(x, a, y), x, y ∈ 𝕏.

Formula (2) takes on the form

P^{a}f(x) = ∫_{𝕏} p(x, a, y)f(y)m(dy).

For uniformity with other notations of this section, we denote by σ(x, da) the probability measure σ(· | x) on 𝔸(x) ⊂ 𝔸 defined by a randomized stationary policy σ ∈ Π^{RS}. The transition density corresponding to σ ∈ Π^{RS} is

p^{σ}(x, y) = ∫_{𝔸} p(x, a, y)σ(x, da), x, y ∈ 𝕏,

the corresponding transition operator is P^{σ}:

P^{σ}f(x) = ∫_{𝕏} p^{σ}(x, y)f(y)m(dy).

Finally, we need multistep transition densities corresponding to a randomized Markov policy π = {σ_{1}, σ_{2}, …} ∈ Π^{RM} where σ_{t} ∈ Π^{RS}. They are defined recursively by the formulas

p_{1}^{π}(x, y) = p^{σ_{1}}(x, y), p_{t+1}^{π}(x, y) = ∫_{𝕏} p_{t}^{π}(x, z)p^{σ_{t+1}}(z, y)m(dz).

We also have a bounding function μ on X and the corresponding μ-norms (see Section 2.3). In the definition of the space V_{μ} it is understood that f ∈ V_{μ} is measurable (throughout this section measurability means Borel measurability).

Assumption 26(a) 𝕏 is a standard Borel space with a σ-finite measure m in it, 𝔸 is a Borel set in a Polish (= complete separable metric) space, the set 𝕂 (see (1)) is measureable in 𝕏 × 𝔸, transition densities p(x, a, y) ≥ 0 and rewards r(x, a) are measurable functions on 𝕂 × 𝕏 and 𝕂 respectively, μ(x) ≥ 1 is a measurable function on 𝕏.

(b) 𝔸(x), x ∈ 𝕏 are nonempty compact sets, functions p(x, a, y) and r(x, a) are continuous in a ∈ 𝔸(x) for every x, y ∈ 𝕏.

(c) ∥r̂∥_{μ} < ∞ (cf. (44)), and for some constant C > 0

∫_{𝕏} p̂(x, y)μ(y) ≤ Cμ(x), x ∈ 𝕏.

(d) Operators (P^{σ})^{t}, σ ∈ Π^{RS} converge in the μ-norm to limiting operators Q^{σ} geometrically fast and uniformly in σ as t → ∞: there exist positive constants C < ∞ and γ < 1 such that

∥(P^{σ})^{t} − Q^{σ}∥_{μ} ≤ Cγ^{t}, σ ∈ Π^{RS}, t = 0, 1, 2, …

The following result is proved in [24].

Theorem 27 If Assumption 26 holds, then there exists a stationary policy φ ∈ Π^{s} Blackwell optimal in the class Π^{RS} of randomized stationary policies. Also, all assertions of Theorem 23 hold (for policies φ, ψ ∈ Π^{S} or Π^{RS}).

Some partial results are true under milder assumptions. For example, Laurent series expansion of v_{β}(σ) for σ ∈ Π^{RS} and the analogue of Theorem 23 are valid under Assumption 16’(w) or 16(w), and also the Laurent series expansion of v_{β}(σ) is valid under an analogue of Assumption 16’ in place of Assumption 26(d). For Blackwell optimality in the class Π of all policies in general we need the following uniform integrability assumption.

Assumption 28 For every x ∈ 𝕏, randomized Markov policy π ∈ Π^{RM}, and ϵ > 0, there exist a set Y ⊂ 𝕏 with m(Y) < ∞ and a constant L > 0 such that

\begin{matrix}∫_{𝕏\Y} p_{t}^{π}(x, y)μ(y)m(dy) < ϵ,  t = 1, 2, 3, …, \\ p_{t}^{π}(x, y)μ(y) ≤ L,  y ∈ Y, t = 1, 2, 3, …. \end{matrix}

The following result is proved in [25].

Theorem 29 Under Assumptions 26 and 28, every policy φ ∈ Π^{s} Blackwell optimal in the class Π^{RS}, is Blackwell optimal in the class Π as well.

In the earlier work [48], results of Theorems 27 and 29 were obtained in the case of bounded transition densities p(x, a, y), bounded rewards r(x, a) (so that one may take μ ≡ 1), a finite measure m, and the following minorant condition: there exist a set Y with m(Y) > 0 and a number δ > 0 such that

p(x, a, y) ≥ δ, (x, a) ∈ 𝕂, y ∈ Y.

In that case Assumptions 26(c) and 28 hold trivially, while the geometric convergence as in 26(d) is shown to be true even for the densities p_{t}^{σ}(x, y). Of course, one has to suppose Assumptions 26(a,b) (with μ = 1).

In related papers [45], [46] Yushkevich proved a partial expansion

V_{β}(x) = (1 + ρ) (\frac{h_{−1}}{ρ} + h_{0}) + o(1)

(cf.(43)) for Borel models satisfying assumptions of the preceding paragraph.

3.2. Specific features of Borel models. In the study of Blackwell optimality in Borel state models there are several features which make it different from that of finite and denumerable CMPs. They are: (i) utilization of the class Π^{RS} instead of Π^{S} in the Laurent series expansions and related topics; (ii) introduction of the weak-strong topology in the space Π^{RS} based on Carathéodory functions, (iii) lexicographical maximization of expected discounted rewards not pointwise at every state but for some absolutely continuous initial distribution; (iv) utilization of the policy improvement to get Blackwell optimal policy φ ∈ Π^{s} from a maximizing policy σ ∈ Π^{RS}.

We have to work with the class Π^{RS} instead of Π^{S} because the latter is not a compact space in a reasonable sense. It should be clear from the following simple example. Let 𝕏 = [0, 1) and 𝔸 = 𝔸(x) = {1, 2}. For every m = 1, 2, … let the stationary policy φ_{m} be defined by the rule: if x ∈ [(k − 1)2^{−m}, k2^{−m}) then φ_{m}(x) = 1 for odd values of k and φ_{m}(x) = 2 for even values of k. Every φ_{m} ∈ Π^{s}, but the only reasonable limit of the sequence φ_{1}, φ_{2}, … is the randomized policy σ ∈ Π^{RS} with the distribution σ(1 | x) = σ(2 | x) = 1/2.

Under assumptions of Section 3.1, Laurent series expansions for v_{β}(σ) with h^{σ} ∈ ℌ_{μ} as in Lemma 20 are valid for σ ∈ Π^{RS}. Along the same way as in denumerable models, with only technical differences, one justifies the lexicographical policy improvement, and this leads to an analogue of Theorem 23, (a) to (d), but for policies σ in the whole space Π^{RS} ⊃ Π^{S}.

In denumerable models we used the product topology in the space Π^{S} defined in Section 2.1. The appropriate topology in Π^{RS} is the so-called weak-strong or ws-topology. In this topology σ_{m} → σ iff

lim_{m→∞} ∫_{𝕂} f(x, a)σ_{m}(x, da)m(dx) = ∫_{𝕂} f(x, a)σ(x, da)m(dx)

for all Carathéodory functions f (i.e. functions continuous in a, measurable in x) satisfying some bounding condition in terms of f̂(x) and measure m. In this topology, Π^{RS} is a compact space with all needed properties. In the deterministic control theory essentally the same fact was used by Warga [42] in connection with relaxed controls. In the nonstationary stochastic dynamic programming the related compactness of the set of all measures corresponding to a given initial distribution in the ws-topology was proved by Schäl [32],[33] and Balder [2]. Another proof, especially for the space Π^{RS}, is given in Yushkevich [49]. Compactness proved in the above references covers the case of a finite reference measure m. For the σ-finite measure m it is proved in [24].

Assumptions of Section 3.1 imply the continuity in σ ∈ Π^{RS} of the operators P^{σ} and Q^{σ}, and after that, through formulas for h_{n}^{σ} as in Theorem 3 and the power series in P^{σ} for (D^{σ})^{n} obtained from (7), the continuity of the coefficients h_{n}^{σ}(x). This implies the continuity of h_{n}^{σ}(ℓ) = ∫_{𝕏} h_{n}^{σ}(x)ℓ(x)m(dx) for any initial density ℓ. Taking a strictly positive

density ℓ on 𝕏, we lexicographically maximize h^{σ}(ℓ) = {h_{n}^{σ}(ℓ), n ≥ −1} over Π^{RS}, and get a “best” policy σ^{∗} for the initial distribution ℓ.

Lexicographical policy improvement applied to σ^{∗} at all states X where it is possible to improve, provides a policy φ ∈ Π^{s}. With the help of the already proven part of Theorem 23, it is now not difficult to show that φ is Blackwell optimal in the class Π^{RS}, and that the Blackwell optimality equation has a unique solution in ℌ_{μ}.

The proof that a policy Blackwell optimal in Π^{RS} is Blackwell optimal in the whole space Π is even more technical than in the denumerable case. It utilizes the main idea of the proof in [8], Assumption 28, and an additional property of the ws-topology; see [25], or for the special case of bounded rewards, [44] or [48].

3.3. Recurence conditions for Blackwell optimality. The uniform geometric μergodicity conditon and the uniform integrability condition (Assumptions 26(d) and 28) are difficult for a verification in CMPs with a noncompact state space and an unbounded reward function. In Hordijk and Yushkevich [25] simpler recurrence and drift conditions are given, which imply those assumptions. This approach is based on ideas developed in Hordijk and Spieksma [22] and Hordijk et al. [23], with an additional use of the weak-strong topology. Consider the following set of conditions.

Assumption 30 (a) (Uniform minorant condition)There exist sets D, Y ⊂ 𝕏 with m(D) > 0, m(Y) > 0 and a number δ > 0 such that

p(x, a, y) ≥ δ, x ∈ D, a ∈ 𝔸(x), y ∈ Y.

(b) (Uniform drift condition) There exist a set D ⊂ 𝕏 with m(D) > 0 and numbers b > 0, 0 < γ < 1 such that

sup_{x∈D} μ(x) < ∞

and

∫_{𝕏} p(x, a, y)μ(y)m(dy) ≤ γμ(x) + b1_{D}(x), (x, a) ∈ 𝕂.

(c) (Uniform accessibility condition) There exists a set D ⊂ 𝕏, and for every sublevel set

M_{c} = {x : μ(x) ≤ c}

there exist a number η > 0 and an integer N such that

∫_{D} P_{N}^{σ}(x, y)m(dy) ≥ η, x ∈ M_{c}, σ ∈ Π^{RS}.

(d) (Dominance integrability condition) There exist a set D ⊂ 𝕏 with m(D) > 0 and a measurable function ℓ ≥ 0 and 𝕏 such that

∫_{𝕏} ℓ(x)μ(x)m(dx) < ∞ and p̂(x, y) ≤ ℓ(y), x ∈ D, y ∈ 𝕏,

and also m(M_{c}) < ∞ for every sublevel set M_{c} with c ≥ 1.

Omitting some details, we summarize those relations between conditions which provide the existence of Blackwell optimal policies. It follows from [23], that Assumptions 30 (a,b,c) with the same set D, together with 26(a) and the condition P^{a}μ(x) ≤ Cμ(x) imply the uniform integrability Assumption 26(d). Also, if the density p(x, a, y) is bounded, Assumptions 30(b,d) together with 26(a,b,c) imply Assumption 28 (with a possible change of the function μ, which does not affect the made assumptions). The proof of the last result essentially follows the proof of a similar result for denumerable models in Dekker et al. [11], with the use of ws-topology. As a consequence, we have the following theorem.

Theorem 31 In CMP satisfying Assumptions 26(a,b,c) and 30(a,b,c), there exists a stationary policy φ ∈ Π^{s} Blackwell optimal in the class Π^{RS}, and all assertions of Theorem 23 hold.

If in addition the transition density p(x, a, y) is bounded and Assumption 30(d) holds, then φ is Blackwell optimal in the class Π as well.

Bibliography

[1] E. Altman, A. Hordijk and L.C.M. Kallenberg, “On the value function in constrained control of Markov chains”, Mathematical Methods of Operations Research 44, 387-399, 1996.

[2] E.I. Balder, “On compactness of the space of policies in stochastic dynamic programming”, Stochastic Processes and Applications 32, 141-150, 1989.

[3] D. Blackwell, “Discrete dynamic programming”, Annals of Mathematical Statistics 33, 719-726, 1962.

[4] R. Cavazos-Cadena and J.B. Lasserre, “Strong 1-optimal stationary policies in denumerable Markov decision processes”, Systems and Control Letters 11, 65-71, 1988.

[5] R. Cavazos-Cadena and J.B. Lasserre, “A direct approach to Blackwell optimality”, 1-16, Preprint, 1993.

[6] R.Ya. Chitashvili, “A controlled finite Markov chain with an arbitrary set of decisions”, Theory of Probability and Its Applications 20, 839-846, 1975.

[7] R.Ya. Chitashvili, “A finite controlled Markov chain with small termination probability”, Theory of Probability and Its Applications 21, 158-163, 1976.

[8] R. Dekker and A. Hordijk, “Average, sensitive and Blackwell optimal policies in denumerable Markov decision chains with unbounded rewards”, Mathematics of Operations Research 13, 395-421, 1988.

[9] R. Dekker and A. Hordijk. “Denumerable semi-Markov decision chains with small interest rates”, Annals of Operations Research 28, 185-212, 1991.

[10] R. Dekker and A. Hordijk, “Recurrence conditions for average and Blackwell optimality in denumerable state Markov decision chains”, Mathematics of Operations Research 17, 271-289, 1992.

[11] R. Dekker, A. Hordijk and F.M. Spieksma, “On the relation between recurrence and ergodicity properties in denumerable Markov decision chains”, Mathematics of Operations Research 19, 539-559, 1994.

[12] E.V. Denardo, “Markov renewal programming with small interest rates”, Annals of Mathematical Statistics 42, 477-496, 1971.

[13] A. Federgruen, A. Hordijk and H.C. Tijms, “A note on simultaneous recurrence conditions on a set of denumerable stochastic matrices”, Journal of Applied Probability 15, 842-847, 1978.

[14] A. Federgruen, A. Hordijk and H.C. Tijms, “Recurrence conditions in denumerable state Markov decision processes”, in Dynamic Programming and Its Applications, edited by M.L. Puterman, 3-22, Academic Press, 1978.

[15] O. Hernández-Lerma, R. Montes-de-Oca and R. Cavazos-Cadena, “Recurrence conditions for Markov decision processes with Borel state space: a survey”, Annals of Operations Research 28, 29-46, 1991.

[16] A. Hordijk, Dynamic Programming and Markov Potential Theory, Mathematical Centre Tract 51, Mathematisch Centrum, 1974.

[17] A. Hordijk, “Regenerative Markov decision models”, in Mathematical Programming Study, 6, edited by R.J.B. Wets, North Holland, 1976, 49-72.

[18] A. Hordijk, R. Dekker and L.C.M. Kallenberg, “Sensitivity-analysis in discounted Markovian decision problems”, Operations Research Spektrum 7, 143-151, 1985.

[19] A. Hordijk, O. Passchier and F.M. Spieksma, “On the existence of the Puisseux expansion of the discounted rewards: a counterexample”, Probability in the Engineering and Informational Sciences 13, 229-235, 1999.

[20] A. Hordijk and K. Sladký, “Sensitive optimality criteria in countable state dynamic programming”, Mathematics of Operations Research 2, 1-14, 1977.

[21] A. Hordijk and F.M. Spieksma, “Are limits of α-discounted optimal policies Blackwell optimal? A counterexample”, Systems and Control Letters, 13, 31-41, 1989.

[22] A. Hordijk and F.M. Spieksma, “On ergodicity and recurrence properties of a Markov chain with an application to an open Jackson network”, Advances in Applied Probability 24, 343-376, 1992.

[23] A. Hordijk, F.M. Spieksma and R.L. Tweedie, “Uniform stability conditions for general space Markov decision processes”, Technical report, Leiden University and Colorado State University, 1995.

[24] A. Hordijk and A.A. Yushkevich, “Blackwell optimality in the class of stationary policies in Markov decision chains with a Borel state space and unbounded rewards”, Mathematical Methods of Operations Research 49, 1-39, 1999.

[25] A. Hordijk and A.A. Yushkevich, “Blackwell optimality in the class of all policies in Markov decision chains with a Borel state space and unbounded rewards”, Mathematical Methods of Operations Research (to appear).

[26] R.A. Howard, Dynamic Programming and Markov Processes, Wiley, 1960.

[27] J.G. Kemeny and J.L. Snell, Finite Markov chains, Van Nostrand-Reinhold, 1960.

[28] J.B. Lasserre, “Conditions for existence of average and Blackwell optimal stationary policies in denumerable Markov decision processes”, Journal of Mathematical Analysis and Applications 136, 479-490, 1988.

[29] S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability, Springer, 1993.

[30] B.L. Miller and A.F. Veinott, “Discrete dynamic programming with a small interest rate”, Annals of Mathematical Statistics 40, 366-370, 1969.

[31] S.M. Ross, “Non-discounted denumerable Markovian decision models”, Annals of Mathematical Statistics 39, 412-423, 1968.

[32] M. Schäl, “On dynamic programming: Compactness of the space of policies”, Stochastic Processes and Applications 3, 345-354, 1975.

[33] M. Schäl, “On dynamic programming and statistical decision theory”, Annals of Statistics 7, 432-445, 1979.

[34] K. Sladký, “On the set of optimal controls for Markov chains with rewards”, Kybernetika (Prague) 10, 350-367, 1974.

[35] F.M. Spieksma, “Geometrically ergodic Markov chains and the optimal control of queues”, Ph.D. Thesis, University of Leiden, 1990.

[36] L.C. Thomas, “Connectedness conditions for denumerable state Markov decision processes”, in Recent Developments in Markov Decision Processes, edited by R. Hartley, L.C. Thomas, D.J. White, Academic Press, 1980, 181-204.

[37] H.C. Tijms , “Average reward optimality equation in Markov decision processes with a general state space”, in Probability, Statistics and Optimization: a Tribute to Peter Whittle, edited by F.P. Kelly, Wiley, 1994, 485-495.

[38] A.F. Veinott Jr., “On finding optimal policies in discrete dynamic programming with no discounting”, Annals of Mathematical Statistics 37, 1284-1294.

[39] A.F. Veinott Jr., “Discrete dynamic programming with sensitive optimality criteria”, Annals of Mathematical Statistics 40, 1635-1660.

[40] A.F. Veinott Jr., Dynamic Programming and Stochastic Control, Unpublished class notes.

[41] H.M. Wagner, “On optimality of pure strategies”, Management Science 6, 268-269, 1960.

[42] J. Warga, Optimal Control of Differential and Functional Equations, Academic Press, 1972.

[43] K. Yosida, Functional Analysis, Springer, 1980.

[44] A.A. Yushkevich, “Blackwell optimal policies in a Markov decision process with a Borel state space”, Mathematical Methods of Operations Research 40, 253-288, 1994.

[45] A.A. Yushkevich, “Strong 0-discount optimal policies in a Markov decision process with a Borel state space”, Mathematical Methods of Operations Research 42, 93-108, 1995.

[46] A.A. Yushkevich, “A note on asymptotics of discounted value function and strong 0-discount optimality”, Mathematical Methods of Operations Research 44, 223-231, 1996.

[47] A.A. Yushkevich, “Blackwell optimal policies in countable dynamic programming without aperiodicity assumptions”, in Statistics, Probability and Game Theory: Papers in Honor of David Blackwell, edited by T.S. Ferguson, L.S. Shapley and J.B. MacQueen, Institute of Mathematical Statistics, 1996, 401-407.

[48] A.A. Yushkevich, “Blackwell optimality in Markov decision processes with a Borel state space”, Proceedings of 36th IEEE Conference on Decision and Control 3, 2827-2830, 1997.

[49] A.A. Yushkevich, “The compactness of a policy space in dynamic programming via an extension theorem for Carathéodory functions”, Mathematics of Operations Research 22, 458-467, 1997.

[50] A.A. Yushkevich, “Blackwell optimality in Borelian continuous-in-action Markov decision processes”, SIAM Journal on Control and Optimization 35, 2157-2182, 1997.

[51] A.A. Yushkevich and R.Ya. Chitashvili, “Controlled random sequences and Markov chains”, Russian Mathematical Surveys 37, 239-274, 1982.

[52] J. Flynn, “Averaging vs. discounting in dynamic programming: a counterexample”, Annals of Statistics 2, 411-413, 1974.

[53] A. Maitra, “Dynamic programming for countable state systems”, Sankhya Ser. A 27, 241-248, 1965.