Definitions and notation

Eugene Feinberg SUNY Stony Brook Stony Brook etc.

Adam Shwartz Electrical Engineering. Technion Etc.

May 29, 2000

Chapter 1

Introduction

ch:intro

Abstract

In this chapter we describe the basic structure of a Markov Decision Process. We introduce the notation and then give a quick tour of this volume. At this point, we use this as information for authors, with examples.

1.1 Introduction

In this section we shall introduce the volume, its purpose, etc. including a heuristic description of what an MDP is (in contrast to the formal presentation of section ^{\underline{C1sec:notation}} 1.2).

1.2 Notation

C1sec:notation

Let ℕ = {0, 1, … } and let ℝ^{n} be an n-dimensional Euclidean space, ℝ = ℝ^{1}. A Markov Decision Process (MDP) is defined through the following objects:

a state space 𝕏;

an action space 𝔸;

sets 𝔸(x) of available actions at states x ∈ 𝕏;

transition probabilities, denoted by p(Y |x, a);

reward functions r(x, a) denoting the one-step reward using action a in state x.

The above objects have the following meaning. There is a stochastic system with a state space 𝕏. When the system is at state x ∈ 𝕏, a decisionmaker selects an action a from the set of actions 𝔸(x) available at state x. After an action a is selected, the system moves to the next state according to the probability distribution p(·|x, a) and the decision-maker collects a onestep reward r(x, a). The selection of an action a may depend on the current state of the system, the current time, and the available information about the history of the system. At each step, the decision maker may select a particular action or, in a more general way, a probability distribution on the set of available actions 𝔸(x). Decisions of the first type are called nonrandomized and decisions of the second type are called randomized.

Discrete MDPs. An MDP is called finite if the state and action sets are finite. We say that a set is discrete if it is finite or countable. An MDP is called discrete if the state and action sets are discrete.

A significant part of research and applications related to MDPs deals with discrete MDPs. For discrete MDPs, we do not need additional measurability assumptions on the major objects introduced above. Readers who are not familiar with measure theory can still read the papers of this volume, since most of the papers deal with discrete MDPs: for the other papers, the results may be restricted to discrete state and action sets.

For a discrete state space 𝕏 we denote the transition probabilities by p(y|x, a) or p_{xy}(a), and use (in addition to x, y) also the letters i, j, k etc. to denote states. Unless mentioned otherwise, we always assume that p(𝕏|x, a) = 1.

The time parameter is t, s or n ∈ ℕ and a trajectory is a sequence x_{0}a_{0}x_{1}a_{1} …. The set of all trajectories is H_{∞} = (𝕏 × 𝔸)^{∞}. A trajectory of length n is called a history, and denoted by h_{n} = x_{0}a_{0} … x_{n−1}a_{n−1}x_{n}. Let H_{n} = 𝕏 × (𝔸 × 𝕏)^{n} be the space of histories up to epoch n ∈ ℕ. A nonrandomized policy is a sequence of mappings ϕ_{n}, n ∈ ℕ, from H_{n} to 𝔸 such that ϕ_{n}(x_{0}a_{0} … x_{n−1}a_{n−1}x_{n}) ∈ 𝔸(x_{n}). If for each n this mapping depends only on x_{n}, then the policy ϕ is called Markov. In other words, a Markov policy ϕ is defined by mappings ϕ_{n} : 𝕏 → 𝔸 such that ϕ_{n}(x) ∈ 𝔸(x) for all x ∈ 𝕏, n = 0, 1, …. A Markov policy ϕ is called stationary if the ϕ_{n} do not depend on n. A stationary policy is therefore defined by a single mapping ϕ : 𝕏 → 𝔸 such that ϕ(x) ∈ 𝔸(x) for all x ∈ 𝕏. We denote by Π, Π^{M}, and Π^{S} the sets of all nonrandomized, Markov, and stationary policies respectively. We observe that Π^{S} ⊆ Π^{M} ⊆ Π.

As mentioned above, by selecting actions randomly, it is possible to expand the set of policies. A randomized policy π is a sequence of transition probabilities π_{n}(a_{n}|h_{n}) from H_{n} to 𝔸, n ∈ ℕ, such that π_{n}(𝔸(x_{n})|x_{0}a_{0} … x_{n−1}a_{n−1}x_{n}) = 1. A policy π is called randomized Markov if π_{n}(a_{n}|x_{0}a_{0} … x_{n−1}a_{n−1}x_{n}) = π_{n}(a_{n}|x_{n}). If π_{m}(·|x) = π_{n}(·|x) for all m, n ∈ ℕ then the Markov policy π is called randomized stationary. A randomized stationary policy π is thus defined by a transition probability π from 𝕏 to 𝔸 such that π(𝔸(x)|x) = 1 for all x ∈ 𝕏. We denote by Π^{R}, Π^{RM}, Π^{RS} the sets of all randomized, randomized Markov, and randomized stationary policies respectively. We have that Π^{RS} ⊆ Π^{RM} ⊆ Π^{R}, and in addition Π^{S} ⊆ Π^{RS}, Π^{M} ⊆ Π^{RM}, and Π ⊆ Π^{R}.

Note that, while we try to be consistent with the above definitions, there is no standard terminology for policies: in particular, there is no general agreement as to whether “stationary” implies nonrandomized or, more generally, whether the “default” should be randomized (the more general case) or nonrandomized. The following additional terms are sometimes also used:

pure policy means nonrandomized;

deterministic policy means (nonrandomized) stationary.

The stochastic process evolves as follows. If at time n the process is in state x, having followed the history h_{n}, then an action is chosen (perhaps randomly) according to the policy π. If action a ensued, then at time n + 1 the process will be in the state y with probability p(y|x, a).

Given an initial state x and a policy π, the “evolution rule” described above defines all finite-dimensional distributions x_{0}, a_{0}, …, x_{n}, n ∈ ℕ. Kolmogorov’s extension theorem guarantees that any initial state x and any policy π define a stochastic sequence x_{0}a_{0}x_{1}a_{1} …. We denote by ℙ_{x}^{π} and 𝔼_{x}^{π} respectively the probabilities and expectations related to this stochastic sequence; ℙ_{x}^{π}{x_{0} = x} = 1.

Any stationary policy ϕ defines a Markov chain with transition probabilities p_{xy}(ϕ) = p(y|x, ϕ(x)) on the state space 𝕏. A randomized stationary policy π also defines a Markov chain with the state space 𝕏. In the latter case, the transition probabilities are p_{xy}(π) = ∑_{a∈𝔸(x)} π(a)p(y|x, a). We denote by P (π) the transition matrix with elements {p_{xy}(π)}. The limiting matrix

Q(π) = lim_{N→∞} \frac{1}{N} ∑_{n=0}^{N−1} P^{n}(ϕ).  (1.1)

always exists and it is stochastic if 𝕏 is finite; Chung ^{\underline{chung}} [2, Section 1.6]. Let f be a terminal reward function and β be a discount factor. We denote by v_{N}(x, π, β, f) the expected total reward over the first n steps, n ∈ ℕ:

v_{N}(x, π, β, f) = 𝔼_{x}^{π} [∑_{n=0}^{N−1} β^{n}r(x_{n}, a_{n}) + β^{N}f(x_{N})] ,  (1.2) C1e:DefFinRew

whenever this expectation is well-defined.

If β ∈ [0, 1[ then we deal with expected total discounted reward. If β = 1, we deal with expected total undiscounted reward or simply total reward. If the discount factor β ∈ [0, 1] is fixed, we usually write v(x, π) instead of v(x, π, β).

The expected total reward over an infinite horizon is

v(x, π) = v(x, π, β) = v_{∞}(x, π, β, 0) .  (1.3) C1e:DefDiscCost

Conditions for the total reward v(x, π, 1) to be well-defined are usually stronger than the conditions that ensure that total discounted rewards v(x, π, β), 0 ≤ β < 1, are well-defined. The expected reward per unit time is

w(x, π) = lim inf_{n→∞} \frac{1}{N} v_{N}(x, π, 1, 0).  (1.4) C1e:DefAvRew

If a performance measure g(x, π) is defined for all policies π, we denote

G(x) = sup_{π∈Π^{R}} g(x, π).  (1.5) C1e:maxValue

In terms of the performance measures defined above, this yields the values

V_{N}(x, β, f) =^{def} sup_{π∈Π^{R}} v_{N}(x, π, β, f) ,  (1.6) C1e:DefFinValue
V (x) = V (x, β) =^{def} sup_{π∈Π^{R}} v(x, π, β) ,  (1.7) C1e:DefDiscValue
W (x) =^{def} sup_{π∈Π^{R}} w(x, π) .  (1.8) C1e:DefAvValue

For ϵ ≥ 0, a policy π is called ϵ-optimal for criterion g if g(x, π) ≥ G(x)−ϵ for all x ∈ 𝕏. A 0-optimal policy is called optimal.

For a function f on 𝕏, we consider the reward operators:

P^{a}f(x) =^{def} 𝔼[f(x_{1}) | x_{0} = x, a_{0} = a] ,  (1.9) C1e:TransOper
T_{β}^{a}f(x) =^{def} r(x, a) + βP^{a}f(x)  (1.10) C1e:DiscOper

and the optimality operators:

P f(x) =^{def} sup_{a∈𝔸(x)}P^{a}f(x) ,  (1.11) C1e:TransOptOper
T_{β}f(x) =^{def} sup_{a∈𝔸(x)}T_{β}^{a}f(x) .  (1.12) C1e:DiscOptOper

The finite horizon Optimality Equation is

V_{N+1}(x) = T_{β}V_{N}(x),  N = 0, 1, ….  (1.13) C1e:FinHorOptEq

The discounted reward Optimality Equation is

V (x) = T_{β}V (x) .  (1.14) C1e:DiscOptEq

An action a ∈ A(x) is called conserving at state x for the (N + 1)-step problem if T_{β}^{a}V_{N}(x) = T_{β}V_{N}(x). An action a ∈ A(x) is called conserving at state x for the total discounted reward if T_{β}^{a}V (x) = T_{β}V (x).

When β = 1 we denote T^{a} = T_{1}^{a} and T = T_{1}. In particular,

V (x) = T V (x)  (1.15) C1e:TotOptEq

is the Optimality Equation for expected total undiscounted rewards.

For total reward criteria, value functions usually satisfy the optimality equation. In addition, the sets of conserving n-step actions, n = 1, …, N +1 form the sets of optimal actions for (N + 1)-step problems. Under some additional conditions, the sets of conserving actions form the sets of optimal actions for infinite horizon problems. We shall consider these results in appropriate chapters. The average reward Optimality Equations are

W (x) = P W (x)  (1.16) C1e:AvOptEq1
W (x) + h(x) = sup_{a∈𝔸′(x)}T^{a}h(x) ,  (1.17) C1e:AvOptEq2

where

𝔸′(x) = {a ∈ 𝔸(x) : P^{a}W (x) = P W (x)} .  (1.18)

Equation (^{\underline{C1e:AvOptEq1}} 1.16) is called the First Optimality Equation and equation (^{\underline{C1e:AvOptEq2}} 1.17) is called the Second Optimality Equation. Note that if W (x) = W, a constant, then the First Optimality Equation holds and 𝔸′(x) = 𝔸(x). In this case, the Second Optimality Equations transforms into

W + h(x) = T h(x)  (1.19) C1e:OptEq2

which is often referred to simply as the Optimality Equation for average rewards.

We allow for the starting point x to be defined by an initial probability distribution μ. In this case, we keep the above notation and definitions but we replace the initial state x with the initial distribution μ. For example, we use ℙ_{μ}^{π}, 𝔼_{μ}^{π}, v(μ, π), V (μ), w(μ, π), and W (μ). We remark that, generally speaking, optimality and ϵ-optimality with respect to all initial distributions are stronger than the defined above optimality and ϵ-optimality with respect to all initial states. However, in many natural cases these definitions are equivalent. For example, it is true for total reward criteria.

A more general problem arises when there are multiple objectives. Suppose there are (K + 1) reward functions r_{k}(x, a), k = 0, …, K. For finite horizon problems, terminal rewards may also depend on k. In this case, we index by k = 0, …, K all functions that describe rewards. For example, we use the notation w_{k}(x, π), f_{k}(x), and W_{k}(x).

For problems with multiple criteria, it is usually natural to fix an initial state x. It is also possible to fix an initial distribution μ, with our convention that all definitions remain the same, but we write μ instead of x. So, for simplicity, we define optimal policies when the initial state x (not a distribution) is fixed.

If the performance of a policy π is evaluated by (K + 1) criteria g_{k}(x, π) then one goal may be to optimize criterion g_{0} subject to constraints on g_{1}, …, g_{K}. Let C_{k}, k = 1, …, K, be given numbers. We say that a policy π is feasible if

g_{k}(x, π) ≥ C_{k},  k = 1, …, K .  (1.20) C1e:DefFeasible

A policy π is called optimal for a constrained optimization problem if it is feasible and

g_{0}(x, π) ≥ g_{0}(x, σ) for any feasible policy σ.  (1.21) C1e:DefOptConstr

Nondiscrete MDPs: general constructions. When a state space 𝕏 or an action space 𝔸 are is not discrete, the natural assumption is that they are measurable spaces endowed with σ-fields X and A respectively. When 𝕏 or 𝔸 are discrete, the corresponding σ-field is the set of all subsets of the corresponding set. It is also natural to assume that the sets 𝔸(x) ∈ A of feasible actions are measurable, for all states x ∈ 𝕏. Of course, this assumption always holds when 𝔸 is discrete.

Unless we specify otherwise, we always consider a Borel σ-field B(ℝ) on ℝ: this is the minimal σ field containing all intervals. For non-discrete MDPs, we also assume that r is a measurable function on (𝕏×𝔸, X ×A) and p(Y |x, a) is a regular transition probability from (𝕏 × 𝔸, X × A) to (𝕏, X). Recall that given two measurable spaces (E_{1}, E_{1}) and (E_{2}, E_{2}), we call p a regular transition probability from E_{1} to E_{2} if the following two conditions hold: (i) p(·|e_{2}) is a probability measure on (E_{1}, E_{1}) for any e_{2} ∈ E_{2}, and (ii) the function p(B|·) is measurable on E_{2} for any B ∈ E_{1}.

In order to define policies in the general situation, we consider σ-fields H_{n} = X × (A × X)^{n} on the sets of histories H_{n} = 𝕏 × (𝔸 × 𝕏)^{n}. Nonrandomized and randomized strategies are defined in a way similar to discrete MDPs, with standard and natural additional measurability conditions: (a) nonrandomized policies π are defined by mappings π_{n} which are measurable on (H_{n}, H_{n}), and (b) stationary and Markov policies are defined by mappings which are measurable on 𝕏 × 𝔸. Similarly, for randomized policies, π_{n} are regular transition probabilities from (H_{n}, H_{n}) to (𝔸, A) and, for randomized Markov and stationary policies, they are regular transition probabilities from (𝕏 × 𝔸, X × A) to (𝔸, A).

Let H_{∞} = (X × A)^{∞}. Ionescu Tulcea theorem, Neveu ^{\underline{ne}} [5, Section 5.1], implies that any initial state x and policy π define a unique probability measure on (H_{∞}, H_{∞}). We denote this measure by ℙ_{x}^{π}. Sometimes it is called the “strategic” measure. We denote by 𝔼_{x}^{π} expectations with respect to this measure. We also notice that Ionescu Tulcea theorem implies that ℙ_{x}^{π} is a regular transition probability from (𝕏, X) to (H_{∞}, H_{∞}) and this implies that the functions v_{n}(x, π, β, f) and v(x, π, β) are measurable in x for any policy π (the terminal function f is also assumed to be measurable).

We remark that we use Ionescu Tulcea theorem instead of better known Kolmogorov’s extension theorem primarily because the latter requires additional assumptions about the structure of the state space (it has to be Borel) and the first one has no such structural assumptions.

At the intuitive level, randomized decisions are more general than nonrandomized ones; this means that any nonrandomized policy belongs to the class of randomized policies. In addition, in order to avoid trivial situation, an MDP has to have at least one policy. In order to guarantee these two intuitive properties, we always assume the following two mild conditions:

(i) all one-point sets {a} are elements of A, a ∈ 𝔸; (ii) there is at least one measurable function ϕ from 𝕏 to 𝔸 such that ϕ(x) ∈ 𝔸(x) for all x ∈ 𝕏 The first assumption always holds for models with discrete state and action spaces. The second assumption always holds for models with discrete state spaces.

For a measure ν and a measurable function f we use the equivalent notations

ν(f) =^{def} ∫ f(α) dν(α) =^{def} f(ν) .  (1.22)

If we denote π_{x}(·) = π(·|x) for a randomized stationary policy π then, similarly to discrete MDPs, this policy defines a Markov chain with transition probabilities p(dy|x, π_{x}). If 𝕏 is discrete, this chain has transition matrix P (π) with elements p_{xy}(π_{x}).

Thus, an MDP, strategies, and objective functions can be defined under very general conditions. However, very little can be done if one tries to analyze MDPs with arbitrary measurable state spaces. The first complication is that the value functions V may not be measurable even for one-step models. The second complication is that an important step in the analysis of MDPs is to construct an equivalent randomized Markov policy for an arbitrary policy; see Chapter ???. This can be done by constructing regular transition probabilities ℙ_{x}^{π}(da_{n}|x_{n}) which may not exist for general state and action spaces. These two complications do not exist if the state space is countable. These two complications can be resolved if 𝕏 and 𝔸 Borel spaces. In addition, at the current state of our knowledge, there is no clear need to consider MDPs with arbitrary state measurable spaces because there is no clear motivation or practical needs for such objects. For example, MDPs with Borel state spaces have applications to statistics, control of models with incomplete information, and to inventory management. However, for example, we are not aware of possible applications of MDPs with state spaces having higher cardinality than continuum.

Discrete state MDPs. In this case, the state space 𝕏 is discrete and the action space is a measurable space (𝔸, A) such that all one-point sets are measurable. The sets of feasible actions 𝔸(x) are also elements of A. Reward functions r(x, a) and transition probabilities p(y|x, a) are automatically measurable in a. All constructions described for discrete and general MDPs go through with X being the σ-field of all subsets of 𝕏.

Classical Borel MDPs. Though we do not follow any particular text, all definitions, constructions, and statements, related to Borel spaces we mention in this chapter can be found in Bertsekas and Shreve ^{\underline{bs}} [1, Chapter 7]; see also Dynkin and Yushkevich ^{\underline{dy}} [3] and Kechris ^{\underline{ke}} [4].

Two measurable spaces (E_{1}, E_{1}) and (E_{2}, E_{2}) are called isomorphic if there is a one-to-one measurable mapping f of (E_{1}, E_{1}) onto (E_{2}, E_{2}) such that f^{−1} is measurable. A Polish space is a complete separable metric space. Unless we specify otherwise, we always consider a Borel σ-fields B(E) on a metric space E; B(E) is the minimal σ-field containing all open subsets of E. Of course, any measurable subset E′ of a Polish space forms a Polish space endowed with the Borel σ-field which is the intersection of E′ with Borel subsets of the original space. A measurable space (E, E) is called Borel if it is isomorphic to a Polish space. All Borel spaces are either finite or countable or continuum, and two Borel spaces with the same cardinality are isomorphic. Therefore, uncountable Borel spaces are continuum. They are also isomorphic to each other and to the sets (ℝ, B(ℝ)) and ([0, 1], B([0, 1])).

The assumptions for Borel MDPs are:

(i) 𝕏 and 𝔸 are Borel spaces and X and A are corresponding Borel σ-fields;

(ii) the graph

Gr 𝔸(x) = {(x, a)| x ∈ 𝕏, a ∈ 𝔸(x)}

is a measurable subset of 𝕏 × 𝔸 and there exists at least one measurable mapping ϕ of 𝕏 into 𝔸 such that ϕ(x) ∈ 𝔸(x) for all x ∈ 𝔸(x);

(iii) the reward functions r(x, a) are measurable on 𝕏 × 𝔸 and the transition probabilities p(·|x, a) are regular transition probabilities from 𝕏 × 𝔸 to 𝕏.

Conditions (i) and (iii) are similar to the corresponding assumptions for general models. The measurability of the graph in (ii) implies that the sets 𝔸(x) are measurable. The existence of a measurable mapping (often called a “selector”) implies that 𝔸(x) ≠ ∅ for all x. We remark that it is possible that the graph is Borel and all images are non-empty but the graph does not contain a Borel mapping. Therefore, the second assumption in (ii) is essential for the existence of at least one policy.

As was discussed above, the first real complication is that even for onestep problems, the values V may not be Borel measurable functions on 𝕏. However, conditions (i)-(iii) imply that these functions are universally measurable for finite and infinite-horizon problems and therefore optimality operators can be defined.

Here we explain the concepts of universally measurable sets and functions. Let (E, E) be a Borel space. For a given probability measure p on (E, E), define a σ-field E_{p} which is a completion of E with respect to measure p. That is, E_{p} is the minimal σ-field that contains E and all subsets F of E such that F ⊂ F′ for some F′ ∈ E, and p(F′) = 0. For example, if (E, E) = ([0, 1], B([0, 1])) then we can consider the Lebesgue measure m defined by m([a, b]) = |b − a|. Then E_{m} is the so-called Lebesgue σ-field. Let P(E) be the set of all probability measures on E. Then the intersection of all σ-fields E_{p}, U(E) = ∩_{{p∈P(E)}}E_{p}, is a σ-field and it is called the universal σ-field. This σ-field is also called the σ-field of universally measurable sets and its elements are called universally measurable subsets of E. A universally measurable function on X is a measurable mapping from (X, U(X)) to (ℝ, B(ℝ), where U(X) is a universal σ-field on X. Of course, any Borel set and any Borel function are universally measurable.

Thus, optimality equations can be defined for Borel MDPs. However, there is another complication for Borel models, which is annoying mostly for aesthetic reasons: ϵ-optimal policies may not exist for small positive ϵ, even for one-step Borel MDPs with bounded reward functions. The example constructed by David Blackwell is based on the observation that the value function is universally measurable but it may not be Borel. However, for any policy, the expected one-step reward is a Borel function of the initial step. Moreover, it is possible to show that for the Borel MDP described above, for any initial measure p on 𝕏, and for any ϵ > 0 there exists a policy which is p − a.s. ϵ-optimal. Such policies are called (p, ϵ)-optimal.

Universally measurable Borel MDPs. If we expand the set of policies and consider universally measurable policies, ϵ-optimal policies exist and the concept of (p, ϵ) optimality is not needed. However, if we expand the set of policies, the results and their proofs hold for assumptions which are broader than (ii) and (iii).

Before we give formal definitions, we explain the concept of analytic sets. Let f is a measurable mapping of a Borel space (E_{1}, E_{1}) into Borel x space (E, E). If F ∈ E then by definition f^{−1}(F) ∈ E_{1}. However, it is possible that f(E) ∉ E for some Borel set F ∈ E_{1}. A subset F of a Borel space (E, E) is called analytic if there exists a Borel space (E_{1}, E_{1}) and a measurable mapping of E_{1} to E such that F = f(F_{1}) for some F_{1} ∈ E_{1}.

Since one can select E_{1} = E and f(e) = e, every Borel set is analytic. It is also possible to show that any analytic set is universally measurable. It is also possible to consider the σ-field of analytically measurable sets which is the smallest σ-field containing all analytic subsets of an analytic set. We remark that Borel and universally measurable σ-fields consist respectively of Borel and universally measurable sets. The situation is different for analytic sets and σ-fields of analytically measurable sets. The complement of an analytic set may not be analytic. Therefore, the σ-field of analytically measurable sets contains sets other than analytic. We remark that there are many equivalent definitions of analytic sets. For example, for Polish spaces they can be defined as continuous images or even as projections of Borel sets.

If (E, E) and (E_{1}, E_{1}) are two Borel spaces (Borel sets with Borel σ-fields) then the mapping f : E → E_{1} is called universally (analytically) measurable if f^{−1}(B) belongs to the σ-field of universally (analytically) measurable subsets of E.

The assumptions for universally measurable MDPs are:

(a) The state and action spaces (𝕏, X) and (𝔸, A) are Borel spaces;

(b) Gr 𝔸(x) is an analytic subset of 𝕏 × 𝔸 and all sets 𝔸(x) are not empty;

(c) The reward function r(x, a) is an upper analytic function on 𝕏 × 𝔸, that is, for any real number c, the set {r ≥ c} is an analytic subset of 𝕏 × 𝔸;

(d) The transition function p(·|x, a) is a regular transition probability from (𝕏 × 𝔸, X × A)to (𝕏, X).

Assumptions (a) and (d) coincide with similar assumptions for Borel MDPs. According to Jankov–von Neumann theorem, assumption (b) implies that there is an analytically measurable mapping ϕ from 𝕏 to 𝔸 such that ϕ(x) ∈ 𝔸(x) for all x ∈ 𝕏. Of course, any analytically measurable mapping is universally measurable. Assumption (c) is more general than the assumption that r(x, a) is Borel. This generality is unimportant. It is kept in the literature just because the same proofs holds for upper analytic and Borel reward functions.

The last important difference between Borel and universally measurable MDPs is that policies are universally measurable for the latter ones. Nonrandomized policies are universally measurable mappings ϕ_{n} of H_{n} to 𝔸 such that ϕ(h_{n}) ∈ 𝔸(x_{n}) for any h_{n} = x_{0}a_{n} … x_{n} ∈ H_{n}. Markov (and stationary) policies are defined by universally measurable mappings ϕ_{n} of 𝕏 to 𝔸 such that ϕ_{n}(x) ∈ 𝔸(x) (ϕ(x) ∈ 𝔸(x)) for all x ∈ 𝕏. Randomized, randomized Markov, and randomized stationary policies are regular transition probabilities defined in the same way as for general models but the sets H_{n} and 𝕏 are endowed with σ-fields of universally measurable subsets that play the role of σ-field E_{1} in the definition of regular transition probabilities given above. Condition (b) implies that there exists at least one policy.

There are other versions of universally measurable MDPs. For example, one can consider analytically measurable policies; see Bertsekas and Shreve \underline{bs} [1] for details. The important feature is that all definitions and notations, given for discrete MDPs, hold also for universally measurable MDPs.

1.3 What’s in this volume

To be written.

Bibliography

bs [1] [BertShr] D. P. Bertsekas and S. E. Shreve,“Stochastic Optimal Control: The Discrete-Time Case,” Academic Press, New York, 1978 (republished by Athena Scientific, 1997).

chung [2] [Chung] K. L. Chung, “Markov Chains with Stationary Transition Probabilities,” Springer-Verlag, Berlin, 1960.

dy [3] [DynYsh] E. B. Dynkin and A. A. Yushkevich, “Controlled Markov Processes,” Springer-Verlag, New York, 1979 (translation from 1975 Russian edition).

ke [4] [Kechris] A. S. Kechris, “Classical Descriptive Set Theory,” Springer-Verlag, New York, 1995.

ne [5] [Ne] J. Neveu, “Mathematical Foundations of the Calculus of Probability,” Holden-Day, San Francisco, 1965.

Index

action available, 1 space, 1

action space, 1

constrained optimization optimal, 6

deterministic policy, 2

feasible, 6

history, 2, 2

Markov Decision Process, 1

optimal, 6 optimality equation, 4

average reward, 5 discounted reward, 4 finite horizon, 4 first, 5 second, 5

performance, 5 policy, 2

feasible, 6 randomized, 2

policy space, 2 pure policy, 2

reward, 1 discounted, 3 expected total, 3 one step, 1 terminal, 3

space action, 1 available actions, 1 policy, 2 state, 1 state space, 1

trajectory, 2

transition probability, 1