A chapter for

MARKOV DECISION PROCESSES Models, Methods, Directions, and Open Problems

written by

Eugene A. Feinberg

Department of Applied Mathematics and Statistics

SUNY at Stony Brook Stony Brook, 11794-3600, NY, USA

May 28, 2000

Chapter 1

Total reward criteria

ch:MC

Abstract

This chapter deals with total reward criteria. One-step rewards can be as positive as negative. We describe results on the existence of optimal and nearly optimal strategies and the results on the convergence of value iteration algorithms under the so-called General Convergence Condition. This condition requires that, for any initial state and for any policy, the sum of positive parts of reward converges to a finite number.

1.1 Introduction

s:TC-intro

This chapter deals with the total reward criterion. This criterion is natural for finite horizon problems and for infinite horizon problems in which the number of steps is not fixed but it is finite along most trajectories. The examples include discounted criteria, which can be interpreted as problems with geometrically distributed horizon, as well as other problems such as sequential statistical procedures, stopping, search, and optimal selection problems.

The analysis of finite horizon models is usually based on the analysis of optimality equations and optimality operators. The value function satisfies the optimality equation and a Markov policy at which these equations are achieved at each step is optimal. If optimality cannot be achieved, a Markov policy, which is (ε/N)-close to the optimal value, is ε-optimal for the Nhorizon problem.

For infinite horizon problems, we can distinguish two distinct approaches. The first approach deals with the analysis of optimality (also called, dynamic programming) equations and operators. The second approach studies probability distributions on the sets of trajectories. In fact, the most interesting results have been achieved by combining these two approaches.

As was observed in sixties, certain properties of optimality operators, namely contracting and motonicity properties, imply the existence of optimal or nearly optimal strategies within natural classes of strategies. These properties also imply the convergence of algorithms. In general, dynamic programming operators may not possess these properties. However, if the one-step reward function is uniformly bounded and the nonnegative discount factor is less then one, then the contracting property holds. If rewards are nonnegative (nonpositive) then the value iteration algorithm, applied to the zero terminal value, forms a monotone and therefore convergent sequence. The mentioned three models are called discounted, positive, and negative respectively.

The first comprehensive results were obtained for these three models. (Blackwell ^{\underline{bl65}} [7] Denardo ^{\underline{de67}} [17], Strauch ^{\underline{st66}} [53]) studied discounted models, (Blackwell^{\underline{bl67}} [8], Ornstein^{\underline{or}} [46], and Strauch^{\underline{st66}} [53]) studied positive models, and Strauch^{\underline{st66}} [53] studied negative models. The results differ significantly from one model to another. To illustrate these differences, let us consider the situation when the state space is countable and there are no additional assumptions such as compactness of action sets. For discounted and positive models, for each initial state the supremum of the expected total rewards over the class of all strategies is equal to the corresponding supremum over the class of all stationary policies; Blackwell ^{\underline{bl65, bl67}} [7, 8]. However, it is not true for negative models; Strauch ^{\underline{st66}} [53]. For discounted models, for any positive constant ε, there exist stationary ε-optimal policies. Such policies may not exist for positive models; Blackwell ^{\underline{bl67}} [8]. However, for positive models there exist stationary εV -optimal policies also called multiplicatively ε-optimal; Ornstein ^{\underline{or}} [46]. There are other significant differences between positive, negative, and discounted programming. The differences are so significant than for a long period of time it was even was not clear how to formulate unified results. As the result, all textbooks on dynamic programming and Markov decision processes, that deal with infinite-horizon models with total rewards, consider only positive, negative, and discounted models and deal with them separately; see e.g. Ross ^{\underline{ro83}} [49] and Puterman ^{\underline{pu}} [48].

In addition to positive, negative, and discounted models, problems with arbitrary reward functions and without discounting have been considered in the literature for a long period of time. It turned out that the most comprehensive results can be proved when so-called General Convergence Condition holds. This condition means that the positive part of the reward function satisfies the positive programming assumptions. Positive, negative, and discounted models are particular cases of models satisfying the General Convergence Condition.

Blackwell ^{\underline{bl62}} [6] and Krylov ^{\underline{kr65}} [41] proved the existence of stationary optimal policies for MDPs with finite state and action sets. Dubins and Savage ^{\underline{dusa}} [19] and Hordijk ^{\underline{ho}} [39] introduced sufficient (and almost necessary) conditions for optimality, so-called conserving and equalizing conditions. Derman and Strauch ^{\underline{dest}} [18], and Strauch ^{\underline{st66}} [53] proved that, for a given initial state, any policy can be substituted with an equivalent randomized Markov policy. Krylov ^{\underline{kr65}} [41] and Gikhman and Skorohod ^{\underline{gisk79}} [36] showed that nonrandomized strategies are as good as randomized strategies. Dynkin and Yushkevich ^{\underline{dyyu}} [20] proved that if someone randomizes between different strategies, the objective function cannot be improved. Feinberg ^{\underline{fe82, fe82a}} [21, 22] proved that, for a given initial state, (nonrandomized) Markov policies are as good as general ones; earlier van Hee ^{\underline{vh}} [62] showed that the supremum of the expected total rewards over the class of Markov policies is equal to the supremum over the class of all policies.

Seminal papers by Blackwell ^{\underline{bl65, bl67}} [7, 8] and Strauch ^{\underline{st66}} [53] dealt with models with Borel state and action spaces. Some of the following papers dealt just with countable state spaces. For some results, their extension from countable to uncountable models is a straightforward exercise. For other results, such extensions are either difficult or impossible. In addition, Blackwell and Strauch considered Borel-measurable strategies and discovered that εoptimal strategies may not exist but for any initial measure they exist almost everywhere. In order to establish the existence of everywhere ε-optimal policies, one should expand the set of policies to universally measurable or analytically measurable policies. Such extension was introduced by Blackwell, Freedman, and Orkin ^{\underline{blfror}} [10] and it was done in a systematic and comprehensive way in the book by Bersekas and Shreve ^{\underline{besh78}} [4]. In particular, this book expanded in a natural way almost all results on positive, negative and discounted programming in a way that ε-optimality was established instead of almost sure ε-optimality. The major exception was Ornstein’s theorem ^{\underline{or}} [46]. It was proved by Ornstein ^{\underline{or}} [46] for a countable state space; see also Hordijk ^{\underline{ho}} [39]. It’s extension to Borel models in the sense of almost sure multiplicative nearly-optimality was formulated by Blackwell ^{\underline{bl67}} [8] as an open question. Frid ^{\underline{fr70}} [34] solved this problem (Schäl and Sudderth ^{\underline{scsu}} [52] found a correctable gap in Frid’s proof). The natural conjecture is that under more general measurability assumptions, in the spirit of Bertsekas and Shreve ^{\underline{besh78}} [4], almost sure nearly-optimality can be replaced with nearly optimality everywhere in Ornstein’s theorem. Blackwell and Ramachandran ^{\underline{blra}} [11] constructed a counter-example to this conjecture.

For the General Convergence Condition, significantly deeper results are available for countable state models than for Borel state problems. First, three important particular results were discovered by van der Wal: (i) the supremum of the expected total rewards over all policies is equal to the supremum over stationary policies if the action sets are finite; ^{\underline{vdw81}} [58, Theorem 2.22] (this result was generalized by Schäl ^{\underline{sc83}} [51] to Borel state models with compact action sets); (ii) extension of Ornstein’s theorem to the case when some action sets are compact; ^{\underline{vdw84}} [60] (this results was generalized by van Dawen and Scäl ^{\underline{vdsh, vd86}} [57, 56]; (iii) existence of uniformly nearly-optimal Markov policies; \underline{vdw83} [59]. The survey by van der Wal and Wessels ^{\underline{vdwwe84}} [61] describes these and many preceding results.

Feinberg and Sonin ^{\underline{feso83}} [31] generalized Ornstein’s ^{\underline{or}} [46] theorem to models satisfying the General Convergence Condition. For the long period of time, it had not been clear even how to formulate such results. The first clue is that in the more general formulation the value function of the class of stationary strategies should be considered instead of the value function of the class of all strategies. The second clue is that in the definition of multiplicative ε-optimal policies function V should be replaced with an excessive majorant of a value function of the class of stationary policies. The proofs in Feinberg and Sonin ^{\underline{feso83}} [31] are non-trivial and differ from Ornstein’s ^{\underline{feso85}} [32] proofs. Feinberg and Sonin ^{\underline{feso85}} [32] extended these results to non-stationary policies and to more general classes of functions that approximate optimal values.

Feinbeg ^{\underline{fe87, fe87a}} [24, 25] described the structure of uniformly nearly-optimal policies in countable state models satisfying the General Convergence Condition. As mentioned above, stationary policies can be significantly outperformed by nonstationary policies in negative problems; see Example ^{\underline{ex6}} 3.6. It turned out that this example demonstrates the only pathological situation when the value of the class of stationary policies is less than the value of the class of all policies. Considers the set of states for which the value functions equal to zero and there are no conserving actions (an action at which the optimality operator applied to the value function achieves the maximum). Then there are policies which are uniformly nearly optimal and which are stationary outside of this set; see Theorems ^{\underline{t:prel}} 19 and ^{\underline{t:main2}} 20.

Another important feature of the papers by Feinberg and Sonin ^{\underline{feso85, fe87, fe87a}} [32, 24, 25] is that they consider general classes of nonstationary policies and general methods how to deals with nonstationary policies. In particular, the information about the past plays an important role. It is possible to identify two properties of this information: (i) non-repeating and (ii) transitivity conditions. Non-repeating condition implies that randomized policies are as good as non-randomized ones and there exist uniformly nearly optimal policies within any class of policies that satisfies this condition. Transitivity condition implies that the model can be transformed into a new model in a way that the class of strategies satisfying this condition in the old model becomes the class of stationary strategies in the new one.

This paper is a survey of results and methods for models satisfying the General Convergence Condition. We present the theory for countable models and discuss open questions, most of which deal with uncountable state spaces. In order to illustrate major concepts and counter-examples, we start our presentation with classical discounted, positive, and negative problems.

1.2 Definitions of discounted, positive, negative,

and general convergent models

s:MC-model

We say that an MDP is discounted if function r is bounded if there is a constant β ∈ [0, 1[, called the discount factor, such that

w(x, π) = 𝔼_{x}^{π} ∑_{t=0}^{∞} β^{t}r(x_{t}, a_{t}).  (1.1) Dis

An MDP is called unbounded discounted if (^{\underline{Dis}} 3.1) holds and the function r is bounded above, r(x, a) ≤ C < ∞ for all x ∈ 𝕏, a ∈ 𝔸(x) and for some C.

Discounted and unbounded discounted MDPs can be reduced to an MDP with a discount factor equal to 1. In order to do it, we add an additional state to the state space X. This state has only one action under which it is absorbent and all rewards are equal to zero in this state. This state sometimes is called a grave. The one-step transition probabilities between states in X become equal to βp_{xy}(a) and the transition probability from any state in X to the new absorbent states become (1 − β). The expected total rewards for all initial distributions on X in the new MDP are equal to the expected total discounted rewards for the same initial distribution in the original system. In the new MDP, the original constant β can be interpreted as the probability that the system remains alive at the next step if it is alive on the current step. This construction is well-known and it is described in details in Altman’s book ^{\underline{al99}} [2, Section 10.1]. Thus we can consider discounted MDPs as a special case of total reward MDPs with the discount factor equal to 1.

An MDP is called positive if r(x, a) ≥ 0 for all x ∈ X and a ∈ 𝔸(x) and w(x, π) < ∞ for all x ∈ X and for all π ∈ Π^{R}. An MDP is called negative if r(x, a) ≤ 0 for all x ∈ 𝕏 and for all a ∈ 𝔸(x).

We we indicate by D, UD, P, and N when we assume that the MDP is respectively discounted, unbounded discounted, positive, and negative. For an arbitrary MDP we define

w_{+}(x, π) = 𝔼_{x}^{π} ∑_{t=0}^{∞} r^{+}(x_{t}, a_{t}),  (1.2) PosCrit

w_{−}(x, π) = 𝔼_{x}^{π} ∑_{t=0}^{∞} r^{−}(x_{t}, a_{t}).  (1.3) NegCrit

Let

V_{+}(x) = sup_{ϕ∈Π^{R}} w_{+}(x, ϕ) V_{−}(x) = sup_{ϕ∈Π^{R}} w_{−}(x, ϕ)

It is well-known that V_{+}(x) = sup_{ϕ∈Π^{S}} w_{+}(x, ϕ); see Blackwell ^{\underline{bl67}} [8]. The following condition holds for D, UD, P, and N MDPs.

General Convergence Condition. V_{+}(x) < ∞ for all x ∈ 𝕏.

The General Convergence Condition is equivalent to the condition that w_{+}(x, π) < ∞ for all x ∈ 𝕏 and for all π ∈ Π^{R}; see van der Wal ^{\underline{vdw81}} [58, Theorem 2.3]. If the General Convergence Condition holds, w(x, π) = w_{+}(x, π) + w_{−}(x, π) for all initial states and for all policies. In this paper we always assume the General Convergence Condition. The value of w(x, π) does not change if we re-group summands r(x_{t}, a_{t}) or change the order of summation. We say that an MDP is General Convergent (GC) if the General Convergence Condition holds.

Let

s(x) = sup_{ϕ∈Π^{S}} w(x, ϕ)

be the value of the class of stationary policies.

1.3 Properties of strategic measures and objective

functions

s:SMOF

t:MC-Markov Theorem 1 (^{\underline{st66, dest, ho}} [53, 18, 39]) Let π^{1}, π^{2}, … be an arbitrary sequence of policies and λ_{1}, λ_{2}, … a sequence of nonnegative numbers summing to 1. Consider a randomized Markov policy π defined by

π_{t} (C | y) =^{def} \frac{∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (x_{t} = y, a_{t} ∈ C)}{∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (x_{t} = y)} , t ≥ 0, y ∈ 𝕏,  (1.4) e:eqrandM

whenever the denominator in (^{\underline{e:eqrandM}} 3.4) is not equal to 0. Then, for all t ≥ 0, y ∈ 𝕏 and Measurable subsets C of 𝔸(y),

ℙ_{x}^{π} (x_{t} = y, a_{t} ∈ C) = ∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (x_{t} = y, a_{t} ∈ C) .  (1.5) e:MC-MarkovP

Note that the randomized Markov policy defined in Theorem ^{\underline{t:MC-Markov}} 1 depends on the initial state. Our first observation related to Theorem ^{\underline{t:MC-Markov}} 1 is that setting λ_{1} = 1 and λ_{i} = 0, i > 1, we have that for any given policy and initial state, we can find a randomized Markov policy that produces the same one-dimensional distributions for the pair (x_{t}, a_{t}). Consequently, for any criterion depending only on such distributions Markov policies suffice. In particular, we have the following result.

c:randMv Corollary 2 Given an initial state x, for any policy σ consider a randomized Markov policy π defined in Theorem ^{\underline{t:MC-Markov}} 1 for π^{1} = σ and λ_{1} = 1. Then v(x, π) = v(x, σ).

Our second observation is that we can expand the notion of a policy by allowing the decision maker to select policies randomly at epoch 0. For example, we can say that a sequence γ = {(λ_{i}, π^{i})}_{i=1}^{∞}, where λ_{i} are nonnegative numbers with the sum equal to 1 and π^{i} are policies is a mixed strategy. Then any couple (γ, μ), where γ is a mixed strategy and μ is the initial probability distribution on 𝕏, define a strategic measure ℙ_{μ}^{γ} = ∑_{i=1}^{∞} λ_{i} ℙ_{μ}^{π^{i}} . Theorem ^{\underline{t:MC-Markov}} 1 shows that mixed policies do not outperform randomized Markov policies. Given a mixed policy γ, formula (6) in Section 1.3 in Dynkin and Yushkevich ^{\underline{dyyu}} [20] defines a usual randomized policy σ such that ℙ_{x}^{σ} = ℙ_{x}^{γ} . This is even a stronger argument that there is no need to deal with mixed policies.

Thus, Theorem ^{\underline{e:MC-MarkovP}} 3.5 implies that

V (x) = sup_{π∈Π^{RM}} v(x, π),  x ∈ 𝕏.  (1.6) e:optrm

Our next step is to show that nonrandomized Markov policies are as good randomized Markov ones. It follows from the fact that, for a given initial state or distribution, any strategic measure for a randomized Markov policies can be presented as a convex combination of strategic measures for nonrandomized Markov policies.

We recall that a Markov policy ϕ selects action ϕ_{n}(x) when the system is at state x on epoch n. Sometimes it is more convenient to write ϕ(x, n) instead ϕ_{n}(x). We shall use both these notations. We observe that the set of all Markov policies Π^{M} is the set of all functions from 𝕏 × ℕ to 𝔸 such that ϕ(x, n) ∈ 𝔸(x) for all x and n. For B ∈ A we denote by A(B) the σ-field on B which elements belong to A.

Now we introduce a measurable structure on Π^{M}. For each couple (x, n) and for each C ∈ A(𝔸(x)) we consider the cylinder Π_{x,n}^{NR}(C) = {ϕ ∈ Π^{NR} : ϕ(x, n) ∈ C}. Then we consider a σ-field of all cylinders with the base (x, n), F_{x,n} = {Π_{x,n}^{NR}(C) : C ∈ A(𝔸(x))}. For a set E ⊆ 𝕏 × ℕ we define the σ-fiels of cylindrical subsets F_{E} with the base at E, F_{E} = ∩_{(x,n)∈E}F_{(x,n)}. We denote F = F_{𝕏×ℕ}.

We observe that ϕ → ℙ_{x}^{ϕ}(C) is a measurable function on (Π^{M}, F) for any C ∈ H_{∞} and for any given initial state x. The main idea of the proof is that we interpret the problem in the following way. The decision-maker selects a Markov policy first and then uses this policy. The initial state is always x. So, we add the point ϕ before each trajectory. A trajectory x, a_{0}, x_{1}, a_{1} … transforms into ϕ, x, a_{0}, x_{1}, a_{1} . . .. The set of trajectories H_{∞} transforms the set H_{∞} into the set Π^{M}×H_{∞}. Transition probabilities from a_{n} to x_{n+1}, given the history ϕ, x_{0}, a_{0}, …, x_{n}, a_{n} are defined by p(dx_{n+1}|x_{n}, a_{n}), n = 0, 1, …. Transition probabilities from x_{n} to a_{n}, given the history ϕ, x_{0}, a_{0}, …, x_{n} are defined by I{ϕ(x_{n}, n) = a_{n}}, n = 0, 1, …. Since the measurability conditions from the Ionesco Tulcea ^{\underline{ne}} [47, Proposition V.1.1] theorem hold, we have that the mapping ϕ → ℙ_{x}^{ϕ}(C) is measurable on (Π^{M}, F) for any C ∈ H_{∞}. The arguments in this paragraph also imply that, for any fixed x ∈ X and C ∈ H_{n}, the function ℙ_{x}^{ϕ}(C) is F_{𝕏×{0,1,... ,n−1}}-measurable; see Lemmas 3.1 and 3.2 in Feinberg ^{\underline{fe87}} [24] for details.

Consider a randomized Markov policy π. We also will use sometimes the notation π(·|x, n) instead of π_{n}(·|x). Consider the measure m^{π} on (Π^{M}, F) defined as the product of measures π(·|x, n). This means that for any set of B(x, n) ∈ A(𝔸(x)), where x ∈ 𝕏 and n ∈ ℕ}, we have

m^{π}{ϕ ∈ Π^{M}| ϕ(x, n) ∈ B(x, n), (x, n) ∈ 𝕏×𝔸} = ∏_{(x,n)∈𝕏×ℕ}m^{π}(B(x, n)|x, n).

The measure m^{π} exists and unique for each Markov policy π. This follows from the general construction of product measures on products of measurable spaces; see e.g. Proposition V.1.2 in Neveu ^{\underline{ne}} [47]. The following theorem is a special case of Theorem 3.1 in Feinberg ^{\underline{ne}} [47].

t:MC-nonran Theorem 3 For any randomized Markov policy π and for any x ∈ 𝕏

ℙ_{x}^{π}(C) = ∫_{Π^{M}} ℙ_{x}^{ϕ}(C)m^{π}(dϕ),  C ∈ H_{∞}.  (1.7) e:intrep

Proof. If (^{\underline{e:intrep}} 3.7) holds for all C ∈ H_{n}, n ∈ ℕ, it holds for all C ∈ H_{∞} because measures P_{x}^{σ} can be continued from ∪_{n=0}^{∞}H_{n} to H_{∞}. Therefore, it is sufficient to prove (^{\underline{e:intrep}} 3.7) for C ∈ H_{n}, n ∈ ℕ. We shall do it by induction.

We have that P_{x}^{σ}{x_{0} = y} = I{x = y} for any y ∈ X and for any policy σ. This implies that (^{\underline{e:intrep}} 3.7) holds for all C ∈ H_{0}.

Let (^{\underline{e:intrep}} 3.7) holds for all C ∈ H_{n} for some n = 0, 1 …. We take an arbitrary C ∈ H_{n} and an arbitrary B ∈ A.

We observe that the function ℙ_{x}^{ϕ}(C′) is F_{𝕏×{0,1,... ,n−1}}-measurable for all C′ ∈ H_{n}. The mapping ϕ(y, n) is F_{𝕏×{n}}-measurable. Since (𝕏×{0, 1, …, n− 1}) ∩ (𝕏 × {n}) = ∅, the σ-fields F_{𝕏×{0,1,... ,n−1}} and F_{𝕏×{n}} are independent with respect to measure m^{π}. This implies that for any D = {x_{0}, a_{0} ∈ B_{0}, x_{1}, …, x_{n−1}, a_{n−1} ∈ B_{n−1}, x_{n}}

\begin{matrix}∫_{Π^{M}} I\{ϕ(x_{n}, n) ∈ B_{n}\}m^{π}(dϕ) ∫_{Π^{M}} ℙ_{x}^{ϕ}(D)m^{π}(dϕ) = \\ ∫_{Π^{M}} I\{ϕ(x_{n}, n) ∈ B_{n}\} ℙ_{x}^{ϕ}(D)m^{π}(dϕ) \end{matrix}  (1.8) e:indst1

for all n = 0, 1, … and for all x_{t} ∈ 𝕏, B_{t} ∈ A_{t}, t = 0, …, n.

We have that

\begin{matrix}ℙ_{x}^{π}\{C × B\} = ∫_{C} π(B|x_{n}, n) ℙ_{x}^{π}(dh_{n}) = \\ ∫_{C} ∫_{Π^{M}} I\{ϕ(x_{n}, n) ∈ B\}m^{π}(dϕ) ∫_{Π^{M}} ℙ_{x}^{ϕ}(dh_{n})m^{π}(dϕ) = \\ ∫_{C} ∫_{Π^{M}} I\{ϕ(x_{n}, n) ∈ B\} ℙ_{x}^{ϕ}\{dh_{n}\}m^{π}(dϕ) = ∫_{C} ℙ_{x}^{ϕ}(C × B)m^{π}(dϕ), \end{matrix} (1.9) e:indst2

where the first and the last equalities in (^{\underline{e:indst2}} 3.9) follow from the definition of measures P_{x}^{σ}, the second equality follows from the definition of the measure m^{π} and from the induction assumption, and the third equality in (^{\underline{e:indst2}} 3.9) follows from (^{\underline{e:indst1}} 3.8).

We have from (^{\underline{e:indst1}} 3.8) that (^{\underline{e:intrep}} 3.7) holds for any C ∈ H_{n} × A. Consider arbitrary C ∈ H_{n} × X and y ∈ 𝕏. We have

\begin{matrix}ℙ_{x}^{π}\{C × \{y\}\} = ∫_{C} p(y|x_{n}, a_{n}) ℙ_{x}^{π}(dh_{n}) = ∫_{C} p(y|x_{n}, a_{n}) ∫_{Π^{M}} ℙ_{x}^{ϕ}(dh_{n})m^{π}(dϕ) = \\ ∫_{Π^{M}} m^{π}(dϕ) ∫_{C} p(y|x_{n}, a_{n}) ℙ_{x}^{ϕ}(dh_{n}) = ∫_{Π^{M}} ℙ_{x}^{ϕ}(C × \{y\}\}m^{π}(dϕ), \end{matrix}

                                                          (1.10) e:indstep2

where the first and the last equalities in (^{\underline{e:indstep2}} 3.10) follow from the definition of measures P_{x}^{σ}, the second one follows from the validity of (^{\underline{e:intrep}} 3.7) for C ∈ H_{n}×A established in (^{\underline{e:indst2}} 3.9), and the third one follows from Fubini’s theorem.

The General Convergence Condition and Theorem ^{\underline{t:MC-nonran}} 2 yield the following result.

c:MC-nonran Corollary 4 For any randomized Markov policy π and for any initial state

x ∈ 𝕏

v(x, π) = ∫_{Π^{M}} v(x, ϕ)m^{π}(dϕ).

Corollaries ^{\underline{c:randMv}} 3.1 and ^{\underline{c:MC-nonran}} 3.2 imply the following statement.

c:nonrMv Corollary 5 Given an initial state x, for any policy σ there exists a Markov

policy ϕ such that

v(x, ϕ) ≥ v(x, σ).

The latter corollary yields the following result.

c:supM Corollary 6 v(x) = sup{v(x, ϕ| ϕ ∈ Π^{M}} for all x ∈ 𝕏.

A nonrandomized policy ϕ is called semi-Markov if ϕ(h_{n}) = ϕ(x_{0}, x_{n}) for all h_{n} = x_{0}, a_{0}, …, x_{n}, n = 1, 2, …. Since the state space 𝕏 is discrete, Corollary ^{\underline{c:supM}} 3.4 implies the following statement.

c:semi-Mar Corollary 7 For any positive function ε(x) on 𝕏 there exists a semi-Markov policy ϕ such that v(x, ϕ) ≥ V (x) − ε(x) for all x ∈ 𝕏.

t:OE Theorem 8 (Optimality Equation) V (x) = T V (x) for all x ∈ 𝕏.

Proof. For a Markov policy ϕ = {ϕ_{0}, ϕ_{1}, … } we define a shifted policy ϕ^{1} = {ϕ_{1}, ϕ_{2}, … }. Then v(x, ϕ) = T^{ϕ(x)}v(x, ϕ^{1}). We fix an arbitrary x ∈ 𝕏. The proof consists of two simple steps.

Step 1 (V (x) ≤ T V (x)). Consider an arbitrary constant ε > 0. According to Corollary ^{\underline{c:supM}} 3.4 there exists a Markov policy ϕ for which v(x, ϕ) ≥ V (x) − ε. We use obvious monotonicity properties of optimality operators and get V (x) − ε ≤ v(x, ϕ) = T^{ϕ(x)}v(x, ϕ^{1}) ≤ T v(x, ϕ^{1}) ≤ T V (x). Since ε > 0 is arbitrary, step 1 is proved.

Step 2 (V (x) ≥ T V (x)). Again, we consider an arbitrary positive constant ε. Corollary ^{\underline{c:semi-Mar}} 3.5 implies that for any ε > 0 there exists an ε-optimal semi-Markov policy ϕ. For any a ∈ 𝔸(x) we consider a nonrandomized policy σ[a, ϕ] such that

σ[a, ϕ](x_{0}, a_{0}, x_{1}, …, x_{n}) = \{ \begin{matrix}a, & if n = 0 and x_{0} = x; \\ ϕ_{0}(x_{1}), & if n = 1; \\ ϕ_{n−1}(x_{1}, x_{n}), & if n > 1. \end{matrix}

This policy uses action a at epoch 0 in the initial state x and than it switches to the semi-Markov policy ϕ with the initial state x_{1} and starting epoch t = 1. We have that

V (x) ≥ V (x, σ[a, ϕ]) = T^{a}v(x, ϕ) ≥ T^{a}(V − ε)(x) = T^{a}V (x) − ε.

and V (x) ≥ T^{a}V (x) − ε for all a ∈ 𝔸(x) and for all ε > 0. Step 2 is proved.

We recall that an action a ∈ 𝔸(x) is called conserving in state x if V (x) = T^{a}V (x). A policy that uses only conserving actions in all states is called conserving. Obviously, a stationary optimal policy is conserving. The following simple example shows that a conserving stationary policy may not be optimal. ex:cons Example 9 Let 𝕏 = 𝔸 = {0, 1}, 𝔸(0) = 𝔸, and 𝔸(1) = {0}. State 1 is

absorbing with one-step reward equal to 0. If action 0 is selected in state 0, the process remains in state 0 and the reward is not collected. Action 1 moves the process to state 1 and brings the one-step reward equal to 1. The formal definitions are p(x|x, 0) = p(1|0, 1) = 1, r(x, 0) = 0, and r(0, 1) = 1 where x ∈ 𝕏. In this example there are two stationary policies ϕ_{a}, a = 0, 1. Policy ϕ_{a} selects action a in state 0. Both ϕ_{0} and ϕ_{1} are conserving. However, V (0, ϕ_{0}) = 0 and V (0, ϕ_{1}) = 1.

A policy π is called equalizing at state x if lim sup_{n→∞} 𝔼_{x}^{π} V (x_{n}) ≤ 0. A policy is called equalizing if it is equalizing all all states x. It is easy to see that if a policy is conserving and equalizing then it is optimal. An optimal policy π is conserving and the limit of 𝔼_{x}^{π} V (x_{n}) exists and equal to 0 for all states x in which V (x) > −∞.

A natural question is when conserving policies exist. The Optimality Equation implies that a stationary conserving policy exists if and only if TV(x) is achieved for each x ∈ 𝕏 at some action a ∈ 𝔸(x).

Consider the following conditions that are essential for the existence of conserving policies.

• (i) A is a metric space and A is its Borel σ-field;

• (ii) 𝔸(x) is compact for some x ∈ 𝕏;

• (iii) p(y|x, a) are continuous in a and r(x, a) are upper semi-continuous in a.

l:max Lemma 10 If conditions (i-iii) hold for a given x ∈ 𝕏 and f is a bounded above function on 𝕏 then T^{a}f(x) = T f(x) for some a ∈ 𝔸(x).

See Lemma 4.2(i) in ^{\underline{fesh96}} [29] for the proof. In order to guarantee the existence of conserving strategies, we consider the following assumption.

Compactness Assumption Condition (i) holds and Conditions (ii) and (iii) hold for all x ∈ 𝕏.

Lemma ^{\underline{l:max}} 3.1 and the Optimality Equation imply the following statement.

c:conv Corollary 11 If the value function V (x) bounded above then the Compactness Assumption implies the existence of stationary conserving strategies.

In some applications, action sets are not compacts but can be approximated by compacts in a way that it is expensive to select actions outside of compact subsets. For example, in some inventory models, the size of the order may not be limited but large orders are expensive. To cover this situation, we consider the following condition.

• (iv) For any positive number N there exist a compact subset B_{N}(x) of 𝔸(x) such that r(x, a) ≤ −N for a ∈ 𝔸(x) \ B_{N}(x).

l:maxgen Lemma 12 If conditions (i – iv) hold for a given x ∈ 𝕏 and f is a bounded above function on 𝕏 then T^{a}f(x) = T f(x) for some a ∈ 𝔸(x).

Proof. If T f(x) = −∞ then T^{a}f(x) = T f(x) for all a ∈ 𝔸(x). Let T^{a^{∗}}f(x) > −∞ for some a^{∗} ∈ 𝔸(x). Let C ≥ f(z) for all z ∈ 𝕏. We set N = C − T^{a^{∗}}f(x) + 1. Lemma ^{\underline{l:max}} 3.1 applied to B_{N}(x) implies that T^{a′}f(x) = sup{T^{a}f(x) : a ∈ B_{N}(x)} for some a′ ∈ B_{N}(x). For any a ∈ 𝔸(x) \ B_{N}(x) we have that T^{a}f(x) ≤ C − N = T^{a^{∗}}f(x) − 1 < T f(x). Thus T^{a′}f(x) = T f(x).

Pre-Compactness Assumption Condition (i) holds and Conditions (iv) and (iii) hold for all x ∈ 𝕏.

The following statements strengthens Corollary ^{\underline{c:conv}} 3.6.

c:conv1 Corollary 13 If the value function V (x) bounded from above then the Pre-Compactness Assumption implies the existence of stationary conserving strategies. In particular, the Pre-Compactness Assumption implies the existence of stationary conserving policies for D, GD, and N MDPs.

ex2 Example 14 There are no conserving policies in positive MDPs satisfying

the Compactness Assumption.

Let 𝕏 = {0, 1, … } ∪ {g}, 𝔸 = 𝔸(0) = {1/2, 1/3, …, 0}, and 𝔸(x) = {0} for x ∈ 𝕏\{0}. We set p(g|x, 0) = 0 for x ∈ 𝕏, r(g, 0) = 0, and r(x, 0) = x−1 for x = 1, 2, …. We also set r(0, a) = 0 for all a ∈ 𝔸(x) and p(x|0, 1/x) = 1/x, p(g|0, 1/x) = (x−1)/x. We have that V (g) = 0, V (x) = x−1 for x ≥ 1, and T^{1/x}V (0) = 1 − 1/x. Since T^{0}V (0) = 0, there is no conserving action at state 0.

In view of Corollary ^{\underline{c:nonrMv}} 3.3, we consider the question if for any randomized Markov policy π there exists a Markov policy ϕ such that v(x, ϕ) ≥ v(x, π) for all x ∈ 𝕏. This natural question was asked in Dynkin and Yushkevich ^{\underline{dyyu}} [20, Section 4.7]. The following example illustrates that the answer to this question is negative even when π is randomized stationary. ex3 Example 15 (Feinberg and Sonin ^{\underline{feso81}} [30]) Let 𝕏 = \{(0, 0)\} ∪ \{(i, j)\}, i =

1, 2, …, j = −i + 1, …, 0}, A = {c, s}, where c stands for continue and s stands for stop. We also have that 𝔸(i, j) = {c} when j < 0, 𝔸(0, 0) = {s}, and 𝔸(i, 0) = {c, s} when i > 0. The state (0, 0) is a “grave.” This means that p((0, 0)|(0, 0), s) = 1 and r((0, 0), s) = 0. The system always moves with zero reward from a state (i, j) to (i, j + 1) when j < 0. In other words, p((i, j + 1)|(i, j), c) = 1 and r((i, j), c) = 0 when j < 0. For i > 0 we set p((i + 1, 0)|(i, 0), c) = p((0, 0)|(i, 0), s) = 1 and r((i, 0), c) = 2^{−(i+1)}, r((i, 0), s) = 1 − 2^{−(i+1)}.

We consider a randomized stationary policy π that selects actions c and c with equal probabilities, π(s|(i, 0), c) = π(s|(i, 0), s) = 0.5 for i > 0. Expected one-step rewards in states (i, 0) are equal to 0.5 when i > 0. If the initial state is (i, 0) with positive i, the income stream forms a geometric progression with the first term and ratio equal to 0.5. The sum of this progression is 1. From each state (i, j) with j < 0, the system moves to state (i, j + 1) with zero one-step rewards until it reaches state (i, 0). Therefore, v(x, π) = 1 for all x ∈ 𝕏 \ {(0, 0)}.

Consider a Markov policy ϕ. If ϕ((i, 0), i − 1) = c for all i ≥ 1 then v((1, 0), π) = 0.5 < v((1, 0), ϕ). Therefore, if v(x, ϕ) ≥ v(x, π) for all x ∈ 𝕏 then ϕ((i, 0), i−1) = s for some i ≥ 1. However, in this case v((i, −i+1), ϕ) = 1 − 2^{−(i+1)} < v((i, −i + 1), ϕ).

1.4 Non-homogeneous and finite-horizon models

s:NFM

Sometimes it is natural to consider models in which all parameters of the change over time. In this section, we consider models in which action sets, transition probabilities, and rewards depend also on time. For such models, called non-homogeneous, it is natural to expand the state space and consider the standard homogeneous model with the state space 𝕏̃ = 𝕏 × ℕ. By doing this, we can expand all previous notations and results to non-homogeneous models. The major distinction is that in the new model the states are couples (x, n) instead of x. For example, values functions are V (x, n).

A particular important example of non-homogeneous models is a finitehorizon model. For an n-horizon model, the state and action sets, reward and transition functions remain unchanged at epochs t = 0, 1, …, n − 1. At epoch n, the one-step reward is V_{0}(x), where V_{0} is a so-called final reward, and the system stops. The final reward is also known under several other names such as terminal reward or salvage value.

For each n-horizon model, it is natural to construct a non-homogeneous model, in which the model remains unchanged at steps 0, 1, …, n − 1. At step n the reward function is V_{0} and the system goes to a “grave” which is a state x with one available action under which this state is absorbent, i.e. p(x|x, a) = 1, and one-step rewards are equal to zero, r(x, a) = 0.

If the original MDP contains nonnegative rewards, V_{0} is a nonnegative function, and the expected total rewards are finite for any policy and any initial state then the corresponding homogeneous model is positive. If the original model is negative and V_{0} is a nonpositive function then the appropriate homogeneous model for an n-horizon model is negative. If the original model satisfies the General Convergence Condition with V_{0} considered as a reward at n-th epoch then the appropriate homogeneous model for an nhorizon model satisfies the General Convergent Condition. In particular, if the original model satisfies the General Convergent Condition and V_{0} = 0 then the homogeneous model, that corresponds to an n-horizon model, satisfies the General Convergent Condition too.

For n-horizon models, it is natural to use notations V_{i}(x, V_{0}) instead of V (x, n − i), i = 0, …, n. Then Theorem ^{\underline{t:OE}} 3 implies that

V_{n+1}(x, V_{0}) = T V_{n}(x, V_{0}),  x ∈ 𝕏.  (1.11) e:dp

Since any policy is equalizing, we obtain a dynamic programming algorithm for N-horizon problems: first solve iteratively (^{\underline{e:dp}} 3.11) for n = 0, 1, …, N − 1 with V_{0}(x, V_{0}) = V_{0}(x). Then for ε > 0 we define a Markov policy ϕ = (ϕ_{N}, phi_{N−1}, …, ϕ_{1}) by ϕ_{n+1}(x) = a where n = N − 1, N − 2, …, 0 x ∈ X, and a is an element of 𝔸(x) such that

T^{a}V_{n}(x, V_{0}) ≥ T V_{n}(x, V_{0}) − ε/N.

Any policy is equalizing in the new homogeneous model. It is easy to see that Markov policy ϕ is ε-optimal. In addition, if this policy can be defined as a conserving policy (ε = 0) then it is optimal. For example, if functions V_{0} and r are bounded above and the Pre-Compactness Assumption holds then a conserving policy can be defined; see Corollary ^{\underline{c:conv1}} 3.7.

For the important case V_{0} identical to 0, we write V_{n}(x) instead of V_{n}(x, V_{0}). An important question is whether the sequence V_{n}(x, V_{0}) converges. We denote V_{∞}(x, V_{0}) = lim_{n→∞} V_{n}(x, V_{0}) and V_{∞}(x) = V_{∞}(x, 0) when these limits, possibly infinite, exist. Sequential computation of V_{n} is called value iteration or successive approximation. When the limit V_{∞} exists, another important question is whether it equals V.

1.5 Particular models

s:SPMO

1.5.1 Discounted MDPs

We write the optimality operator T in the explicit form

T f(x) = sup{r(x, a) + βP^{a}f(x) : a ∈ 𝔸(x)}.

This operator is a contracting mapping of the set of bounded functions endowed with the norm ∥f∥ = sup_{x} f(x) into itself; see Denardo ^{\underline{de67}} [17] or Blackwell ^{\underline{bl65}} [7]. This implies that the optimality equation has a unique bounded solution and the limit V_{∞}(x, V_{0}) exists and is equal to this solution for any bounded V_{0}. Theorem ^{\underline{t:OE}} 3 implies that this solution is V.

t:disc Theorem 16 Blackwell ^{\underline{bl67}} [8], Denardo ^{\underline{de67}} [17]) Consider a D MDP. (i) For any ε > 0 there exists a ε-stationary optimal policy. (ii) If a stationary policy is conserving, it is optimal. (iii) If the Pre-Compactness Assumption holds then there exists a sta-

tionary optimal policy.

(iv) The limit V_{∞} exists and equals V.

We remark that (i) and (ii) follow from the equalizing property applied either to a stationary policy ϕ with T^{ϕ(x)}V (x) ≥ V (x) − (1 − β)ε for all x ∈ 𝕏 or to a stationary conserving policy; (iii) follows from Corollary ^{\underline{c:conv1}} 3.7, boundness of V (x), and (iv); and (iv) follows from the fixed point theorem for contracting mappings. We also remark that, as the following simple example shows, the Optimality Equation may have additional unbounded solutions.

ex4 Example 17 𝕏 = {0, 1, … } and 𝔸(x) = {a}. All rewards are equal to 0. If the system is in state i, it moves to state i + 1; p(i + 1|i, a) = 1. We have that V (x) = 0 for all x. However, any function u(i) = C/β^{i} satisfies the Optimality Equation u = T u.

1.5.2 Generalized Discounted MDPs

t:gdisc Theorem 18 Consider a GD MDP. (i) For any ε > 0 there exists a stationary ε-optimal policy. (ii) If a stationary policy is conserving, it is optimal. (iii) If the Compactness Assumption holds then there exists a stationary

optimal policy.

(iv) The limit V_{∞}(x) exists and V_{∞}(x) ≥ V (x) for all x ∈ 𝕏.

Proof. The proof of statements (i-iii) coincides with the proof of the corresponding statements in Theorem ^{\underline{t:disc}} 4. (iv) Let r(x, a) ≤ C for all x and a. If we subtract C from r then V (x, π) will be reduced by C/(1 − β) for all x and π. Therefore, we received an equivalent N MDP and the inequality follows from Theorem ^{\underline{t:negat}} 6(iv) .

ex5 Example 19 (V_{∞}(x) > V (x)) Let 𝕏 = {(0, 0)} ∪ {1, 2, … } × {0, 1, … }, 𝔸 = 𝔸(0, 0) = {a^{0}, a^{1}, … }, and 𝔸(x) = {a^{0}} when x ∈ 𝕏 \ {(0, 0)}. From any state (i, j) with i > 0, the system moves to (i + 1, j). This means that p((i+1, j)|(i, j), a^{0}) = 1 when i > 0. If action a^{j} is selected at state (0, 0), the system moves to (1, j). In other words, p((1, j)|(0, 0), a^{j})=1. The rewards are

r((i, j), a^{0}) = \{ \begin{matrix}−β^{−i}, & if i = j \\ 0, & otherwise. \end{matrix}

We have that V_{n}(0, 0) = 0 for n > 0 and therefore V_{∞}(0, 0) = 0. We also have that V (0, 0) = −1.

1.5.3 Negative MDPs

t:negat Theorem 20 (Strauch ^{\underline{st66}} [53])Consider an N MDP. (i) For any ε > 0 there exists a Markov ε-optimal policy. (ii) If a stationary policy is conserving, it is optimal. (iii) If the Pre-Compactness Assumption holds then there exists a sta-

tionary optimal policy.

(iv) The sequence V_{n}(x) is nonincreasing, the limit V_{∞}(x) exists, and V_{∞}(x) ≥ V (x) for all x ∈ 𝕏.

(v) The value function V is the maximum nonpositive solution of the Optimality Equation.

(vi) If either 𝕏 is finite or all sets 𝔸(x) are finite then V_{∞}(x) = V (x) for all x ∈ 𝕏.

In order to verify (i), one should consider a Markov policy ϕ = {ϕ_{1}, ϕ_{2}, …, } such that T^{ϕ_{n}(x)}v(x) ≥ v(x) − ε_{n} for all x ∈ 𝕏 and for all n ∈ ℕ, where ε_{0} + ε_{1} + … ≤ ε. Then the inequality v(x) ≤ 0 implies ε-optimality of ϕ. (ii) follows from the same reasons where ϕ is a stationary policy such that actions ϕ(x) are conserving at x. Since V (x) ≤ 0, the value function V is bounded above and Corollary ^{\underline{c:conv1}} 3.7 implies (iii). (iv) is correct because v(x, π) ≤ v(x, π, n + 1) ≤ v(x, π, n) for any policy π and therefore V (x) ≤ V_{n+1}(x) ≤ V_{n}(x). Statements (i), (ii), and (iii) hold for general convergent MDPs with V (x) ≤ 0 for all x ∈ X. The proof of these generalizations is the same as for N MDPs. It follows from the fact that any policy is equalizing. Statement (vi) was proved by Strauch ^{\underline{st66}} [53]. When β = 1, Example ^{\underline{ex5}} 3.5 demonstrates the possibility of V_{∞}(x) > V (x); see also Strauch ^{\underline{st66}} [53].

The following example demonstrates that stationary ε-optimal policies may not exist.

ex6 Example 21 𝕏 = {1, 2}, 𝔸 = 𝔸(1) = [0, 1), and 𝔸(2) = {0}. State 2 is absorbent with zero one-step rewards, p(2|2, 0) = 1 and r(2, 0) = 0. If action a is selected in state 1, p(1|1, a) = a, p(2|1, a) = 1 − a, and r(1, a) = (a − 1). Then w(1, ϕ) = −1 and V (1) = 0.

1.5.4 Positive MDPs

The notion of an ε-optimal policies has been defined for a constant ε. It is easy to extend it when a function f(x) is considered instead of constant ε. We say that a policy π is f-optimal for a given function f on 𝕏 if w(x, π) ≥ v(x) − f(x) for all x ∈ 𝕏.

t:negat1 Theorem 22 Consider a P MDP. (i) (Blackwell ^{\underline{bl67}} [8]) s(x) = V (x) for all x ∈ 𝕏. (ii) (Ornstein ^{\underline{or}} [46]) For any ε > 0 there exists a stationary εV -optimal

policy.

(iii) The sequence V_{n}(x) is nondecreasing and the limit V_{∞}(x) exists and V_{∞}(x) = V (x) for all x ∈ 𝕏.

(iv) The value function V is the minimum nonnegative solution of the Optimality Equation.

The first result was established by Blackwell ^{\underline{bl67}} [8]. Its proof consists of the following steps. First, we introduce a discount factor β ∈ [0, 1[. Then v(x, π, β) is non-decreasing in β and v(x, π, β) → v(x, π) as β → 1. We fix an arbitrary ε > 0. If ϕ is a stationary policy such that T^{ϕ(x)}v(x, β) ≥ v(x)− (1−β)ε for all x ∈ 𝕏 then v(x, π, β) ≥ v(x)−ε for all x ∈ 𝕏. This implies that for any positive β < 1 and for any policy π there exist a stationary policy ϕ such that v(x, ϕ, β) ≥ v(x, π, β) for all x ∈ 𝕏. Consider an ε-optimal policy π. We fix x ∈ 𝕏 and consider β such that v(x, π, β) ≥ v(x, π) − ε. We have that

s(x) ≥ v(x, ϕ, β) ≥ v(x, π, β) − ε ≥ v(x, π) − 2ε ≥ V (x) − 3ε.

Since ε > 0 is arbitrary, s(x) ≥ V (x). However, s(x) ≤ V (x). Thus, s(x) = V (x) for all x ∈ 𝕏.

The proof of (ii) is non-trivial and it was explained in greater details in Hordijk ^{\underline{ho}} [39]. Statements (ii) and (iii) are easy. Example ^{\underline{ex7}} 3.7 shows that conserving strategies may not be optimal. In addition it shows that the Compactness Assumption does not imply the existence of a stationary optimal policy even when the state space is finite.

ex7 Example 23 (Cavazos-Cadena, Feinberg, Montes-de-Oca ^{\underline{ccfemo}} [13]). Consider an MDP with state and action spaces given by 𝕏 = {0, 1} and 𝔸 = [0, 1], respectively. The sets of admissible actions are defined by 𝔸(1) = A = [0, 1], and 𝔸(0) = {0}, whereas the transition law and the reward function are determined by

p(0|0, 0) = 1, p(0|1, a) = a = 1 − p(1|1, a), a ∈ [0, 1],

and

r(0, 0) = 0, and r(1, a) = a(1 − a), a ∈ [0, 1].

From these definitions, it is clear that 0 is an absorbing state under every policy and that V (0) = 0. Also, stationary policies are naturally indexed by the action they prescribe at state 1: ϕ_{a} ∈ 𝔽 is given by

ϕ_{a}(1) = a, ϕ_{a}(0) = 0, a ∈ [0, 1].

The following statements are true for this example:

(a) the expected total-reward at state 1 under policy ϕ_{a} is given by v(1, ϕ_{a}) = 1 − a if a ∈ (0, 1], and v(1, ϕ_{a}) = 0 if a = 0;

(b) the optimal expected total-reward at state 1 is V (1) = 1;

(c) an optimal policy does not exist.

Indeed, (i) implies that s(1) = 1. Theorem ^{\underline{t:negat1}} 7(i) and (a) imply (c). From (a) and (b) we have that there is no stationary optimal policy. However, if an optimal policy exists in positive dynamic programming then a stationary optimal policy exists (Puterman 1994 , p. 324). Therefore, (a) and (b) yield (c).

Now we verify (a). Let a ∈ (0, 1] be fixed. Starting at state X_{0} = 1, under policy ϕ_{a} the system will arrive to state 0 at a random time T which is geometrically distributed with parameter a, that is, for each positive integer n, ℙ_{1}^{ϕ_{a}}{T = n} = a(1 − a)^{n−1} and a reward r(1, a) = a(1 − a) will be earned at each integer time t ∈ {0, 1, …, T − 1}. Since r(0, 0) = 0 and state 0 is absorbing, we have

V (1, ϕ_{a}) = 𝔼_{1}^{ϕ_{a}} [∑_{t=0}^{T −1} r(X_{t}, A_{t})] = r(1, a) 𝔼_{1}^{ϕ_{a}}[T]

= a(1 − a) × 𝔼_{1}^{ϕ_{a}}[T] = a(1 − a) × \frac{1}{a} = (1 − a).

Consider now a = 0. In this case, state 1 is absorbing under ϕ_{a} = ϕ_{0}, and a reward r(1, 0) = 0 is earned forever, so that V (1, ϕ_{0}) = 0.

Blackwell ^{\underline{bl67}} [8] constructed an example when there is no stationary εoptimal policy for a positive countable MDP with a finite state of actions. The following example, which is Example 2 in Feinberg and Sonin ^{\underline{feso81}} [30] shows that randomized Markov K-optimal policies may not exist for any K > 0; see also relevant Example 2.26 in van der Wal ^{\underline{vdw81}} [58].

ex8 Example 24 Let X = {(0, 0)} ∪ {(i, j) : i = 1, 2, …, j = −i + 1, …, 0, 1}, and 𝔸 = {c, s}. In states (0, 0) and (i, j), where i = 1, 2, …, and j < 0, the action sets, transition probabilities, and rewards are the same as in Example ^{\underline{ex3}} 3.3. We set 𝔸(i, 1) = \{c\} and p((0, 0)|(1, 1), c) = 1, p((i, 1)|(i + 1, 1), c) = 1, and r((i, 1), c) = 1, i = 1, 2, …. We also set 𝔸(i, 0) = 𝔸, p((0, 0)|(i, 0), c) = p((i+1, 0)|(i, 0), c) = 0.5, p((2^{i}−i^{2}+i−1, 1)|(i, 0), s) = 1, and r((i, 0), a) = 0, i = 1, 2, …, a ∈ 𝔸.

We denote g(i) = i^{2} − i + 1. The sequence g(i) is used in this example because of its three properties: (a) \frac{g(n+i)}{2^{i}} → 0 as i → ∞, (b) g(i) > 0 when i ≥ 1, and (c) ∑_{i=1}^{∞} \frac{1}{g(i)} < ∞.

Let i be a positive integer. If action s is selected in state (i, 0), the total future reward is 2^{i} − g(i). If action c is selected in this state, the system moves with fifty-fifty chances to the “grave” (0, 0) or to the state (i + 1, 0). Let ϕ be a Markov policy and m = min{n ≥ 0| ϕ_{n}(i + n) = s, i = 0, 1, … }. If m < ∞, we have that v((i, 0), ϕ) = 2^{−n}(2^{i+n} − g(i + n)). If m = ∞ then v((i, 0), ϕ) = 0. Therefore, v(i, 0) = 2^{i}. The optimality equation implies that v(i, j) = 2^{i} when j < 0.

Let ψ be a randomized Markov K-optimal policy for some constant K > 0. Since v((i, j), ψ) ≥ V (i, j)−K = 2^{i} −K, j ≤ 0, we have that π_{j}(s|(i, 0)) ≤ K/g(i), j = 0, 1, …, i − 1. Then

v((i, 0), ψ) = ∑_{t=0}^{∞} P {x_{t} = (i + t, 0), a_{t} = s}(2^{i+t} − g(i + t)) =

π_{0}(s|(i, 0))(2^{i} − g(i)) + ∑_{n=1}^{∞} π_{n}(s|(i + n, 0))(\frac{1}{2})^{n}×

[∏_{j=0}^{n−1}(1 − π_{j}(s|(s + j, 0)))](2^{n+i} − g(n + i)) ≤

2^{i} ∑_{n=0}^{∞} π_{n}(s|(i + n, 0)) < 2^{i}K ∑_{j=i}^{∞} \frac{1}{g(j)} = 2^{i} − 2^{i}(1 − K ∑_{j=i}^{∞} \frac{1}{g(j)}) < 2^{i} − K.

when i is large enough. The last inequality holds since

∑_{j=i}^{∞} \frac{1}{g(j)} → 0 as j → ∞. Thus ψ is not K-optimal and for any K > 0 there is no randomized Markov K-optimal policy.

Puterman ^{\underline{pu}} [48] describes a generalization of positive models called positive bounded models. For these models the assumption that the reward function r is nonnegative is replaced with a weaker assumption that for each x ∈ 𝕏 there is at least one a ∈ 𝔸(x) for which r(x, a) ≥ 0. As explained in Puterman ^{\underline{pu}} [48], these more general models inherits many properties of positive models. Our remark is that, though S = V for positive bounded models, stationary εV -optimal may not exist for them. The following example shows that randomized Markov εV -optimal policies may not exist in positive bounded MDPs.

ex9 Example 25 Consider Example ^{\underline{ex8}} 3.8. Let ṽ and Ṽ denote functions v and V in that example. If ψ is a randomized Markov policy such that ṽ((i, j), ψ) > Ṽ (i, j) − 1 for all i ≥ 1 and j < 0 then ṽ((i, 0), ψ) < Ṽ (i, 0) − 1 for large i. Using the same arguments as in the previous example but with slightly more complicated calculations, it is possible to show that ṽ((i, −1), ψ) < Ṽ (i, −1) − K for some i. We recall that Ṽ (i, j) = 2^{i}.

Now we slightly modify Example ^{\underline{ex8}} 3.8 by setting 𝔸(i, −1) = \{c, s\} with p((i, 0)|(i, −1), c) = 1, r((i, −1), c) = 1 − 2^{i} and p((0, 0)|(i, −1), s) = 1, r((i, −1), s) = 0. In other words, the decision maker can either pay 2^{i} − 1 and move to the state (i, 0) or collect zero return and stop the process. Since v(i, 0) = 2^{i}, the optimality equation implies that V (i, j) = 1 when j < 0. Fix ε > 0. Let ϕ be a randomized Markov policy and v((i, j), ϕ) ≥ 1 − ε when j < 0. Consider the model from the Example ^{\underline{ex8}} 3.8. For that model consider a randomized Markov policy ψ which coincides with ϕ at all states except (i, −1), i = 1, 2, …. Since in the MDP from Example ^{\underline{ex8}} 3.8 we have that 𝔸(i, −1) = {c}, policy ϕ always selects action c at states (i, −1). We observe that v((i, j), ϕ) ≤ ṽ((i, j), ψ) + 2^{i} − 1. Therefore, if v((i, j), ϕ) ≥ V (i, j) − εV (i, j) for all states (i, j) with j < 0 then ṽ((i, j), ψ) ≥ 2^{i} − ε for all states with j < 0. As explained in the previous paragraph, this is impossible.

1.6 The first main theorem: uniformly nearly-optimal

stationary policies

s:SP

Comparison of positive and negative MDPs creates a strong impression that these models are totally different; see the table on page 324 in Puterman ^{\underline{pu}} [48]. For example, for P MDPs s = V but it is not true for N MDPs. In addition, it is even not obvious how to define a unified notion of ε-optimality. The notion of εV -optimality, which is natural for P MDPs, is not applicable to N MDPs because policies cannot better than optimal. The notion of ε-optimality, which is natural for N MDPs, is not applicable to P models; see Example ^{\underline{ex8}} 3.8.

As the result, almost all books treat these models separately. The major exceptions are Hinderer ^{\underline{hi}} [38], Dynkin and Yushkevich ^{\underline{dyyu}} [20], and van der Wal ^{\underline{vdw81}} [58]. The first two books were written when very little was known about GC MDPs. Van der Wal ^{\underline{vdw81}} [58] introduced several new results including several counterexamples, the proof that s = V when all actions 𝔸(x) are finite, and interesting results on value iteration. The following result has been known for a long period of time.

t:FIN Theorem 26 (Blackwell^{\underline{bl62}} [6], Krylov^{\underline{kr65}} [41], Dynkin and Yushkevich^{\underline{dyyu}} [20], Kallenberg ^{\underline{ka}} [40]) If 𝕏 and A are finite then there exists a stationary optimal policy.

As Examples ^{\underline{ex6}} 3.6 and ^{\underline{ex8}} 3.8 demonstrate, if either 𝕏 or one of the sets 𝔸(x) is infinite then optimal policies may not exist. Van der Wal ^{\underline{vdw81}} [58] showed that if all states 𝔸(x) are finite then s(x) = V (x) for all x. Schäl ^{\underline{sc83}} [51] extended this result to Borel state problems with compact action sets.

For a long period time, there were no results available on the existence of stationary uniformly nearly-optimal policies in GC MDPs. Probably the first result was van der Wal’s ^{\underline{vdw84}} [60] theorem that states that stationary εV_{+}-optimal policies exist if for each x ∈ 𝕏_{≤} = {x ∈ 𝕏| V (x) ≤ 0} there exists a conserving action. This result generalizes Ornsten’s theorem (Theorem ^{\underline{t:negat1}} 7(ii)). The weak point of this statement is that the use of function V_{+} in the definition of ε-optimality does not look natural when reward functions can be negative. For example, if V (x) is always nonpositive and there is a conserving action in each state, such actions form a stationary optimal policy; this fact follows from the same arguments as Theorem ^{\underline{t:negat}} 6(ii). However, it is possible that V_{+}(x) is unbounded from above and van der Wal’s ^{\underline{vdw84}} [60] result implies the existence of stationary policies which are far from optimal. Van der Wal and Wessels ^{\underline{vdwwe84}} [61] asked whether V_{+} could be substituted with a better function.

Now we describe the result from Feinberg and Sonin ^{\underline{feso83}} [31] on the existence of uniformly nearly-optimal policies within the class of stationary policies for GC MDPs. This result implies Ornstein’s theorem and many other specific results. First, we define the sets

X_{S} = {x ∈ X| v(x, ϕ) = s(x) for some ϕ ∈ S};

X_{Π} = {x ∈ X| v(x, π) = V (x) for some π ∈ Π}.

For any x from X_{Π} there is a policy π which is optimal for this state. Similarly, for any x from X_{S} there is a stationary policy which is the best stationary policy for this state.

Let Φ be the class of numerical functions on 𝕏 such that P f^{+} < ∞. We observe that functions V, S, V_{+} belong to Φ. Constants also belong to Φ. For Z ⊆ 𝕏 and for any function f ∈ Φ, we denote by L(f, Z) the set of nonnegative functions ℓ on 𝕏 such that ℓ(x) > 0 and ℓ(x) ≥ max{f, P ℓ} when x ∈ 𝕏 \ Z. We also define L(f) = L(f, ∅).

We remark that L(f, Z) is the set of nonnegative functions which are positive excessive (or super-harmonic) majorants of f on 𝕏 \ Z. The sets L(f, Z) possess the following two properties: (i) if f(x) ≥ g(x) for all x ∈ 𝕏 \ Z then L(g, Z) ⊇ L(f, Z), and (ii) if Z ⊂ Y then L(f, Z) ⊇ L(f, Y). We also observe that if ℓ ∈ L(f, Z) then ℓ_{0} ∈ L(f, Z) where l_{0}(x) = l(x) for x ∈ 𝕏 \ Z and l_{0}(x) = 0 for x ∈ Z.

We observe that V_{+} + 1 ∈ L(V). Therefore, the set L(V, Z) ≠ ∅ for any Z. We also observe that V ∈ L(V, X_{S}) in P MDPs and V_{+} ∈ L(V, X_{S}) if for each x ∈ 𝕏_{≤} there exists a conserving action. Indeed, consider the set X^{∗} = {x ∈ X|V_{+}(x) = 0}. If an initial state belongs to X^{∗} the system will never leave X^{∗}. Therefore, we get a negative MDP if we restrict X to X^{∗}. Since there are conserving actions in all sets 𝔸(x) when x ∈ X_{≤} and X^{∗} ⊆ X_{≤}, there is a stationary optimal policy in the negative MDP with the state space X^{∗}. therefore, there is an optimal stationary policy for any initial point x ∈ X^{∗}. Thus, X^{∗} ⊆ X_{S}. And we have that V_{+} ∈ L(V_{+}, X^{∗}) ⊆ L(V, X_{S}).

t:main1 Theorem 27 (First main theorem: the existence of uniformly optimal stationary policies; Feinberg and Sonin ^{\underline{feso83}} [31], Theorem 2.1.) For any ε > 0 and for any ℓ ∈ L(s, X_{S}) there exists a stationary policy ϕ such that v(x, ϕ) ≥ s(x) − εℓ for all x ∈ 𝕏.

The proof of Theorem ^{\underline{t:main1}} 9 is not trivial and we do not consider it here. This theorem provides a unified way to prove the existence of uniformly εℓ-optimal policies: it is sufficient to prove that s(x) = V (x) for any given x and that ℓ ∈ L(s, X_{S}.) As we saw in Theorem ^{\underline{t:negat1}} 7, the proof that s(x) = V (x) is significantly easier that the direct proof that there are uniformly nearlyoptimal policies. For example, for P MDPs, we have s(x) = V (x) (Theorem \underline{t:negat1} 7(i)) and V ∈ L(V, X_{S}). Therefore, Theorem ^{\underline{t:main1}} 9 implies Ornstein’s theorem. If there is a conserving action for any x ∈ X_{≤} then s(x) = V (x); this and more general results follow from our main statement, Theorem ^{\underline{t:main2}} 20. Therefore, Theorem ^{\underline{t:main1}} 9 implies van der Wal’s ^{\underline{vdw84}} [60] described before its formulation. We also observe that if V is bounded above by a constant K then K ∈ L(V). Therefore, if S = V and V is bounded above then there exist stationary εoptimal policies. For example, Theorem ^{\underline{t:main1}} 9 implies the existence of stationary ε-optimal policy for positive bounded models from Puterman ^{\underline{pu}} [48]. Indeed, it is easy to see that in this model V (x) ≥ 0 for all x and if V (x) = 0 then there is a conserving action at x. Thus, s(x) = V (x) for all x in positive bounded models.

An important corollary from Theorem ^{\underline{t:main1}} 9 is that the value function s is the solution of the optimality equation.

t:oes Theorem 28 (Feinberg and Sonin ^{\underline{feso83}} [31, Theorem 2.2]) s(x) = T s(x) for all x ∈ 𝕏.

We remark that we do not know how to prove s = T s in GC MDPs without using Theorem ^{\underline{t:main1}} 9. It is easy to show that T s(x) ≥ s(x) for all x ∈ X. In order to prove s(x) ≥ T s(x) we need to use the existence of a stationary policy ϕ such that v(z, ϕ) ≥ s(z) − ε(z) for all z ∈ X and for some function ε(z). In the proof of V ≥ T V, we used Corollary ^{\underline{c:semi-Mar}} 3.5 for the similar result. After Theorem ^{\underline{t:main1}} 9 is established, the proof of s = T s is similar to the proof of V = T V; see Feinberg and Sonin ^{\underline{feso83}} [31] for details.

An important question is how to expand the class of functions L(s, X_{S}). One possible approach is to replace s in L(s, X_{S}) with a function d ≤ S. Our particular interest is to consider d defined in a way that it is possible that s is not bounded above but d is bounded above. Van Dawen and Schäl ^{\underline{vdsh}} [57], van Dawen ^{\underline{vd86}} [56], and Schäl and Sudderth ^{\underline{scsu}} [52] considered functions d of this type for particular models. These functions were related to the limiting behavior of s(x_{n}). For countable MDPs, the broadest known class of such functions was introduced in Feinberg and Sonin ^{\underline{feso85}} [32]. Let Q^{b} = ∪_{n=1}^{∞}\{τ < n\} be the set of all uniformly bounded stopping times. Let

d_{S}(x) = sup_{ϕS} inf_{τ∈Q^{b}} 𝔼_{x}^{ϕ} s(x_{τ}).

The following theorem generalizes Theorem ^{\underline{t:main1}} 9 in the sense that it describes a larger class of functions ℓ with respect to which ε-optimal policies exist.

t:main1m Theorem 29 (Feinberg and Sonin ^{\underline{feso85}} [32], Theorem 1.) For any ε > 0 and for any ℓ ∈ L(d, X_{S}) there exists a stationary policy ϕ such that v(x, ϕ) ≥ s(x) − εℓ for all x ∈ 𝕏.

We say that an MDP is deterministic if all transition probabilities p(y|x, a) are equal to 0 or 1. Bertsekas and Shreve ^{\underline{besh79}} [5] proved the existence of stationary ε-optimal policies in P MDPs.

Theorem 30 (Feinberg and Sonin ^{\underline{feso83}} [31, Section 5]) Consider a deterministic

t:main1d

MDP. Consider an arbitrary nonnegative function ℓ on 𝕏 such that ℓ(x) ≥ ℓ(y) for x, y ∈ 𝕏\X_{S} when there is an action a ∈ 𝔸(x) such that p(y|x, a) = 1. Then for any ε > 0 there exists a stationary policy ϕ such that v(x, ϕ) ≥ s(x) − εℓ(x) for all x ∈ 𝕏. In particular, in a P MDP for any ε > 0 there exists an ε min 1, V -optimal stationary policy.

We see that stationary εℓ-optimal policies exist in deterministic models for a broader class of functions ℓ. A natural direction of research is to expand the class L(d, X_{s}) in Theorem ^{\underline{t:main1m}} 11. An open question is to get results that unify deterministic and stochastic models; see Feinberg ^{\underline{fe86}} [23] for additional details. Function d is related to value functions in gambling problems; see Dubins and Savage ^{\underline{dusa}} [19] and Maitra and Sudderth ^{\underline{masu96}} [45]. However, the meaning of this relationship currently is not clear.

In conclusion, we illustrate how Theorems ^{\underline{t:main1}} 9 ^{\underline{t:main1m}} 11 can be used to prove the existence of uniformly nearly-optimal policies in particular models.

t:co Theorem 31 (cp. Cavazos-Cadena and Montes-de-Oca ^{\underline{ccmo}} [14]) Consider a negative MDP, all rewards r are nonpositive. Assume that if V (x) > −∞ for some x ∈ 𝕏 then

lim_{n→∞} inf_{ϕ∈S} 𝔼_{x}^{ϕ} v(x_{n}, ϕ) = 0.  (1.12) e:co

If this assumption holds then for any ε > 0 there exists a stationary ε-optimal policy.

Proof. In view of Theorem ^{\underline{t:main1}} 9, it is sufficient to prove that s(x) = V (x) for all x ∈ 𝕏. Since s(x) ≤ V (x) we have that s(x) = V (x) when V (x) = −∞. We observe that it is sufficiently to prove the theorem for the situation when V (x) > −∞ for all x ∈ 𝕏. Indeed, let Y = {x ∈ 𝕏| V (x) = −∞}. If Y = 𝕏 then the problem is trivial. So, we consider the case, Y ≠ 𝕏. In this case, we exclude the subset Y from 𝕏 and remove all actions a such that p(Y |x, a) > 0 from sets 𝔸(x) when x ∈ 𝕏 \ Y. We remark that 𝔸(x), X ∈ 𝕏 \ Y are still nonempty sets after this procedure because otherwise we would have V (x) = −∞. So, we have received a new model in which condition (^{\underline{e:co}} 3.12) holds for all x ∈ 𝕏.

So, it is sufficient to show that s(x) = V (x) for any x ∈ 𝕏 if (^{\underline{e:co}} 3.12) holds for all x ∈ 𝕏. In order to do it, we fix an arbitrary ε > 0 and an arbitrary x ∈ 𝕏. Then we select n ≥ 1 such that

inf_{ϕ∈S} 𝔼_{x}^{ϕ} v(x_{n}, ϕ) ≥ −ε.  (1.13) e:coone

We also select a stationary policy ϕ such that T^{ϕ(z)}V (z) ≥ V (z) − ε/n for all z ∈ 𝕏. We have that

(T^{ϕ})^{n}V (x) ≥ V (x) − ε.  (1.14) e:cotwo

We also have

s(x) ≥ v(x, ϕ) = T^{ϕ}v(x, ϕ) = (T^{ϕ})^{n}v(x, ϕ) = (T^{ϕ})^{n}(v(x, ϕ)−V (x)+V (x)) =

(T^{ϕ})^{n}V (x) + 𝔼_{x}^{ϕ} v(x_{n}, ϕ) − 𝔼_{x}^{ϕ} V (x_{n}) ≥ V (x) − 2ε.

The last inequality follows from (^{\underline{e:coone}} 3.13,^{\underline{e:cotwo}} 3.14) and V (x) ≤ 0. Since ε > 0 is arbitrary, s(x) ≥ V (x). Thus, s(x) = V (x).

We remark that s = V if s_{−} = V_{−} where the minus means that the function is related to the model in which r is replaced with r^{−}; see Theorem \underline{t:main2} 20. So, if the model, in which r is replaced with r^{−} satisfies conditions of Theorem ^{\underline{t:co}} 13 then for any ℓ ∈ L(d_{s}, X_{s}) and for any ε > 0 there exists a stationary εℓ-optimal policy. We also observe that X_{Π} = X_{s} if V = s.

t:fest Theorem 32 (Corollary 2 in Feinberg ^{\underline{fe86}} [23]) If for any x ∈ \{x ∈ 𝕏| V (x) > −∞} and for any π ∈ Π^{M}

lim sup_{n→∞} 𝔼_{x}^{π} s(x_{n}) ≥ 0

then for any ℓ ∈ L(d_{s}, 𝕏_{Π}) and for any ε > 0 there exists a stationary εℓ-optimal policy.

In conclusion, we remark that s(x) = s_{R}(x) for all x ∈ X where s_{R}(x) = sup_{π∈Π^{RS}} v(x, π) for all x ∈ X. This result was proved for the countable state MDPs by Feinberg and Sonin ^{\underline{feso85}} [32] and for Borel MDPs by Feinberg ^{\underline{fe92}} [27].

1.7 (f, I)-generated policies

s:NSP

Van der Wal ^{\underline{vdw83}} [59] proved that for any ε > 0 there exists a Markov εℓ-optimal policy with ℓ = V_{+} + 1. Theorems ^{\underline{t:main1}} 9 and ^{\underline{t:main1m}} 11 imply similar results for broader sets of functions ℓ. Indeed, let us replace the state space 𝕏 with the state space of couples (x, n) where x ∈ 𝕏 and n = 0, 1, …. The process moves from states (x, n) to (y, n + 1) with transition probabilities p(y|x, a). There is one-to-one correspondence between stationary policies in the new model and Markov policies in the original one. We also observe that if there exists a policy π such that v(x, π) = V (x) for some x ∈ 𝕏 then there is a Markov policy ϕ such that v(x, π) = V (x); see Corollary ^{\underline{c:nonrMv}} 3.3. These observations and Theorems ^{\underline{t:main1}} 9 imply the following result.

t:mare Theorem 33 (Feinberg and Sonin ^{\underline{feso85}} [32]) For any ε > 0 and for any ℓ ∈ L(V, X_{Π}) there exists a Markov εℓ-optimal policy.

We remark that if one uses Theorem ^{\underline{t:main1m}} 11 instead Theorem ^{\underline{t:main1}} 9 then a slightly more general class of function ℓ can be considered. We shall formulate it as a part of a more general statement. The natural question is which classes of strategies contain uniformly mearly-optimal policies. In order to answer this question, we consider the following construction.

Let I = {0, 1, … } and f : H → I. A policy π is called randomized (f, I)- generated if π_{n}(·|h_{n}) = σ(·|x_{n}, f(h_{n})) for some conditional distribution σ. We also consider nonrandomized (f, I)-generated policies. In the latter case, π_{n}(h_{n}) = σ(x_{n}, f(h_{n})) where σ is a mapping from 𝕏 × I to 𝔸. If we say that a policy is (f, I)-generated we mean that it is nonrandomized and (f, I)- generated.

Markov policies are an example of (f, I)-generated policies. In this case f(h_{n}) = n. Stationary policies form another example. In this case, f(h_{n}) = 0 for all h_{n}. Tracking strategies introduced by Hill ^{\underline{hi79}} [37] is the third example. For tracking policies, decision depends on the current state and the number of visits to it, i.e. f(h_{n}) = ∑_{i=0}^{n} I{x_{i} = x_{n}}. So, I is the information available about the past and f is a memory function which indicates what information about the past is remembered. We consider the following condition.

Transitivity Condition (Feinberg and Sonin ^{\underline{feso85}} [32]) If f(h_{n}) = f(h′_{m}) and x_{n} = x′_{m}, where h_{n} = x_{0}a_{0}x_{1} … x_{n} and h_{m} = x′_{0}a′_{0}x′_{1} … x′_{m}, then f(h_{n}az) = f(h′_{m}az) for all a ∈ 𝔸(x_{n}) and for all z ∈ 𝕏.

In other words, the current state x_{n}, the current information i_{n} = f(h_{n}), the next action a, and the next state z completely define i_{n+1} = f(h_{n}az). We observe that stationary and Markov policies satisfy the Transitivity Condition and tracking policies do not satisfy this condition. We denote by I^{f} the set of (f, I)-generated policies. We also denote by RI^{f} the set of randomized (f, I)-generated policies. We define

V^{f} = sup{v(x, π) : π ∈ I^{f}}, V_{R}^{f} = sup{v(x, π) : π ∈ RI^{f}}.

Let

d^{f}(x) = sup_{ϕ∈I^{f}} inf_{τ∈Q^{b}} 𝔼_{x}^{ϕ} V^{f}(x_{τ}).

Let also

𝕏^{f} = {x ∈ 𝕏|v(x, ϕ) = V^{f}(x) for some ϕ ∈ I^{f}}.

t:trans Theorem 34 (Feinberg and Sonin ^{\underline{feso85}} [32]) Let function f satisfies the transitivity condition. Then V^{f}(x) = V_{R}^{f}(x) for all x ∈ 𝕏 and for any ℓ ∈ L(d^{f}, 𝕏^{f}) and for any ε > 0 there exists an (f, I)-generated policy ϕ such that V (x, ϕ) ≥ V^{f}(x) − εℓ(x) for all x ∈ 𝕏.

The proof of Theorem ^{\underline{t:trans}} 16 is based on the following observation. Consider the MDP with the state space 𝕏×ℕ. If the transitivity condition holds then there is a one-to-one correspondence between (f, I)-policies and stationary policies in the new model where states are in fact couples (x_{n}, f(h_{n})). Then Theorem ^{\underline{t:trans}} 16 follows from s(x) = s_{R}(x) and from Theorem ^{\underline{t:main1m}} 11.

Markov and stationary policies are two examples of classes of policies satisfying the transitivity conditions. Another important example is socalled Y -policies introduced in Feinberg ^{\underline{fe87a}} [25]. For Y -policies, defined by a subset Y of 𝕏, decisions depend on the following factors: (i) the current state, (ii) the number of visits to Y, and (iii) the time passed after the last visit to Y. For any history h_{n} ∈ H_{n}, n = 0, 1, …, we define the number of visits to Y

m(h_{n}, Y) = ∑_{i=0}^{n} I{x_{i} ∈ Y }.

We also agree by that definition x_{−1} ∈ Y and let ξ(h_{n}, Y) is the epoch when the system visited Y for the last time,

ξ(h_{n}, Y) = max{i = −1, 0, 1, …, n| x_{n} ∈ Y }

and θ(h_{n}, Y) = n − ξ(h_{n}, Y) be the time passed after the last visit.

For Y -embedded policies we define I = {0, 1, … }×{0, 1, … } and f(h_{n}) = (m(h_{n}, Y), θ(h_{n}, Y)). We observe that if f(h_{n}) = (m, i) then f(h_{n}, a, z) = (m, i + 1)I{z ∉ Y } + (m + 1, 0)I{z ∈ Y } where I is an indicator function. Therefore, the Transitivity Condition holds and Theorem ^{\underline{t:trans}} 16 can be applied to Y -embedded policies. We also remark than in two extreme cases, Y = 𝕏 and Y = ∅, the set of Y -embedded policies coincides with the set of Markov policies.

Let τ^{1} be the first epoch when the system hits Y, τ^{1}(h) = min{n ≥ 0| x_{n} ∈ Y } and let τ^{m} be the (m + 1)-hitting epoch for Y : τ^{m} = min{n > τ^{m}| x_{n} ∈ Y }. We observe that {τ^{m}(h) = n} = {(m(h_{n}, Y) = m, θ(h_{n}, Y) = 0. The following theorem is a direct generalization of Theorem ^{\underline{t:MC-Markov}} 1 to Y - embedded policies. It was proved by induction in Feinberg ^{\underline{fe87}} [24] when λ_{1} = 1 and λ_{i} = 0 for i > 1. However, in the case of arbitrary λ_{i}, the proof remains the same.

t:embed Theorem 35 (Theorem 4.1 in ^{\underline{fe87}} [24]) Let π^{1}, π^{2}, … be an arbitrary sequence of policies and λ_{1}, λ_{2}, … a sequence of nonnegative numbers summing to 1. For an arbitrary Y ⊆ X consider a randomized Y -embedded policy π defined by

π (C | y, m, k) =^{def} \frac{∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (x_{τ^{m}+k} = y, τ^{m+1} > τ^{m} + k, a_{τ^{m}+k} ∈ C)}{∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (τ^{m} + k = y, τ^{m+1} > τ^{m} + k)} ,

                                                          (1.15) e:eqrandE

whenever the denominator in (^{\underline{e:eqrandE}} 3.15) is not equal to 0, where C ∈ 𝔸, y ∈ 𝕏, m = 1, 2, …, and k = 0, 1, …. Then, for all m, k = 0, 1, …, y ∈ 𝕏 and measurable subsets C of 𝔸(y),

\begin{matrix}ℙ_{x}^{π} (x_{τ^{m}+k} = y, τ^{m+1} > τ^{m} + k, a_{τ^{m}+k} ∈ C) = \\ ∑_{i=1}^{∞} λ_{i} ℙ_{x}^{π^{i}} (x_{τ^{m}+k} = x, τ^{m+1} > τ^{m} + k, a_{τ^{m}+k} ∈ C) , \end{matrix}  (1.16) e:MC-embed

and therefore

v(x, π) = ∑_{i=1}^{∞} λ_{i}v(x, π^{i}).  (1.17)

Theorem ^{\underline{t:embed}} 17 provides an important result in the following direction. Let Δ be some class of randomized policies. Then there is an explicit formula such that indicates a policy π ∈ Δ for a given initial state x and for an arbitrary policy π such that v(x, σ) = v(x, π).

The results in this direction were provided for stationary policies by Krylov^{\underline{kr85, kr87}} [42, 43] for discounted controlled diffusion processes and by Borkar^{\underline{bo88}} [12] for discounted MDPs. Altman ^{\underline{al96}} [1] proved the same result for MDPs with uniformly bounded life times. Discounted MDPs are a particular case of such models. In this case, the occupation measure for the original policy is equal to the occupation measure for the corresponding randomized stationary policy. For a more general case when the expected number to each state is bounded above, Altman ^{\underline{al96}} [1] proved a weaker result that the occupation measure for the corresponding randomized stationary policy majorizes the original occupation measure. Feinberg and Sonin ^{\underline{feso96}} [33] constructed an example when the strong inequality takes place.

We remark that our Theorem ^{\underline{t:embed}} 17 has no limitation on the life time of the system. In is a direct generalization of Theorem ^{\underline{t:MC-Markov}} 1 which follows from Theorem ^{\underline{t:embed}} 17 when Y = 𝕏 aor Y = ∅. Unfortunately, its relationship of Theorem ^{\underline{t:embed}} 17 with the results on the existence of equivalent randomized stationary policies is unknown; see Borkar’s paper in this volume.

In addition to the Transitivity Condition, the so-called Non-Repeating Condition for (f, I)-policies plays an important role.

Non-Repeating Condition (Feinberg ^{\underline{fe87}} [24]) If history h_{m} = x_{0}a_{0} … x_{m} is a continuation of history h_{n} = x_{0}a_{0} … x_{n}, i.e. h_{m} = h_{n}a_{n} … x_{m}, then (x_{n}, f(h_{n})) ≠ (x_{m}, f(h_{m})).

In other words, if the Non-Repeating Condition means that if m > n, h_{m} = h_{n}a_{n}x_{n+1} … x_{m}, and x_{n} = x_{m} then f(h_{m}) ≠ f(h_{n}). Markov, tracking, and Y -embedded policies are examples of (f, I)-generated policies that satisfy the Non-Repeating Condition. Stationary policies do not satisfy this condition.

Any randomized (f, I)-generated policy π is defined by transition probabilities π(·|x, i). Any nonrandomized (f, I)-generated policy σ is defined by a function σ(x, i). Let I^{f} be the set of all functions ϕ on 𝕏 × I with values on 𝔸 and such ϕ(x, i) ∈ 𝔸(x) for all x ∈ X. Any randomized (f, I)- generated policy π defines a measure m^{π} on the set I^{f} defined as the product of the countable set of independent measures π(·|x, i) over the set 𝕏 × I; see Neveu ^{\underline{ne}} [47, Proposition VI.2] for the existence and uniqueness of such products. t:nonrep Theorem 36 (Feinberg ^{\underline{fe87}} [24], Theorem 3.1) If the function f satisfies the

Non-Repeating Condition then for any C ∈ F_{∞} and for any randomized (f, I)-generated policy π

ℙ_{x}^{π}(C) = ∫_{I^{f}} ℙ_{x}^{ϕ}(C)m^{π}(dϕ)  (1.18) e:nonrep

and therefore v(x, π) = ∫_{I^{f}} v(x, ϕ)m(dϕ).

c:nonrep Corollary 37 If π is a randomized (f, I)-generated policy, f satisfies the Non-Repeating Condition, and x is any fixed element of 𝕏 then v(x, ϕ) ≥ v(x, π) for some (f, I)-generated policy ϕ.

Thus, we have three groups of results that can help us to prove the existence of uniformly εℓ-optimal policies in some class of nonrandomized policies. First, Theorems ^{\underline{t:MC-Markov}} 1, ^{\underline{t:embed}} 17, and relevant results for stationary policies related to occupation measures (see Krylov ^{\underline{kr85, kr87}} [42, 43], Borkar ^{\underline{bo88}} [12], Altman ^{\underline{al96}} [1], and Feinberg and Sonin ^{\underline{feso96}} [33]) provide the methods to prove that for any initial state and policy there is an equivalent randomized policy in a given class of policies. Theorem ^{\underline{t:nonrep}} 18, Theorem ^{\underline{t:trans}} 16, or equality s(x) = s_{R}(x) (see ^{\underline{feso85, fe92}} [32, 27] imply that a policy can be selected in a nonrandomized form. Theorems ^{\underline{t:main1}} 9, \underline{t:main1m} 11, and ^{\underline{t:trans}} 16 imply the existence uniformly εℓ-optimal policies within certain classes of policies.

1.8 The second main theorem: uniformly nearly

optimal locally stationary policies

s:tsmt

Ornstein’s theorem (Theorem ^{\underline{t:negat1}} 7(ii)) implies the existence of stationary uniformly nearly optimal policies in P MDPs. Example ^{\underline{ex6}} 3.6 implies that such policies do not exist in N MDPs. Demko and Hill ^{\underline{dehi}} [16] proved that if r(x, a) = r(x) < 0 all x ∈ 𝕏 then for any ε > 0 there exists a stationary ε-optimal policy. This result can be interpreted in the following way: if rewards are negative in a strong sense then there exist stationary uniformly nearly optimal policies.

Since stationary nearly optimal policies may not exist, it is natural to consider subsets of the state space on which such policies exist. We say that a nonrandomized policy ϕ is stationary on the set Y ⊆ 𝕏 if ϕ_{n}(x_{0}a_{0} … x_{n}) = ϕ(x_{n}) for some function ϕ when x_{n} ∈ Y. We denote by Π^{S,Y} the set of policies stationary on Y. We remark that Π^{S} = Π^{S,𝕏}. We also denote

s_{Y} (x) = sup_{ϕ∈Π^{S,Y}} w(x, ϕ).

We consider the sets

𝕏^{+} = {x ∈ 𝕏| V (x) > 0}, 𝕏^{−} = {x ∈ 𝕏| V (x) < 0},
𝕏^{c} = {x ∈ 𝕏| A^{c}(x) ≠ 0}, 𝕏^{∗} = X^{+} ∪ 𝕏^{−} ∪ 𝕏^{∗}.

Thus, 𝕏^{+} is the subset of states where the value function is positive, 𝕏^{−} is the subset where the value function is positive, and 𝕏^{c} is the set of states where exist conserving actions. We have that the set 𝕏^{∗} contains all elements of 𝕏 except those where the value function is equal to 0 and there is no conserving actions. Chitashvili ^{\underline{yuch}} [64] showed that if 𝕏 is finite then s_{𝕏^{∗}}(x) = V (x) for all x ∈ 𝕏. Feinberg ^{\underline{fe87a}} [25] proved the existence of uniformly nearly optimal policies in Π^{S,𝕏^{∗}} for the countable state space.

Let

d(x) = sup_{ϕ∈Π^{S,X^{∗}}} inf_{τ∈Q^{b}} 𝔼_{x}^{ϕ} V (x_{τ}).  (1.19) e:defd

The following theorem is a particular case of Theorem 6.2 in Feinberg ^{\underline{fe87a}} [25].

t:prel Theorem 38 Consider a set (f, I)-generating policies I^{f} with the function f satisfying the Non-Repeating Condition. Then for any ε > 0 and for any ℓ ∈ L(d, 𝕏_{Π}) there exists a policy ϕ with the following properties: (i) ϕ is stationary on 𝕏^{∗}, (ii) ϕ ∈ I^{f}, and (iii) is uniformly εℓ-optimal, i.e.

v(x, ϕ) ≥ V (x) − εℓ(x), x ∈ 𝕏.

We observe that if Y ⊆ Z then s_{Y} (x) ≥ s_{Z}(x) for all x ∈ 𝕏. In view of Theorem ^{\underline{t:prel}} 19 it is natural to find the biggest set Y for which s_{Y} (x) = V (x) for all x ∈ 𝕏. Unfortunately, even when 𝕏 is finite, it is possible that there are several maximum sets with this property (a subset Y is called a maximum subset with a given property if there is no set Z other than Y such that Z satisfies this property and contains Y). The following example is similar to one provided by Chitashvili ^{\underline{ch76}} [15]. It shows that it is possible that s_{Y} = V and s_{Z} = V but s_{X∪Y} (x) < V (x) for some x.

ex10 Example 39 Let 𝕏 = {0, 1, g} and 𝔸 = {0} ∪ {b^{1}, b^{2}, … } ∪ {c^{1}, c^{2}, … }. The state g is absorbing, 𝔸(g) = {0}, r(g, 0) = 0, and p(g|g, 0) = 1. We also have that 𝔸(x) = {b^{1}, b^{2}, … } ∪ {c^{1}, c^{2}, … } for x = 1, 2. We also have p(g|x, b^{i}) = 1/i, p(x|x, b^{i}) = 1 − 1/i, p(1|0, c^{i}) = p(0|1, c^{i}) = 1, and r(x, b^{i}) = r(x, c^{i}) = −1/i for i = 1, 2, … and x = 0, 1. It is easy to see that V (g) = s(g) = 0, V (0) = V (1) = 0, and s(0) = s(1) = −1. Let Y = {0, g} and Z = {1, g}. Then 𝕏 = Y ∪Z. It is easy to see that s_{Y} (x) = s_{Z}(x) = V (x).

According to Example 6.1 in Feinberg ^{\underline{fe87a}} [25], the following situation is possible. There are finite sets Z_{n}, n = 1, 2, … such that Z_{n} ⊆ Z_{n+1}, 𝕏 = ∪_{n=1}^{∞}Z_{n}, s_{Z_{n}} = V but s ≠ V. Since s = s_{𝕏}, this example shows that if 𝕏 is countable, maximal subsets, for which there exist good policies stationary on them, may not exist. The following natural way to expand the set 𝕏^{∗} was described in Feinberg ^{\underline{fe87a}} [25].

Let r(x, a) = r^{1}(x, a) + r^{2}(x, a) where r^{1} and r^{2} are measurable in a. We assume that r^{2} is a nonnegative function and consider two MDPs with the same state space, the same action spaces, and the same transition probabilities as the original MDP but with the reward function r^{1} and r^{2} respectively. Let V^{1} and V^{2} are the value functions for these MDPs. We assume that V^{2}(x) < ∞ for all x ∈ 𝕏. We also set Z = {x ∈ 𝕏| V^{1}(x) < 0}. Of course, the set Z depends on the selection of r^{2} which defines r^{1} and V^{1}. For example, we can select r^{2}(x, a) = 0 for all x and a. In this case, r = r + 0 and Z = 𝕏^{−}. We can select r^{2}(x, a) = r^{+}(x, a). Then r^{1} = r^{−} and Z = {x ∈ 𝕏| V_{−}(x) < 0.} It is obvious that this set contains 𝕏^{−}. We also can select r^{2} = kr^{+} where k is a constant or nonnegative bounded function of x and a.

We also remark that if a function r^{2} is replaced with a function, that is greater or equal to r^{2}(x, a) for all x ∈ 𝕏 and for all a ∈ 𝔸(x), then the corresponding set Z expands. However, the function r_{2} cannot be arbitrary large because of the condition V^{2}(x) < ∞ for all x ∈ 𝕏.

t:main2 Theorem 40 (The second main theorem; Feinberg ^{\underline{fe87a}} [25]) Consider a set (f, I)-generating policies I^{f} with the function f satisfying the Non-Repeating Condition. Let Z be a subset of 𝕏 defined above by some nonnegative function r^{2} with V^{2}(x) < ∞ for all x ∈ 𝕏. Then for any ε > 0 and for any ℓ ∈ L(d, 𝕏_{Π}) there exists a policy ϕ with the following properties: (i) ϕ is stationary on 𝕏^{∗} ∪ Z, (ii) ϕ ∈ I^{f}, and (iii) is uniformly εℓ-optimal, i.e.

v(x, ϕ) ≥ V (x) − εℓ(x), x ∈ 𝕏.

We remark that Theorem ^{\underline{t:main2}} 20 implies almost all known results on the existence of uniformly nearly optimal policies. For example, for P MDPs, 𝕏 = 𝕏^{∗} and Theorem ^{\underline{t:main2}} 20 implies Ornstein’s theorem. For I^{f} = Π^{M}, it implies van der Wal’s ^{\underline{vdw83}} [59] theorem on the existence of uniformly nearly optimal Markov policies. If I^{f} is selected to be the set of tracking policies, Theorem \underline{t:main2} 20 gives the positive answer to the question asked by van der Wal and Wessels ^{\underline{vdwwe84}} [61] on the existence of uniformly nearly optimal policies. If X^{0} ⊆ X^{c} Theorem ^{\underline{t:main2}} 20 implies the existence of stationary εℓ-optimal policies and this result strengthens van der Wal’s theorem on stationary strategies ^{\underline{vdw84}} [60]; see also Theorem 2.22 in van der Wal ^{\underline{vdw81}} [58]. In addition, if 𝕏 and 𝔸 are finite, this result implies the existence of stationary optimal policies because the set of stationary policies if finite and the stationary εℓ-optimal policy is optimal for small ε > 0.. In addition, Theorem ^{\underline{t:main1}} 9 contains the statement that if there exists an optimal policy then there exists a stationary optimal policy.

There are two important open questions related to Theorem ^{\underline{t:main1}} 9: (i) how to provide the broadest natural description of the set where stationary policies are sufficient; (ii) how to decrease the function d? With respect to the second question, it would be nice to select d in a form that it equals to 0 for deterministic MDPs. Some results and discussion related to these two important questions can be found in Feinberg ^{\underline{fe86, fe87a}} [23, 25]. In particular, Theorem 6.2 in Feinberg ^{\underline{fe87a}} [25] contains function d which is less than or equal to function d defined in (^{\underline{e:defd}} 3.19).

1.9 Uncountable MDPs

s:umdp

Most of the described above results hold for Borel MDPs. In particular, Dynkin and Yushkevich ^{\underline{dyyu}} [20] studied the sets of strategic measures ℙ_{μ}^{π}. They showed that this is a convex Borel space. Furthermore, this set is convex in a strong sense when strategic measures are integrated with respect to any probability measure; see ^{\underline{dyyu}} [20, Section 3.5]. The observation that this set is convex is important. Imagine that we expand the notion of a strategy in the following way: the decision-maker selects randomly a policy at epoch 0 and then follows it. This initial randomization procedure is defined by a probability measure on the set of strategic measures with a given initial distribution or state. We call such strategies mixed. The convexity of the set of strategic measures implies that for each mixed policy there is an equivalent randomized policy. Therefore, in-fact mixed policies do not expand the set of policies. In view of this fact, policy π in Theorem ^{\underline{t:MC-Markov}} 1 which was originally established by Strauch ^{\underline{st66}} [53] for Borel MDPs and λ_{1} = 1, can be constructed in two steps for a fixed initial state x: for any sequence of nonnegative numbers λ_{i} with the sum equal to 1 and for any sequence of policies π^{i}, i = 1, 2, …, there exists a policy σ with ℙ_{x}^{σ} = ∑_{i=1}^{∞} ℙ_{x}^{σ^{i}},; and (ii) for any

policy σ there exists a Markov policy π such that ℙ_{x}^{π}{x_{n} ∈ Y, a_{n} ∈ B} = ℙ_{x}^{σ}{x_{n} ∈ Y, a_{n} ∈ B} for any Borel subsets Y ⊆ 𝕏 and B ⊆ 𝔸. In both cases (i) and (ii) there are simple formulae for σ and π.

Another general result for strategic measures is that strategic measures for randomized Markov strategies can be presented as convex integral combinations of strategic measures for nonrandomized Markov policies; Feinberg ^{\underline{fe96}} [28]. This fact implies that for any policy and for any given initial distribution there exists a Markov policy with equal or better performance; Feinberg ^{\underline{fe82, fe82a}} [21, 22]. Schäl ^{\underline{sc75}} [50], Balder ^{\underline{ba89}} [3], and Yushkevich ^{\underline{yu97}} [63] studied topological properties of the sets on strategic measures and used them to establish sufficient conditions for the existence of optimal policies.

The optimality equation holds for Borel MDPs; see Strauch ^{\underline{st66}} [53], Dynkin and Yushkevich ^{\underline{dyyu}} [20], and Bertsekas and Shreve ^{\underline{besh78}} [4]. The major technical difficulty when a Borel state space is considered instead of a countable state space is related to so-called selection theorems. All results from Section ^{\underline{s:SPMO}} 3.5, except Ornstein’s theorem (Theorem ^{\underline{t:negat1}} 7(ii)) were originally proved for classical Borel models and the existence of (p, ε)-optimal policies was proved.

Blackwell ^{\underline{bl67}} [8] recognized that the validity of Ornstein’s theorem for Borel positive MDPs was a difficult question and posted it as an open problem. Frid ^{\underline{fr70}} [34] proved that Ornstein’s theorem is valid for Borel MDPs if (p, εV)- optimality is considered instead of εV -optimality. Schäl and Sudderth ^{\underline{scsu}} [52] found a correctable mistake in Frid’s proof: one of the sets where Frid switched policies was universally measurable but not Borel measurable.

Here I would like to mention the name of gifted mathematician Efim Frid who died at a young age as a result of an accident: he was hit by a vehicle when he was crossing a street in Odessa. Efim was a student of Nicolai Krylov. In addition to the proof of Blackwell’s conjecture, Frid also wrote one of the first papers on MDPs with multiple criteria ^{\underline{fr72}} [35] and several interesting papers on stochastic games, in particular, on the sequence of nonzero sum two-person games. Though during many years we both have been living in Moscow at the same time, unfortunately I have never met Efim Frid.

Bertsekas and Shreve ^{\underline{besh78}} [4] studied MDPs with universally measurable policies. Except Ornstein’s theorem they proved that for all results on the existence of ε-optimal policies from Section ^{\underline{s:SPMO}} 3.5, there are similar ε-optimal policies for Borel MDPs with universally nearly optimal policies. Blackwell and Ramakrishnan ^{\underline{blra}} [11] constructed an example of a P Borel MDP with a bounded function V for which there is no stationary universally measurable policy which is uniformly ε-optimal. This example implies that Ornstein’s theorem as well as more general statements, Theorems ^{\underline{t:main1}} 9, ^{\underline{t:main1m}} 11, ^{\underline{t:trans}} 16, ^{\underline{t:prel}} 19, and \underline{t:main2} 20 cannot be expanded to Borel MDPs with universally measurable polices. The questions whether any of these statements or Theorem ^{\underline{t:mare}} 15 hold for Borel MDPs when the notion of p-a.s. εℓ policies is considered are completely open. The key issue here is Theorem ^{\underline{t:main1}} 9. Its proof in Feinberg and Sonin ^{\underline{feso83}} [31] used explicitly that the state space is not bigger than countable. Except Frid ^{\underline{fr70}} [34] and Blackwell and Ramakrishnan ^{\underline{blra}} [11], the only research that studied possibilities to expand Ornstein’s theorem to uncountable state spaces and other relevant issues, I am familiar with, is the paper by Schäl and Sudderth ^{\underline{scsu}} [52].

As was observed in Feinberg ^{\underline{fe91}} [26], it is not clear whether the Non-Repeating Condition implies the result similar to Theorem ^{\underline{t:nonrep}} 18 for Borel MDPs. It was shown there that a so-called Strong Non-Repeating Condition, which holds for Markov policies, implies such result.

We also mention that Feinberg ^{\underline{fe92}} [27] proved that s_{R}(x) = s(x) for all x ∈ 𝕏. Schäl ^{\underline{sc83}} [51] proved that s(x) = V (x), x ∈ X, for models with compact action sets. Since Theorem ^{\underline{t:main1}} 9 is an open question for Borel MDPs when (p, εℓ)-optimality is considered, we do not know if s = T s for GC Borel MDPS. The non-trivial part is to prove that s(x) ≥ T s(x) for all x ∈ 𝕏. The measurability properties of function s were established in Feinberg ^{\underline{fe96}} [28] by using the results by Sudderth ^{\underline{su}} [54] and Blackwell ^{\underline{bl76}} [9].

Acknowledgement. This research was partially supported by NSF Grant DMI-9908258.

Bibliography

al96 [1] [al96] E. Altman, “Constrained Markov decision processes with total cost criteria: occupation measures and primal LP,” Math. Methods Oper. Res. 43 pp. 45–72, 1996.

al99 [2] [al99] E. Altman, Constrained Markov Decision Processes, Chapman & Hall/CRC, Boca Raton, 1999.

ba89 [3] [ba89] E.J. Balder, “On compactness of the space of policies in stochastic dynamic programming,” Stoch. Proc. Appl. 32 pp. 141–151, 1989.

besh78 [4] [besh78] D.P. Bertsekas and S. Shreve, Stochastic Optimal Control: the Discrete Time Case, Academic Press, New York, 1978 (reprinted by Athena Scientific, Belmont, 1996).

besh79 [5] [besh79] D.P. Bertsekas and S. Shreve, “Existence of stationary optimal policies in deterministic optimal control,” J. Math. Anal. Appl. 69, pp. 607–620, 1979.

bl62 [6] [bl62] D. Blackwell, “Discrete dynamic programming,” Ann. Math. Stat. 33 pp. 719–726, 1962.

bl65 [7] [bl65] D. Blackwell, “Discounted dynamic programming,” Ann. Math. Stat. 36 pp. 226–235, 1965.

bl67 [8] [bl67] D. Blackwell, “Positive dynamic programming,” in Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability 1 pp. 415–418, University of California Press, Berkeley, 1967.

bl76 [9] [bl76] D. Blackwell, “The stochastic processes of Borel Gambling and dynamic programming,” Ann. Statist. 4 pp. 370–374, 1976.

blfror [10] [blfror] D. Blackwell, D. Freedman and M. Orkin, “The optimal reward operator in dynamic programming,” Ann. Probab. 2 pp. 926– 941, 1974. blra [11] [blra] D. Blackwell and S. Ramakrishnan, “Stationary plans need not

be uniformly adequate for leavable, Borel gambling problems,” Proc. Am. Math. Soc. 102 pp. 1024–1027, 1988.

bo88 [12] [bo88] V.S. Borkar, “A convex analytic approach to Markov decision processes,” Prob. Theor. Relat. Fields 78 pp. 583-602, 1988.

ccfemo [13] [ccfemo] R. Cavazos-Cadena, E.A. Feinberg and R. Montes-de-Oca, “A note on the existence of optimal policies in total reward dynamic programs with compact action sets,” Math. Oper. Res., to appear.

ccmo [14] [ccmo] R. Cavazos-Cadena and R. Montes-de-Oca, “Nearly optimal stationary policies in negative dynamic programming,” Math. Methods Oper. Res. 49 pp. 441–456, 1999.

ch76 [15] [ch76] R.Ya. Chitashvili, “On the existence of ε-optimal stationary policies for a controlled Markov chain,” Soobshch. Acad. Nauk. Gruzin. SSR 83 pp. 549–552, 1976.

dehi [16] [dehi] S. Demko and T.P.Hill, “Decision processes with total cost criteria,” Ann. Prob. 9 pp. 293-301, 1981.

de67 [17] [de67] E.V. Denardo, “Contracting mappings in the theory underlying dynamic programming,” SIAM Rev. 9 pp. 165–177, 1967.

dest [18] [dest] C. Derman and R. Strauch, “A note on memoryless rules for controlling sequential control processes,” Ann. Math. Stat. 37 pp. 276– 278, 1966.

dusa [19] [dusa] L.E. Dubins and L.J. Savage, How to Gamble If You Must: Inequalities for Stochastic Processes. McGraw-Hill, New York; second edition: Dover, New York, 1976.

dyyu [20] [dyyu] E.B. Dynkin and A.A. Yushkevich, Controlled Markov Processes. Springer-Verlag, New York, 1979.

fe82 [21] [fe82] E.A. Feinberg, ”Nonrandomized Markov and semi-Markov strategies in dynamic programming,” SIAM Theory Prob. Appl. 27 pp. 116–126, 1982.

fe82a [22] [fe82a] E.A. Feinberg, ”Controlled Markov processes with arbitrary numerical criteria,” SIAM Theory Prob. Appl. 27 pp. 486–503, 1982. fe86 [23] [fe86] E.A. Feinberg, ”The structure of persistently nearly optimal

strategies in stochastic dynamic programming,” Lecture Notes in Control and Inform. Sci. 81 pp. 22–31, 1986.

fe87 [24] [fe87] E.A. Feinberg, ”Sufficient classes of strategies in discrete dynamic programming. I: decomposition of randomized strategies and imbedded models,” SIAM Theory Prob. Appl. 31 pp. 658–668, 1987.

fe87a [25] [fe87a] E.A. Feinberg, ”Sufficient classes of strategies in discrete dynamic programming. I: locally stationary strategies,” SIAM Theory Prob Appl. 32 pp. 478–493, 1987.

fe91 [26] [fe91] E.A. Feinberg, “Nonrandomized strategies in stochastic decision processes,” Ann. Oper. Res. 29 pp. 315–332, 1991.

fe92 [27] [fe92] E.A. Feinberg, “On stationary strategies in borel dynamic programming,” Math. Oper. Res. 17 pp. 393–397, 1992.

fe96 [28] [fe96] E.A. Feinberg, “On measurability and representation of strategic measures in Markov decision processes”, in Statistics, Probability and Game Theory Papers in Honor of David Blackwell (eds. T.S. Ferguson et al.), IMS Lecture Notes - Monograph Series, 30, pp. 29–43, 1996.

fesh96 [29] [fesh96] E.A. Feinberg and A. Shwartz, “Constrained discounted dynamic programming,” Math. of Operations Research 21 pp. 922–945, 1996.

feso81 [30] [feso81] E.A. Feinberg and I.M. Sonin, “Markov policies in infinite horizon dynamic programming problems with bounded value functions,” in Abstracts of 4-th USSR - Japan Symposium on Probability Theory and Mathematical Statistics 1 pp. 209–210, Tbilisi, 1982.

feso83 [31] [feso83] E.A. Feinberg and I.M. Sonin, “Stationary and Markov policies in countable state dynamic programming,” Lecture Notes in Math., 1021 pp. 111–129, 1983.

feso85 [32] [feso85] E.A. Feinberg and I.M. Sonin, “Persistently nearly optimal strategies in stochastic dynamic programming,” in Statistics and Control of Stochastic Processes, Steklov Seminar pp. 69–101, Optimization Software, New York, 1985

feso96 [33] [feso96] E.A. Feinberg and I.M. Sonin, “Notes on equivalent stationary policies in Markov decision processes with total rewards,” ZOR - Math. Methods of Oper. Res. 44 pp. 205–221, 1996. fr70 [34] [fr70] E.B. Frid, “On a problem of D. Blackwell from the theory of

dynamic programming,” SIAM Theory Prob Appl. 15 pp. 719–722, 1970.

fr72 [35] [fr72] E.B. Frid, “On optimal strategies in cintrol problems with constraints,” SIAM Theory Prob Appl. 17 pp. 188–192, 1972.

gisk79 [36] [gisk79] I.I. Gikhman and A.V. Skorokhod, Controlled Random Processes, Springer, New York, 1979.

hi79 [37] [hi79] T. Hill, “On the existence of good Markov strategies,” Trans. Amer. Math. Soc. 247 pp. 157–176, 1979.

hi [38] [hi] K. Hinderer, Foundations of Non Stationary Dynamic Programming with Discrete Time Parameter, Lecture Notes in Operations Research 33, Springer-Verlag, NY, 1970.

ho [39] [ho] A. Hordijk, Dynamic Programming and Markov Potential Theory, Math. Centre Tracts 51, Math. Centrum, Amsterdam, 1974.

ka [40] [ka] L.C.M. Kallenberg, Linear Programming and Finite Markovian Problem, Math. Centre Tracts 148, Math. Centrum, Amsterdam, 1983.

kr65 [41] [kr65] N.V. Krylov, “Construction of an optimal strategy for a finite controlled chain,” SIAM Theory Prob. Appl. 10 pp. 45–54, 1965.

kr85 [42] [kr85] N.V. Krylov, “Once more about the connection between elliptic operators and Itô’s stochastic equations,” in Statistics and Control of Stochastic Processes, Steklov Seminar(N.V. Krylov, R.Sh. Liptser, and A.A. Novikov, eds.) pp. 69–101, Optimization Software, New York, 1985

kr87 [43] [kr87] N.V. Krylov, “An approach in the theory of controlled diffusion processes,” SIAM Theory Prob. Appl. 31 pp. 604–626, 1987.

masu92 [44] [masu92] A. Maitra and W.D. Sudderth “The optimal return operator in negative dynamic programming,” Math. Oper. res. 17 pp. 921–931, 1992.

masu96 [45] [masu96] A. Maitra and W.D. Sudderth, Discrete Gambling and Stochastic Games, Springer-Verlag, New York, 1996.

or [46] [or] D. Ornstein, “On the existence of stationary optimal strategies,” Proc. Am. Math. Soc. 20 pp. 563–569, 1969. ne [47] [ne] J. Neveu, “Mathematical Foundations of the Calculus of Proba-

bility,” Holden-Day, San Francisco, 1965.

pu [48] [pu] M.L. Puterman, Markov Decision Processes, Wiley, New York, 1994.

ro83 [49] S.M. Ross, Introduction to Stochastic Dynamic Programming, Academic Press, Orlando, 1983.

sc75 [50] [sc75] M. Schäl, “On dynamic programming: compactness of the space of policies,” Stoch. Processes Appl. 3 pp. 345–364, 1975.

sc83 [51] [sc83] M. Schäl, “Stationary policies in dynamic programming models under compactness assumptions,” Math. Oper. Res. 8 pp. 366–372, 1983.

scsu [52] [scsu] M. Schäl and W.D. Sudderth, “Statioanary policies and Markov policies in Borel dynamic programming,” Probab. Th. Rel Fields 74 pp. 91–111, 1987.

st66 [53] [st66] R. Strauch, “Negative dynamic programming,” Ann. Math. Stat. 37 pp. 871–890, 1966.

su [54] [su] W.D. Sudderth “On the existence of good stationary strategies,” Trans. Amer. Math. Soc. 126 pp. 399–414, 1969.

vd85 [55] [vd85] R. van Dawen, “Negative dynamic programming,” Preprint no. 458, University of Bonn, 1985.

vd86 [56] [vd86] R. van Dawen, “Pointwise and uniformly good stationary strategies in dynamic programming models,” sl Math. Oper. Res. 9 pp. 521-535 (1986).

vdsh [57] [vdsh] R. van Dawen and M. Schäl, “On the existence of Stationary Optimal Policies in Markov Decision Processes,” Z. Angew. Math. Mech. 63, no 5, pp. T403-T404, 1983.

vdw81 [58] [vdw81] J. van der Wal, Stochastic Dynamic Programming, Math. Centre Tracts 139, Math. Centrum, Amsterdam, 1981.

vdw83 [59] [vdw83] J. van der Wal, “On uniformly nearly-optimal Markov strategies,” in Operations Research Proceedings 1982, pp. 461–467. Springer-Verlag, Berlin, 1983. vdw84 [60] [vdw84] J. van der Wal, “On stationary strategies in countable state

total reward Markov decision processes,” Math. Oper. Res. 9 pp. 290– 300, 1984.

vdwwe84 [61] [vdwwe84] J. van der Wal and J. Wessels, “On the use of information in Markov decision processes,” Statistics & Decisions 2, pp. 1–21, 1984.

vh [62] [vh] K.M. van Hee, “Markov strategies in dynamic programming,” Math. Oper. Res. 3 pp. 37–41, 1978.

yu97 [63] [yu97] A.A. Yushkevich “The compactness of a policy space in dynamic programming via an extension theorem for Caratheodory functions,” Math. Oper. Res. 22, pp. 458–467, 1997.

yuch [64] [yuch] A.A. Yushkevich and R.Ya. Chitashvili, “Controlled random sequences and Markov chains,” Russian Math. Surveys 37, no 6, pp. 239-274, 1982.