Markov Decision Processes

Lodewijk Kallenberg Leiden University The Netherlands

May 28, 2000

Chapter 1

Finite state and action MDPs

ch:finite

Abstract

In this chapter we study Markov decision processes (MDPs) with finite state and action spaces. This is the classical theory developed since the end of the fifties. We consider finite and infinite horizon models. For the finite horizon model the utility function of the total expected rewards is commonly used. For the infinite horizon the utility function is less obvious. We consider several criteria: total discounted expected rewards, average expected rewards and more sentitive optimality criteria including the Blackwell optimality criterion. We end with a variety of other subjects. The emphasis is on computational methods to compute optimal policies for these criteria. These methods are based on concepts like value iteration, policy iteration and linear programming. This survey covers about three hundred papers. Although the subject of finite state and action MDPs is classical, there are still open problems. We also mention some of them.

1.1 Introduction

1.1.1 Origin

Bellman’s book ^{\underline{be}} [13], can be considered as starting point of Markov decision processes (MDPs). However, already in 1953, Shapley’s paper ^{\underline{sh}} [222] on stochastic games includes as a special case the value iteration method for MDPs, but this was recognized only later on. About 1960 the basics for the other computational methods (policy iteration and linear programming) were developed in publications like Howard ^{\underline{ho60}} [122], De Ghellinck ^{\underline{degh60}} [42], D’Epenoux^{\underline{depn60}} [55], Manne ^{\underline{manne60}} [165] and Blackwell ^{\underline{bl62}} [27]. Since the early sixties, many results on MDPs are published in numerous journals, monographs, books and proceedings. Over thousand papers were published in scientific journals. There are about fifty books on MDPs. Around 1970 a first series of books was published. These books (e.g. Derman ^{\underline{der70}} [58], Hinderer ^{\underline{hin70}} [107], Kushner ^{\underline{kush71}} [149], Mine and Osaki ^{\underline{mine70}} [168] and Ross ^{\underline{ross70}} [199] contain the fundamentals of the theory of finite MDPs. Since that time nearly every year one or more MDP-books appeared. These books cover special topics (e.g. Van Nunen ^{\underline{nunen76b}} [251], Van der Wal ^{\underline{wal81}} [247], Kallenberg ^{\underline{kal83}} [135], Federgruen ^{\underline{fed84}} [69], Vrieze ^{\underline{vrieze87}} [261], Hernández-Lerma ^{\underline{her89}} [102], Altman ^{\underline{alt99}} [2] and Sennott ^{\underline{sen99}} [219] or they deal with the basic and advanced theory of MDPs (e.g. Bertsekas ^{\underline{bertse76a}} [15], Whittle ^{\underline{whittle82a}} [290], ^{\underline{whittle82b}} [291], Ross ^{\underline{ross83}} [201], Dietz and Nollau ^{\underline{dietz83}} [63], Bertekas ^{\underline{bertse87}} [17], Denardo ^{\underline{den82}} [50], Heyman and Sobel ^{\underline{hey84}} [106], White ^{\underline{white932}} [286], Puterman ^{\underline{put94}} [187], Bertsekas ^{\underline{bertse95a}} [18], ^{\underline{bertse95b}} [19], Hernández-Lerma and Lasserre ^{\underline{her96}} [103], ^{\underline{her99}} [104], and Filar and Vrieze ^{\underline{filar97}} [79].

1.1.2 The model

We will restrict ourselves to discrete, finite Markovian decision problems, i.e. the state space E and the action spaces A(i), i ∈ E, are finite, and the decision time points t are equidistant, say t = 1, 2, . . .. If, at time point t, the system is in state i and action a ∈ A(i) is chosen, then the following happens independently of the history of the process:

(1) a reward r_{i}(a) is earned immediately;

(2) the process moves to state j ∈ E with transition probability p_{ij}(a), where p_{ij}(a) ≥ 0 and Σ_{j}p_{ij}(a) = 1 for all i, j and a.

The objective is to determine a policy, i.e. a rule at each decision time point, which optimizes the performance of the system. This performance is expressed as a certain utility function. Such utility function may be the expected total (discounted) rewards over the planning horizon or the average expected reward per unit time. The decision maker has to find the optimal balance between immediate rewards and future rewards: a high immediate reward may bring the process in a bad situation for later rewards.

A policy R is a sequence of decision rules: R = (π^{1}, π^{2}, …, π^{t}, …), where π^{t} is the decision rule at time point t. The decision rule at time point t may depend on ”all information” of the system until time t, i.e. on the states at the time points 1, 2, …, t and on the actions at the time points 1, 2, …, t − 1. A formal definition of a decision rule is stated below.

Let ExA = {(i, a) | i ∈ E, a ∈ A(i)} and let H_{t} denote the set of the possible histories of the system up to time point t, i.e.

H_{t} ={(i_{1}, a_{1}, …, i_{t−1}, a_{t−1}, i_{t})|(i_{k}, a_{k})∈E ×A, 1 ≤ k ≤ t−1; i_{t} ∈ E}. (1.1)

A decision rule π^{t} at time point t gives the probability, as function of the history H_{t} to the action space, of choosing action a_{t} i.e. π_{h_{t}}^{t}(a_{t}) ≥ 0 for every a_{t} ∈ A(i_{t}) and Σ_{a_{t}}π_{h_{t}}^{t}(a_{t}) = 1 for every h_{t} ∈ H_{t}.

A policy R = (π^{1}, π^{2}, …, π^{t}, …) is said to be memoryless if the decision rule π^{t} is independent of (i_{1}, a_{1}, …, i_{t−1}, a_{t−1}) for every t ∈ ℕ. Hence, in a memoryless policy the decision rule at time t only depends on the state i_{t}. Memoryless policies are also called Markov policies. If a policy is memoryless and the decision rules are independent of the time point, i.e. π^{1} = π^{2} = ⋯, then the policy is called a stationary policy. We will denote the stationary policy R = (π, π, …) by π^{∞}. If the decision rule π of a stationary policy π^{∞} is nonrandomized, then the policy is called deterministic. A deterministic policy can be described by a function f on E such that f(i) is the action chosen in state i, i ∈ E. A deterministic policy will be denoted by f^{∞}.

Any policy R and any initial distribution β, i.e. β_{i} is the probability that the system starts in state i, induce - by a theorem of Ionescu Tulcea (cf. Bertsekas and Shreve ^{\underline{bertse78}} [22]) - a probability measure ℙ_{β,R} on H_{∞}, where

H_{∞} = {(i_{1}, a_{1}, i_{2}, a_{2}, …) | (i_{k}, a_{k}) ∈ E × A, k = 1, 2, … }.  (1.2)

Let the random variables X_{t} and Y_{t} denote the state and action at time t(t = 1, 2, …) and let ℙ_{β,R}[X_{t} = j, Y_{t} = a] be the notation for the probability that at time t the state is j and the action is a, given that policy R is used and β is the initial distribution. The next theorem shows that for any initial distribution β, any sequence of policies R_{1}, R_{2}, … and any convex combination of the marginal distributions of ℙ_{β,R_{k}}, k ∈ ℕ, there exists a Markov policy R which has the same marginal distribution.

Theorem 1 Given any initial distribution β, any sequence of policies R_{1}, R_{2}, … and any sequence of nonnegative real numbers p_{1}, p_{2},... with Σ_{k}p_{k} = 1, there exists a Markov policy R_{∗} such that for every (j, a) ∈ E × A

ℙ_{β,R_{∗}}[X_{t} = j, Y_{t} = a] = Σ_{k}p_{k} · ℙ_{β,R_{k}}[X_{t} = j, Y_{t} = a], t ∈ ℕ.  (1.3)

Corollary 2 For any starting state i and any policy R, there exists a Markov policy R_{∗} such that

ℙ_{i,R_{∗}}[X_{t} = j, Y_{t} = a] = ℙ_{i,R}[X_{t} = j, Y_{t} = a], t ∈ ℕ, (j, a) ∈ E × A. (1.4)

The results of Theorem 1 and Corollary 2 imply the sufficiency of Markov policies for performance measures which only depend on the marginal distributions. Corollary 2 is due to Derman and Strauch ^{\underline{der66}} [61] and the extension to theorem 1 was given by Strauch and Veinott ^{\underline{str}} [238]. The result is further generalized to more general state and actions spaces by Hordijk ^{\underline{hor74}} [112] and Van Hee ^{\underline{hee78}} [248].

1.1.3 Optimality criteria

Let v_{i}(R) be the utility function if policy R is used and state i is the starting state, i ∈ E. The value vector v of this utility function is defined by

v_{i} = sup_{R} v_{i}(R), i ∈ E.  (1.5)

A policy R is an optimal policy if v_{i}(R) = v_{i}, i ∈ E. In Markov decision theory the existence and the computation of optimal policies is studied. For this purpose a so-called optimality equation is derived, i.e. a functional equation for the value vector. Then a solution of this equation is constructed which produces both the value vector and an optimal policy. There are three standard methods to perform this: value iteration, policy iteration and linear programming.

In value iteration the optimality equation is solved by successive approximation. Starting with some v^{0}, v^{t+1} is computed from v^{t}, t = 0, 1, . . .. The sequence v^{0}, v^{1}, … converges to the solution of the optimality equation. In policy iteration a sequence of improving policies f_{0}^{∞}, f_{1}^{∞}, … is determined, i.e. v(f_{t+1}^{∞}) ≥ v(f_{t}^{∞}) for all t, until an optimal policy is reached. The linear programming method can be used because the value vector is the smallest solution of a set of linear inequalities; an optimal policy can be obtained from its dual program.

In this survey we consider the following utility functions:

(1) total expected rewards over a finite horizon;

(2) total expected discounted rewards over an infinite horizon;

(3) average expected rewards over an infinite horizon;

(4) more sensitive optimality criteria for the infinite horizon.

Suppose that the system has to be controlled over a finite planning horizon of T periods. As performance measure we use the total expected rewards over the planning horizon, i.e. for policy R we will consider for starting state i

v_{i}^{T} (R) = Σ_{t=1}^{T}𝔼_{i,R}[r_{X_{t}}(Y_{t})] = Σ_{t=1}^{T}Σ_{j,a}ℙ_{i,R}[X_{t} = j, Y_{t} = a] · r_{j}(a). (1.6)

A matrix P = (p_{ij}) is called a transition matrix if p_{ij} ≥ 0 for all (i, j) and Σ_{j} p_{ij} = 1 for all i. Markov policies, and consequently also stationary and deterministic policies, induce transition matrices. For the Markov policy R = (π^{1}, π^{2}, …) we define, for every t ∈ ℕ, the transition matrix P (π^{t}) by

[P (π^{t})]_{ij} = Σ_{a}p_{ij}(a)π_{i}^{t}(a) for all i, j ∈ E,  (1.7)

and the reward vector r(π^{t}) by

r_{i}(π^{t}) = Σ_{a}π_{i}^{t}(a)r_{i}(a) for all i ∈ E.  (1.8)

Hence the total expected rewards can be written in vector notation as

v^{T} (R) = Σ_{t=1}^{T}P (π^{1})P (π^{2}) ⋯ P (π^{t−1})r(π^{t}).  (1.9)

It can be shown (we refer to section 2) that an optimal Markov policy R_{∗} = (f_{∗}^{1}, f_{∗}^{2}, …, f_{∗}^{T}) exists, where f_{∗}^{t} is a deterministic decision rule 1 ≤ t ≤ T. Such policy is called nonstationary deterministic. The nonstationarity is due to the finiteness of the planning horizon.

Next, we consider an infinite planning horizon. In that case there is not a unique optimality criterion. Different optimality criteria are meaningful: discounted rewards, total rewards, average rewards or more sensitive criteria. In the discounted reward criterion an amount r that is obtained at time point 1 has at time point 2 the value (1 + ρ) · r, at time point 3 the value (1+ρ)^{2}·r, etc., where ρ is the interest rate. In the discounted reward criterion the rewards are considered as earned at time point 1. Therefore, the reward r_{X_{t}}(Y_{t}) at time point t has at time point 1 the discounted value α^{t−1}r_{X_{t}}(Y_{t}), where α = (1 + ρ)^{−1}.α is called the discount factor and 0 < α < 1.

The total expected α-discounted reward, given initial state i and policy R, is denoted by v_{i}^{α}(R) and defined by

\begin{aligned}v_{i}^{α}(R) & = Σ_{t=1}^{∞}𝔼_{i,R}[α^{t−1}r_{X_{t}}(Y_{t})] \\ & = Σ_{t=1}^{∞}α^{t−1}Σ_{j,a}ℙ_{i,R}[X_{t} = j, Y_{t} = a]r_{j}(a). \end{aligned}  (1.10)

In section 3 it will be shown that there exists an optimal deterministic policy and that any stationary policy π^{∞}, and therefore also any deterministic policy, satisfies

v^{α}(π^{∞}) = Σ_{t=1}^{∞}α^{t−1}P (π)^{t−1}r(π) = [I − αP (π)]^{−1}r(π).  (1.11)

When there is no discounting, i.e. the discount factor α equals 1, then - for instance - we may consider the total expected reward and the average expected reward criterion. In the total expected reward criterion the utility function is Σ_{t=1}^{∞} 𝔼[r_{X_{t}}(Y_{t})]. However, this infinite sum does not exist, in general. When the average reward criterion is used, the limiting behaviour of the expectation of \frac{1}{T} Σ_{t=1}^{T} r_{X_{t}}(Y_{t}) is considered. Since lim_{T →∞} \frac{1}{T} Σ_{t=1}^{T} 𝔼[r_{X_{t}}(Y_{t})] or 𝔼[lim_{T →∞} \frac{1}{T} Σ_{t=1}^{T} r_{X_{t}}(Y_{t})] does not exist, in general, and interchanging limit and expectation may not be allowed, there are four different evaluation measures, which can be considered for a given policy:

(a) the lower limit of the average expected reward:

ϕ_{i}(R) = lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}𝔼_{i,R}[r_{X_{t}}(Y_{t})], i ∈ E;  (1.12)

(b) the upper limit of the average expected reward:

Φ_{i}(R) = lim sup_{T →∞} \frac{1}{T} Σ_{t=1}^{T}𝔼_{i,R}[r_{X_{t}}(Y_{t})], i ∈ E;  (1.13)

(c) the expectation of the lower limit of the average reward:

Ψ_{i}(R) = 𝔼_{i,R}[lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}r_{X_{t}}(Y_{t})], i ∈ E;  (1.14)

(d) the expectation of the upper limit of the average reward:

Ψ_{i}(R) = 𝔼_{i,R}[lim sup_{T →∞} \frac{1}{T} Σ_{t=1}^{T}r_{X_{t}}(Y_{t})], i ∈ E.  (1.15)

Lemma 3 (i) ψ(R) ≤ ϕ(R) ≤ Φ(R) ≤ Ψ(R) for every policy R; (ii) ψ(π^{∞}) = ϕ(π^{∞}) = Φ(π^{∞}) = Ψ(π^{∞}) for every stationary policy π^{∞}.

Remark In Bierth ^{\underline{bier}} [26] is shown that the four citeria are equivalent in the sense that the value vectors can be attained for one and the same deterministic policy. Examples can be constructed in which for some policy R the inequalities of Lemma 3 part (i) are strict.

The long-run average reward criterion has the disadvantage that it does not consider rewards earned in a finite number of periods: the streams of rewards 0, 0, 0, 0, 0, … and 100, 100, 0, 0, 0, … are measured as the same. Hence, there may be a preference for more selective criteria. There are several ways to be more selective. One way is to consider discounting for discount factors that tend to 1. Another way is to use more subtle kinds of averaging. We will present some criteria and results. For all criteria it can be shown that deterministic optimal policies exist and that these policies are (at least) average optimal.

A policy R_{∗} is called bias-optimal if lim_{α↑1}[v^{α}(R_{∗}) − v^{α}] = 0 and Blackwell optimal if v^{α}(R_{∗}) = v^{α} for all α ∈ [α_{0}, 1) for some α_{0}. These two criteria are special cases of a class of criteria called n-discount optimality,for n = −1, 0, 1, . . ..

A policy R_{∗} is called n-discount optimal if lim_{α↑1}(1−α)^{−n}[v^{α}(R_{∗}) − v^{α}] = 0. Obviously, 0-discount optimal is the same as bias-optimal. One can show that (-1)-discount optimality is equivalent to average optimality, and that Blackwell optimality is n-discount optimality for all n ≥ N − 1, where N = #E. In this chapter we will always use the notation N for the number of states.

There is also the concept of n-average optimality. For any policy R, t ∈ ℕ and n = −1, 0, 1, …, let the vector v^{n,t}(R) be defined by

v^{n,t}(R) = \{ \begin{matrix}v^{t}(R) & for & n = −1 \\ Σ_{s=1}^{t}v^{n−1,s}(R) & for & n = 0, 1 … \end{matrix}  (1.16)

R_{∗} is said to be n-average optimal if lim inf_{T →∞} \frac{1}{T} [v^{n,T} (R_{∗}) − v^{n,T} (R)] ≥ 0 for all policies R. (-1)-average optimality is equivalent to average optimality. Furthermore, it can be shown that for all n ∈ {−1, 0, … } n-average optimality is equivalent to n-discount optimality. In a fundamental paper Blackwell ^{\underline{bl62}} [27] presented a mathematical rigorous proof for the policy iteration method to compute an α-discounted optimal policy. He also introduced the concept of bias-optimality (Blackwell called it nearly optimality) and established the existence of a discounted optimal policy for all discount factors sufficiently close to 1. In honour of Blackwell, such policy is called a Blackwell optimal policy. The n-discount optimality criterion, and the policy iteration method for finding an n-discount optimal policy, was proposed by Veinott ^{\underline{vei69}} [258]. He also showed that Blackwell optimality is the same as n-discount optimality for n ≥ N −1. Sladky ^{\underline{sla}} [224] has introduced the concept of n-average optimality; furthermore, he also showed the equivalence between this criterion and the n-discount optimality.

1.1.4 Applications

White has published three papers on ’real applications’ of Markov decision theory (White ^{\underline{white85}} [281], ^{\underline{white881}} [282] and ^{\underline{white931}} [285]. We also mention Lamond’s chapter in this book on water reservoir applications. Many problems can be formulated as MDPs. In this section we shortly introduce the following examples: routing problems, stopping and target problems, replacement problems, maintenance and repair problems, inventory problems, the optimal control of queues, stochastic scheduling and multi-armed bandit problems. In this book there are also chapters on applications in finance (by Schäl) and in telecommunication (by Altman).

Routing problems In routing problems the problem is to find an optimal route through a network. Well known is the deterministic shortest path problem. Consider a layered network, i.e. the nodes V are partitioned into V_{1} = {v_{1}}, V_{2}, ⋯, V_{m−1}, V_{m} = {v_{n}}, and if (i, j) is an arc then i ∈ V_{k} and j ∈ V_{k+1} for some 1 ≤ k ≤ m−1. In the shortest path problem one has to find the (length of the) shortest path from node v_{1} to node v_{n}. This problem can be modelled as an MDP with a finite horizon (m stages). The state space E consists of the nodes; the action set A(i) in state i corresponds to the arcs with starting point node i; the transitions are deterministic: p_{ij}(a) = 1 if action a corresponds to the arc (i, j), and the length l_{ij} is considered as cost when in state i action (i, j) is chosen, i.e. r_{i}(a) = − l_{ij} if action a = (i, j). Let u_{i} be the minimum distance from state i to the destination v_{n}. Then, by the principle of optimality, we obtain the so-called optimality equation for the shortest path problem, i.e. u_{i} = min{l_{ij} + u_{j}|(i, j) ∈ A}, i ≠ n; u_{n} = 0. u_{1} is the solution of the shortest path problem. There is also a stochastic version of the shortest path problem.

Another application of this kind is the maximum reliability problem. In this network the (direct) connections are unreliable: let p_{ij} be the probability of reaching node j when the arc from node i to node j is chosen. The objective is to obtain the maximum probability of reaching a terminal node n when starting from node 1. Let P be a path from node 1 to node n. Notice that ℙ(P), the probability to reach n from 1 when path P is chosen, satisfies ℙ(P) = Π_{(i,j)∈P} p_{ij} and that max_{P} ℙ(P) is equivalent to max_{P} [log{ℙ(P)}] which in turn is equivalent to min_{P} [-log{ℙ(P)}]. Since log{ℙ(P)} = Σ_{(i,j)∈P} log[p_{ij}] the maximum reliability problem is equivalent to the shortest path problem with l_{ij} = -log[p_{ij}]. Results for the stochastic version of the shortest path problem can for instance be found in Bertsekas and Tsitsiklis ^{\underline{bertse91}} [23]. The maximum reliability problem is discussed in Roosta ^{\underline{roo}} [195]. We also mention White’s chapter in this book on transportation applications.

Optimal stopping problems In an optimal stopping problem there are two actions in each state. The first action is the stopping action and the second action corresponds to continue. If we continue in state i, a cost c_{i} is incurred and the probability of being in state j at the next time point is p_{ij}. If the stopping action is chosen in state i, then a(final) reward r_{i} is earned and the process terminates. In an optimal stopping problem, in each state one has to determine which action is chosen with respect to the total expected reward criterion. An example of an optimal stopping problem is the house selling problem (see Ross ^{\underline{ross70}} [199]). At the beginning of each period a decision has to be taken whether to sell the house for the best offer so far, or to wait for another period (when the house is unsold there are maintenance costs for the next period). We assume that the numbers p_{j} are known, where p_{j} is the probability of an offer j during a period (these probabilities are stationary, i.e. they are independent of the period). This house selling problem can be modelled as an optimal stopping problem with the following state descrition: state i means that the best offer so far is i. Selling the house corresponds to the stopping action; otherwise we continue and have probability p_{j} for a transition from state i to state j > i and the transition probability from i to i is equal to Σ_{j≤i} p_{j}. For this kind of problems it can be shown that a control limit policy is optimal (i.e. sell the house at the first offer of at least i_{∗} for a certain amount i_{∗}). It is possible to derive an explicit expression for i_{∗}. The original analysis of optimal stopping problems appeared in Derman and Sacks ^{\underline{der60}} [60], and Chow and Robbins ^{\underline{chow}} [36]. A dynamic programming approach can be found in Breiman ^{\underline{brei}} [28] who showed the optimality of control limit policies. We refer also to Sonin’s chapter in this book.

Target problems In a target problem one wants to reach a distinguished state (or a set of states) in some optimal way, where in this context optimal means e.g. at minimum cost or with maximum probability. The target states are absorbing, i.e. there are no transitions to other states and the process can be assumed to terminate in the target states. These target problems can be modelled as MDPs with the total expected reward as optimality criterion. To the class of target problems we may count the first passage problem. In this problem there is one target state and the objective is to reach this state (for the first time) at minimum cost. We assume that the costs are positive. It is easy to see that the first passage problem is equivalent to this MDP. A second class of target problems are the gambling problems (the gambler’s goal is to reach a certain fortune N and the problem is to determine a policy which maximizes the probability to reach this goal). For more information about MDPs and gambling problems we refer to Maitra and Sudderth’s chapter in this book. The first passage problem was introduced by Eaton and Zadeh ^{\underline{eaton}} [67] under the name ”pursuit problem”. The dynamic programming approach is introduced in Derman ^{\underline{der62}} [56]. The standard reference on gambling is Dubins and Savage ^{\underline{dubins}} [64]. Dynamic programming approaches are given in Ross ^{\underline{ross74}} [200] and Dynkin ^{\underline{dyn}} [66].

Replacement problems Consider an item which is in a certain state. The state of the item describes its condition. Suppose that in each period, given the state of the item, the decision has to be made whether or not to replace the item by a new one. When an item of state i is replaced by a new one, the old item is selled at price s_{i}, a new item is bought at price c, and the transition to the new state is instantaneously. In case of nonreplacement, let p_{ij} be the probability that an item of state i is at the beginning of the next period in state j, and suppose that c_{i} is the maintenance cost - during one period - for an item of state i. This problem can be modelled as an MDP. It turns out that an efficient algorithm for the computation of an optimal policy exists, the so-called myopic algorithm with complexity O(N^{3}), see Gal ^{\underline{gal}} [83]. Next, we consider the model deterioration with failure. In this model the states are interpreted as ’ages’. In state i there is a failure probability p_{i} and, when failure occurs, there is an extra cost f_{i} and the item has to be replaced by a new one. If there is no failure the next state is state i + 1. It can be shown that, under very natural assumptions about the failure probabilities and the costs, a control limit policy is optimal, i.e. there is an age i_{∗} and the item is replaced by a new one if its age exceeds i_{∗}. This structural property holds for the discounted reward criterion as well as for the average reward criterion. There are a lot of references on replacement models. The early survey of Sherif and Smith ^{\underline{she}} [223] contained already over 500 references. Results on the optimality of control limit policies for replacement problems can be found in Derman ^{\underline{der63}} [57], Kolesar ^{\underline{kol}} [147], Derman ^{\underline{der70}} [58], Ross ^{\underline{ross70}} [199] and Kao ^{\underline{kao}} [139].

Maintenance and repair problems In maintenance and repair problems there is a system which is subject to deterioration and failure. In each period the state of the system is observed. Usually, the state is a characterization of the condition of the system. When the state is observed, an action has to be chosen, e.g. to keep the system unchanged, to execute some maintenance or repair, or to replace one or more components by new ones. Each action has corresponding costs (total costs, discounted costs or average costs) over a finite or infinite horizon. As an example of a repair problem, consider a system with two components in series. Each component may be either in a functioning or a failed state. At the end of a period a functioning component may be in a failed state with probability p. For the production of one unit operations on both components are needed. When both components are functioning (at the begin of the period) a good unit is produced; if one of the components has failed, then a good unit is produced with probability q; if both components have failed the unit is defective. After inspection of the state of the components, there are the following possible actions:

- if both components are functioning: do nothing;

- if one component has failed: either do nothing or repair the component;

- if both components have failed: either repair one component or repair both components.

The repair of a component costs c and the production of a good unit gives a reward r. The objective is to maximize the average reward over an infinite horizon. This problem can easily be modelled as an MDP. The one-component problem is described in Klein ^{\underline{klein}} [146]. The two-component maintenance problem was introduced by Vergin and Scriabin ^{\underline{ver}} [260]. Other contributions in this area are e.g. Oezekici ^{\underline{oez}} [174], and Van der Duyn Schouten and Vanneste ^{\underline{duyn}} [245]. An n-component series system is discussed in Katehakis and Derman ^{\underline{kate84}} [140]. Asymptotic results for highly reliable systems can be found in Smith ^{\underline{smi}} [227], Katehakis and Derman ^{\underline{kate89}} [141], and Frostig ^{\underline{frost}} [81].

Inventory problems In inventory problems an optimal balance between inventory costs and ordering costs has to be determined. We assume that the probability distribution of the demand is known. There are different variants of the inventory problem. They differ, for instance, in the following aspects:

- stationary or nonstationary costs and demands;

- a finite planning horizon or an infinite planning horizon;

- backlogging or no backlogging. For all these variants different performance measures may be considered. As an example we will describe an inventory model with backlogging. At the start of each week the inventory manager observes the inventory and decides how many units to order. We assume that orders are delivered instantaneously, and that there is a finite inventory capacity of B. Let D be the stochastic demand during one week and let ℙ[D = j] be denoted by p_{j}, 0 ≤ j ≤ M. If the demand during a period excesses the inventory on hand, then the shortage is backlogged in the next period. If the inventory at the beginning of a week is i (shortages are modelled as negative inventory), the number of units ordered is a and the inventory at the end of the week is j, then the following costs are involved:

Ordering costs : K · δ(a) + k · a, where δ(a) = \{ \begin{matrix}1 & if & a ≥ 1 \\ 0 & if & a ≤ 0 \end{matrix}

Inventory costs : h · δ(j) · j; backlogging costs : q · δ(−j) · (−j).

The data K, k, h, q and p_{j}, 0 ≤ j ≤ M are known. This inventory problem can be modelled as an MDP with:

E = {−M, …, −1, 0, 1, …, B}; A(i) = {a ≥ 0|0 ≤ i + a ≤ B};

p_{ij}(a) = \{ \begin{matrix}p_{i+a−j} & j ≤ i + a \\ 0 & j > i + a \end{matrix} i, j ∈ E, a ∈ A(i);

\begin{aligned}r_{i}(a) = −[K · δ(a) + k · a & + Σ_{j=0}^{i+a}p_{j} · h · (i + a − j) \\ & + Σ_{j=i+a+1}^{M}p_{j} · q · (j − i − a)] \end{aligned}

In many inventory models the optimal policy is of (s, S)-type, i.e. when the inventory is smaller than or equal to s, then replenish the stock to level S. The existence of optimal (s, S)-policies in finite horizon models with fixed cost K is based on the so-called K-convexity, introduced by Scarf ^{\underline{sca}} [203]. The existence of an optimal (s, S)-policy in the infinite horizon model is shown by Iglehart ^{\underline{igle}} [127]. Another related paper is Veinott ^{\underline{vei66a}} [256]. For the relation between discounted and average costs we refer to Hordijk and Tijms ^{\underline{hor75}} [120]. For the computation of the values s and S we refer to papers like Federgruen and Zipkin ^{\underline{fedzip84}} [76], and Zheng and Federgruen ^{\underline{zhe}} [293].

Optimal control of queues Consider a queueing system where customers arrive according to a Poisson process and where the service time of a customer is exponentially distributed. Suppose that the arrival and service rates can be controlled by a finite number of actions. When the system is in state i, i.e. there are i customers in the system, action a means that the arrival or the service rates are λ_{i}(a) or μ_{i}(a), respectively. The arrival and service processes are continuous-time processes. However, by the memoryless property of the exponential distribution, we can find an embedded discrete-time Markov chain which is appropriate for our analysis. This technique is called uniformization (see e.g. Tijms ^{\underline{ty}} [242]). A queue, or a network of queues, is a useful model for many applications, e.g. manufacturing, computer, telecommunication and traffic systems. Control models can optimize certain performance measures by varying the control parameters of the system. We distinguish between admission control and service rate control. As an example of admission control, consider an M/M/1 queue where customers arrive as a Poisson process and the service time is exponential. One has the option to reject an arrival. However, a cost c must be paid for each rejection. Furthermore, there are holding costs h per period for each customer in the system. Hence, in an optimal situation there is a balance between rejection of new customers and congestion of customers in the system. Assume that the total expected discounted costs have to be minimized. It can be shown that there is a control limit or threshold policy which is optimal, i.e. there is a value i_{∗} and an arriving new customer is rejected if there are more than i_{∗} customers in the system. For details we refer to Walrand ^{\underline{wal}} [266]. In a service rate model, the service rate can be chosen from an interval [0, μ̄]. If rate μ is chosen, there are service costs c(μ) per period; we also assume that there are holding costs h(i) per period when there are i customers in the system. Under natural conditions it can be shown that a bang-bang policy is optimal, i.e. μ = 0 or μ = μ̄. For details see Weber and Stidham ^{\underline{web87}} [269]. Surveys of optimal control of (networks of) queues can be found in the book by Walrand ^{\underline{wal}} [266] and the papers by Stidham ^{\underline{stid85}} [235] and Stidham and Weber ^{\underline{stid93}} [236].

Stochastic scheduling In a scheduling problem, jobs are processed on machines. Each machine can process only one job at a time. A job has a given processing time on the machines. In stochastic scheduling, these processing times are random variables. At certain time points decisions have to be made, e.g. which job is assigned to which machine. There is a utility function by which different policies can be measured, and we want to find a policy that optimizes the utility function. Such problems are also considered in the control of queueing systems. Then, instead of jobs and machines, the terms customers and servers are frequently used. There are two types of models: the customer assignment models, in which each arriving customer has to be assigned to one of the queues (each queue with its own server) and server assignment models, where the server has to be assigned to one of the queues (each queue has its own customers). As a first example we consider one server allocation (with preemption) to parallel queues. Customers arrive at a system of m parallel queues and one server. The system operates at discrete time points, i.e. arrival times and service times have values in the set {1, 2, … }. Furthermore, the arrival times are arbitrary and the service time T_{i}, for a customer in queue i, is geometrically distributed with rate μ_{i}, which implies that 𝔼[T_{i}] = μ_{i}^{−1}. At any time point the server chooses a customer from one of the queues; so, this is a server assignment model. Services which are going on may be interrupted and resumed later on (preemption). For each customer in queue i, a cost c_{i} is charged per unit of time that this customer is in the system. Which policy minimizes the total costs in T periods? It can be shown that the so-called μc-rule is an optimal policy. This rule assigns the server to queue k, where k is the queue with μ_{k}c_{k} = max_{i}{μ_{i}c_{i} | queue i is nonempty}. Note that c_{i}μ_{i} is the expected costs per unit of service for a customer in queue i, and by using the μc-rule, the largest reduction of the expected costs in the next period is obtained. A second example is customer allocation to parallel identical queues. Customers arrive at a system of m parallel queues. Each queue has a server and the service times are identically and exponentially distributed with rate μ. At arrival, a customer has to join one of the queues (customer assignment model). Which policy minimizes the total discounted number of customers in the system? It is clear that the policy that allocates an arriving customer to the shortest queue is optimal for this individual customer. It can be shown that this policy, which is called the shortest queue policy (SQP), is also optimal for the overall criterion. As a final example of stochastic scheduling we consider the problem of minimizing the makespan and the total flowtime. Consider a set of n jobs, where each job has to be processed on one of m identical machines. Job j has an exponential distribution with rate μ_{j}, where μ_{1} ≤ μ_{2} ≤ ⋯ ≤ μ_{n}. Let T_{j} be the completion time of job j, 1 ≤ j ≤ n. Which policy minimizes the expected makespan, i.e. 𝔼[max(T_{1}, T_{2}, …, T_{n})]. This model can be considered as a server assignment model with m servers (machines): which jobs are processed by machine 1, which jobs by machine 2, etc. It can be shown that an optimal policy is the policy which chooses the longest expected processing time (LEPT) first. Hence, the jobs are allocated to the machines in the order 1, 2, …,n. When the expected total flowtime 𝔼[Σ_{j=1}^{n}T_{j}] has to be minimized, then the order is reversed, i.e. the shortest expected processing time first (SEPT). In this case the allocation of the jobs to the machines is n, n − 1, …, 1. The optimality of the μc-rule is established in Baras, Ma and Makowsky ^{\underline{bmm85}} [9]. Ephremides, Varayia and Walrand ^{\underline{ephr}} [68] have shown the optimality of the shortest queue policy. The results for the optimality of the LEPT and SEPT policies are due to Bruno, Downey and Frederickson ^{\underline{bruno}} [30]. Related results are obtained by Weber ^{\underline{web82}} [267] and by Chang, Hordijk, Righter and Weiss ^{\underline{chang}} [33]. For reviews on stochastic scheduling we refer to Weiss ^{\underline{wei82}} [270], Walrand ^{\underline{wal}} [266] (chapter 8), Righter ^{\underline{rig}} [194] and Weber’s chapter in this book.

Multi-armed bandit problem The multi-armed bandit problem is a model for dynamic allocation of a resource to one of n independent alternative projects. Any project may be in one of a finite number of states. At each period the decision maker has the option of working on exactly one of the projects. When a project is chosen, the immediate reward and the transition probabilities only depend on the active project and the states of the remaining projects are frozen. As utility function the total discounted reward is chosen. There are many applications of this model, e.g. in machine scheduling, in the control of queueing systems and in the selection of decision trials in medicine. It can be shown that an optimal policy is the policy that selects the project which has the largest so-called Gittins-index. Surprisingly, these indices can be computed for each project seperately. As a consequence, the multiarmed bandit problem can be solved by a sequence of n one-armed bandit problems. This is a decomposition result by which the dimensionality of the problem is reduced considerably. Efficient algorithms for the computation of the Gittins indices exist. The most fundamental contribution on multiarmed bandit problems was made by Gittins (cf. Gittins and Jones ^{\underline{gitt74}} [86], and Gittins ^{\underline{gitt79}} [85]). The importance of Gittins work was not recognized in the seventies. The re-discovery is due to Whittle ^{\underline{whittle80}} [289] who gave a more easy and natural proof. Other proofs are given by Ross ^{\underline{ross83}} [201], Varaiya, Walrand and Buyoccoc ^{\underline{var}} [255], Weber ^{\underline{web92}} [268] and Tsitsiklis ^{\underline{ts93}} [244]. Several methods are developed for the computation of the Gittins indices: Varaiya, Walrand and Buyukkoc ^{\underline{var}} [255], Chen and Katehakis ^{\underline{chen86}} [35], Kallenberg ^{\underline{kal86}} [136], Katehakis and Veinott ^{\underline{kate87}} [142], Ben-Israel and S.D.Flåm ^{\underline{benis90}} [14], and Liu and Liu ^{\underline{liu94}} [156].

1.2 FINITE HORIZON

Consider an MDP with a finite horizon of T periods. In fact, we can analyse with the same effort a nonstationary MDP, i.e. with rewards and transition probabilities which may depend on the time t(1 ≤ t ≤ T). These nonstationary rewards and transition probabilities are notated by r_{i}^{t}(a) and p_{ij}^{t}(a). By the principle of optimality, an optimal policy can be determined by backward induction as the next theorem shows. The proof can be given by induction on the length T of the horizon. The use of the principle of optimality and the technique of dynamic programming for sequential optimization is provided by Bellman ^{\underline{be}} [13].

Theorem 4 Let x_{i}^{T +1} = 0, i ∈ E. Determine for t = T, T − 1, ..., 1 a deterministic decision rule f_{t} such that

r_{i}^{t}(f_{t}(i)) + [P (f_{t})x^{t+1}]_{i} = max_{a∈A(i)}{r_{i}^{t}(a) + Σ_{j}p_{ij}^{t}(a) · x_{j}^{t+1}}, i ∈ E,

and let x^{t} = r^{t}(f_{t}) + P^{t}(f_{t})x^{t+1}. Then, R^{∗} = (f_{1}, f_{2}, ..., f_{T}) is an optimal policy and x^{1} is the value vector v^{T}.

If r_{i}^{t}(f_{t}(i)) + [P^{t}(f_{t})x^{t+1}]_{i} = max_{a∈A(i)}{r_{i}^{t}(a) + Σ_{j}p_{ij}^{t}(a) · x_{j}^{t+1}}, i ∈ E, then we denote r^{t}(f_{t})+P^{t}(f_{t})x = maxExA{r^{t} +P^{t}x} and f_{t} ∈ argmaxExA{r^{t} + P^{t}x}.

Algorithm I (finite horizon)

1. x = 0.

2. Determine for t = T, T − 1, …, 1 :

f_{t} ∈ argmaxExA{r^{t} + P^{t}x} and x = r^{t}(f_{t}) + P^{t}(f_{t})x.

3. R^{∗} = (f_{1}, f_{2}, …, f_{T}) is an optimal policy and x is the value vector.

Remarks

1. It is also possible to include in this algorithm elimination of suboptimal actions. Suboptimal actions are actions that will not occur in an optimal policy. References are Hastings and Van Nunen ^{\underline{hast77}} [99] and Hübner ^{\underline{hub77}} [125].

2. A finite horizon nonstationary MDP can be transformed in an equivalent stationary infinite horizon model. In such an infinite horizon model other options, as the treatment of side constraints, are applicable. These results can be found in Derman and Klein ^{\underline{der65}} [59] and in Kallenberg ^{\underline{kal81a}} [132], ^{\underline{kal81b}} [133].

1.3 DISCOUNTED REWARD CRITERION

1.3.1 Introduction

In order to find an optimal policy and the value vector v^{α}, the so-called optimality equation

v_{i}^{α} = max_{a}{r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}}, i ∈ E  (3.1)

plays a central role. Consider the mapping U : ℝ^{N} → ℝ^{N}, defined by

x_{i} = max_{a}{r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j}}, i ∈ E.  (3.2)

It turns out that U is a monotone contraction mapping with as fixed point the value vector v^{α}. By the general theory of monotone contraction mappings questions can be answered as:

- Is there a unique fixed-point?

- How can the fixed-point be computed?

- What is the rate of convergence of the computation? We first introduce some concepts and properties of contraction mappings.

Let X be a normed Banach space and B : X → X. The operator B is called a contraction mapping if for some β ∈ [0, 1) one has

∥ Bx − By ∥≤ β· ∥ x − y ∥ for all x, y ∈ X.  (3.3)

The number β is called the contraction factor of B. An element x^{∗} ∈ X is said to be a fixed-point of B if

Bx^{∗} = x^{∗}.  (3.4)

The next Fixed-point theorem shows the existence of a unique fixed point in a Banach space.

Theorem 4 Let X be a Banach space and suppose that B : X → X is a contraction. Then, for every x ∈ X, x^{∗} = lim_{n→∞}B^{n}x exists and x^{∗} is the unique fixed-point of B.

Hence, a straightforward method to approximate the fixed point is: x^{n} = Bx^{n−1} = B^{n}x^{0}, n ∈ ℕ (choose x^{0} arbitrarily). The convergence rate of the sequence x^{0}, x^{1}, … to the fixed point is based on the following result.

Theorem 5 Let X be a Banach space and suppose that B : X → X is a contraction mapping with contraction factor β and fixed-point x^{∗}. Then, for all x ∈ X

\begin{aligned}(i) & ∥ x^{∗} − B^{n}x ∥ & ≤ β(1 − β)^{−1}· ∥ B^{n}x − B^{n−1}x ∥ \\ & & ≤ β^{n}(1 − β)^{−1}· ∥ Bx − x ∥, n ∈ ℕ; \end{aligned}

(ii) ∥ x^{∗} − x ∥≤ (1 − β)^{−1}· ∥ Bx − x ∥ .

From the above theorem it follows that the convergence of B^{n}x to the fixedpoint is at least linear. This kind of convergence is also called geometric convergence.

Next, we mention some properties of monotone (contraction) mappings. Suppose that B : X → X is a mapping in a partially ordered set X. B is called monotone if x ≤ y implies Bx ≤ By. The next theorem shows an order property.

Theorem 6 Let X be a partially ordered Banach space and suppose that B : X → X is a monotone contraction mapping with fixed-point x^{∗}. Then,

\begin{matrix}(i) & Bx ≤ x & implies that & x^{∗} ≤ Bx ≤ x; \\ (ii) & Bx ≥ x & implies that & x^{∗} ≥ Bx ≥ x. \end{matrix}

It is well-known that ∥ x ∥_{∞}= max_{1≤i≤N} | x_{i} | is a norm, the supremum norm, in the partially ordered Banach space ℝ^{N} with ordering x ≤ y if x_{i} ≤ y_{i} for 1 ≤ i ≤ N. Hence, for x ∈ ℝ^{N} we have x ≤∥ x ∥_{∞} ·e, where e is the vector with all components equal 1.The subordinate matrix norm ∥ P ∥_{∞}for a square matrix P is defined by ∥ P ∥_{∞}= max_{i} Σ_{j}|p_{ij}|(cf. Stoer and Bulirsch ^{\underline{stoer}} [237] p.178). The following results, which we will express in the supremum norm, can be generalized to the so-called μ-norm, defined by ∥ x ∥_{μ} = max_{1≤i≤N} μ_{i}^{−1}· | x_{i} |, where μ ∈ ℝ^{N} with μ_{i} > 0. For μ = e, the μ-norm and the supremum norm coincide. More results are formulated in the following lemmas.

Lemma 7 Let B be a monotone contraction in ℝ^{N} with respect to the supremum norm, with contraction factor β and fixed-point x^{∗}. Suppose that there exist scalars a and b such that a · e ≤ Bx − x ≤ b · e for some x ∈ ℝ^{N}. Then,

\begin{aligned}x − (1 − β)^{−1} | a | ·e ≤ & Bx − β(1 − β)^{−1} | a | ·e ≤ x^{∗} ≤ \\ & Bx + β(1 − β)^{−1} | b | ·e ≤ x + (1 − β)^{−1} | b | ·e. \end{aligned}

The proof of this lemma can be given by first showing (by induction) that B^{n}x ≤ Bx+(β+⋯+β^{n−1}) | b | ·e ≤ x+(1+β+⋯+β^{n−1}) | b | ·e, n ∈ ℝ^{N}. By letting n → ∞ we obtain x^{∗} ≤ Bx + β(1 − β)^{−1} | b | ·e ≤ x + (1 − β)^{−1} | b | ·e. The other side of the inequalities can be shown similarly. Since − ∥ Bx − x ∥_{∞} ·e ≤ Bx − x ≤∥ Bx − x ∥_{∞} ·e, we obtain the following corollary.

Corollary 8 Let B be a monotone contraction in ℝ^{N} with respect to ∥ x ∥_{∞}, with contraction factor β and fixed-point x^{∗}. Then,

x − (1 − β)^{−1}· ∥ Bx − x ∥_{∞} ·e ≤ Bx − β(1 − β)^{−1}· ∥ Bx − x ∥_{∞} ·e ≤ x^{∗} ≤
Bx + β(1 − β)^{−1}· ∥ Bx − x ∥_{∞} ·e ≤
x + (1 − β)^{−1}· ∥ Bx − x ∥_{∞} ·e.

Lemma 9 Let B be a monotone contraction in ℝ^{N} with respect to ∥ x ∥_{∞}, with contraction factor β, fixed-point x^{∗} and with the property that B(x + c · e) = Bx + βc · e for every x ∈ ℝ^{N} and scalar c. Suppose that for some scalars a and b and for some x ∈ ℝ^{N}, a · e ≤ Bx − x ≤ b · e. Then, x + (1 − β)^{−1}a · e ≤ Bx + β(1 − β)^{−1}a · e ≤ x^{∗} ≤ Bx + β(1 − β)^{−1}b · e ≤ x + (1 − β)^{−1}b · e.

The proof of lemma 9 can be given analogously to the proof of lemma 7. We will apply these general results of monotone contraction mappings to special mappings in our MDP model. These mappings are U, defined in (3.2) and L_{π}, for any stationary decision rule π, defined by

L_{π}x = r(π) + αP (π)x.  (3.5)

Let f_{x}(i) ∈ argmax_{A(i)}{r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j}}, then

L_{f_{x}}x = Ux = max_{π} L_{π}x.  (3.6)

Theorem 10 With respect to the norm ∥ x ∥_{∞}, L_{π} and U are monotone contraction mappings in ℝ^{N} with contraction factor α.

Proof. Suppose that x ≥ y. Let π be any stationary decision rule. Because P (π) ≥ 0, we may write L_{π}x = r(π) + αP (π)x ≥ r(π) + αP (π)y = L_{π}y, i.e. L_{π} is monotone. Since Ux = max_{π} L_{π}x ≥ L_{f_{y}}x ≥ L_{f_{y}}y = Uy, U is also monotone. Because ∥ L_{π}x − L_{π}y ∥_{∞}=∥ αP (π)(x − y) ∥_{∞}≤ α· ∥ P (π) ∥_{∞} · ∥ x − y ∥_{∞}= α· ∥ x−y ∥_{∞}, L_{π} is a contraction with contraction factor α. For the operator U we obtain Ux−Uy = L_{f_{x}}x−L_{f_{y}}y ≤ L_{f_{x}}x−L_{f_{x}}y = α·P (f_{x})(x−y) ≤ α· ∥ x−y ∥_{∞} ·e. Interchanging x and y yields Uy − Ux ≤ α· ∥ x − y ∥_{∞} ·e. Hence, ∥ Ux − Uy ∥_{∞}≤ α· ∥ x − y ∥_{∞}, i.e. U is a contraction with contraction factor α.

The next theorem shows that, for any stationary policy π^{∞}, the total αdiscounted reward v^{α}(π^{∞}) is the fixed-point of the mapping L_{π}.

Theorem 11 For any stationary decision rule π, v^{α}(π^{∞}) is the unique solution of the functional equation L_{π}x = x.

Using the property v^{α}(π^{∞}) = [I − αP (π)]^{−1}r(π), the proof follows directly from the theorems 4 and 10.

Corollary 12 v^{α}(π^{∞}) = lim_{n→∞} L_{π}^{n}x for any x ∈ ℝ^{N}.

Theorem 13 v^{α} is the unique solution of the equation Ux = x. Proof. An outline of the proof is as follows. First, show that v^{α}(R) ≤ Uv^{α} for any Markov policy R, implying - by theorem 1 - that v^{α} = sup_{R∈C(M)}v^{α} (R) ≤ Uv^{α}. Then, prove that for any ϵ > 0, v_{i}^{α} ≥ (Uv^{α})_{i} − ϵ, i ∈ E, which implies that v^{α} ≥ Uv^{α}.

Because, v^{α} = Uv^{α} = L_{f_{v}α}v^{α}, the last equality by (3.6), it follows from theorem 13 that v^{α} = v^{α}(f_{v^{α}}^{∞}), i.e. f_{v^{α}}^{∞} is an optimal policy. If f^{∞} satisfies r_{i}(f(i)) + αΣ_{j} p_{ij}(f(i))v_{j}^{α} = max_{a}{r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}}, i ∈ E, then f^{∞} is called a conserving policy. f_{v^{α}}^{∞} is a conserving policy and conserving policies are optimal. Therefore, the equation Ux = x is called the optimality equation.

Corollary 14 (i) There exists a deterministic and stationary α-discounted optimal policy; (ii) v^{α} = lim_{n→∞} U^{n}x for any x ∈ ℝ^{N}; (iii) Any conserving policy is α-discounted optimal.

Since L_{f}(x + c · e) = L_{f}x + αc · e and U(x + c · e) = Ux + αc · e for any x ∈ ℝ^{N} and any scalar c, we can apply lemma 9 to obtain bounds for the fixed points v^{α}(f^{∞}) and v^{α} of the operators L_{f} and U, respectively.

Lemma 15 For any x ∈ ℝ^{N} we have

(i) x + (1 − α)^{−1} min_{i}(Ux − x)_{i} · e ≤Ux + α(1 − α)^{−1} min_{i}(Ux − x)_{i} · e
≤ v^{α}(f_{x}^{∞}) ≤ v^{α}

≤ Ux + α(1 − α)^{−1} max_{i}(Ux − x)_{i} · e ≤ x + (1 − α)^{−1} max_{i}(Ux − x)_{i} · e.

\begin{aligned}(ii) & ∥ v^{α} − v^{α}(f_{x}^{∞}) ∥_{∞}≤ α(1 − α)^{−1}span(Ux − x), \\ & where span(y) = max_{i} y_{i} − min_{i} y_{i}. \end{aligned}

An action a ∈ A(i) is called suboptimal if there does not exist an α-discounted optimal policy f^{∞} with f(i) = a. Because f^{∞} is α-discounted optimal if and only if v^{α}(f^{∞}) = v^{α}, and because v^{α} = Uv^{α}, an action a ∈ A(i) is suboptimal if and only if

v_{i}^{α} > r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}.  (3.7)

Suboptimal actions can be excluded. Not directly by (3.7), because v^{α} is unknown, but by using the bounds on v^{α} as given by lemma 15. Then, by the monotonicity of U, the next result is obtained.

Theorem 16 (i) Suppose that x ≤ v^{α} ≤ y. If r_{i}(a) + αΣ_{j}p_{ij}(a)y_{j} < (Ux)_{i}, then action a ∈ A(i) is suboptimal. (ii) Suppose that for some scalars b and c, x + b · e ≤ v^{α} ≤ x + c · e. If r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j} < (Ux)_{i} − α(c − b), then action a ∈ A(i) is suboptimal.

Using the bounds of v^{α} from lemma 15, we obtain suboptimality for an action a ∈ A(i) if

r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j} < (Ux)_{i} − α(1 − α)^{−1}span(Ux − x)  (3.8)

or

r_{i}(a) + αΣ_{j}p_{ij}(a)(Ux)_{j} < (U^{2}x)_{i} − α^{2}(1 − α)^{−1}span(Ux − x)  (3.9)

Remark If we relax the property that Σ_{j}p_{ij}(a) = 1 to Σ_{j}p_{ij}(a) ≤ 1 for all (i, a) and require that the model is transient, i.e. the matrix Σ_{t=1}^{∞}[P (f)]^{t} has finite elements for every policy f^{∞}, then the total expected reward criterion, i.e. the discounting case with discount factor α = 1, is well-defined. For this criterion similar results can be obtained as in the discounted model. The investigation whether an MDP is transient can be done efficiently (cf. Veinott ^{\underline{vei69}} [258] and Kallenberg ^{\underline{kal83}} [135]. Other references on this topic are van Hee, Hordijk and van der Wal ^{\underline{hee}} [249], Denardo and Rothblum ^{\underline{den79a}} [53], and Hordijk and Kallenberg ^{\underline{hor84a}} [116].

Already in 1953, Shapley ^{\underline{sh}} [222] analysed contraction properties for stochastic games. In the special case of a one-player game a stochastic game becomes an MDP. A comprehensive treatment of the theory of contraction mappings for discounted Markov decision processes was given by Denardo ^{\underline{den67}} [45]. The generalization to the μ-norm was made by Wessels ^{\underline{wes77}} [272] and Van Nunen ^{\underline{nunen76b}} [251]. They apply this μ-norm to MDPs with countable state space and unbounded rewards. The details of the proof of theorem 13 can be found in Ross ^{\underline{ross70}} [199]. An alternative proof that U has a fixed point, based on Brouwer’s theorem, was given in Shapiro ^{\underline{sha}} [221]. The concepts ’conserving’ and ’span’ were introduced by Dubins and Savage ^{\underline{dubins}} [64] and Bather ^{\underline{bath73a}} [10]. Concerning the bounds of lemma 15, the weakest bounds were proposed by MacQueen ^{\underline{mac66}} [163] and the strongest by Porteus ^{\underline{por71}} [180]. Related papers are Porteus ^{\underline{por75}} [181] and Bertsekas ^{\underline{bertse76b}} [16]. The notion that suboptimal actions can be excluded if bounds on the value vector are available can be found in MacQueen ^{\underline{mac67}} [164], which paper includes the test (3.8). Test (3.9) is proposed by Porteus ^{\underline{por71}} [180]. Other suboptimality tests can be found in Hastings and Mello ^{\underline{hast73}} [97], White ^{\underline{white78}} [279] and Thomas ^{\underline{th81}} [240].

1.3.2 Policy iteration

For x, y ∈ ℝ^{N}x > y means that x_{i} ≥ y_{i} for every i and x_{i} > y_{i} for at least one i. In the method of policy iteration a sequence of deterministic policies f_{1}^{∞}, f_{2}^{∞}, … is constructed such that

v^{α}(f_{k+1}^{∞}) > v^{α}(f_{k}^{∞}) for k = 1, 2, …  (3.10)

Because there are finite deterministic policies f^{∞}, the method of policy iteration is finite. Furthermore, it can be shown that the method terminates with an α-discounted optimal policy. We first remark that the following lemma is a consequence of theorem 10.

Lemma 17 (i) If L_{f}x ≤ x, then v^{α}(f^{∞}) = lim_{n→∞} L_{f}^{n}x ≤ L_{f}x ≤ x; (ii) if L_{f}x > x, then v^{α}(f^{∞}) = lim_{n→∞} L_{f}^{n}x ≥ L_{f}x > x.

For every i ∈ E and deterministic policy f^{∞}, the set A(i, f) be defined by

A(i, f) = {a ∈ A(i)|r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}(f^{∞}) > v_{i}^{α}(f^{∞})}.  (3.11)

The intuitive idea of policy iteration is that if action f(i) is replaced by an action a ∈ A(i, f) the resulting policy improves the α-discounted rewards. Therefore, the actions of A(i, f) are called improving actions.The correctness of this idea is established by the following theorem.

Theorem 18 (i) If A(i, f) = ∅ for every i ∈ E, then f^{∞} is α-discounted optimal; (ii) If A(i, f) ≠ ∅ for some i ∈ E, then v^{α}(g^{∞}) > v^{α}(f^{∞}) for any policy g with g ≠ f and g(i) ∈ A(i, f) if g(i) ≠ f(i). Proof. (i) A(i, f) = ∅, i ∈ E, implies L_{g}v^{α}(f^{∞}) = r(g) + αP (g)v^{α}(f^{∞}) ≤ v^{α}(f^{∞}) for every g. By lemma 17(i) v^{α}(g^{∞}) ≤ v^{α}(f^{∞}) for every g, i.e. f^{∞} is optimal. (ii) Take any g ≠ f such that g(i) ∈ A(i, f) if g(i) ≠ f(i). Then, if g(i) ≠ f(i), r_{i}(g) + αΣ_{j}p_{ij}(g)v_{j}^{α}(f^{∞}) > v_{i}^{α}(f^{∞}). If g(i) = f(i), r_{i}(g) + αΣ_{j}p_{ij}(g)v_{j}^{α}(f^{∞}) = r_{i}(f) + αΣ_{j}p_{ij}(f)v_{j}^{α}(f^{∞}) = v_{i}^{α}(f^{∞}). Hence, L_{g}v^{α}(f^{∞}) = r(g)+αP (g)v^{α}(f^{∞}) > v^{α}(f^{∞}) and, by lemma 17(ii), v^{α}(g^{∞}) > v^{α}(f^{∞}).

Let

s_{ia}(f) = r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}(f^{∞}) − v_{i}^{α}(f^{∞}), a ∈ A(i) and i ∈ E. (3.12)

Algorithm II (policy iteration; discounted rewards)

1. Start with any deterministic policy f^{∞}.

2. Compute v^{α}(f^{∞}) as unique solution of the linear system L_{f}x = x.

3. Determine for every i ∈ E : A(i, f) = {a ∈ A(i)|s_{ia}(f) > 0}.

4. If A(i, f) = ∅ for every i ∈ E: go to step 6.

Otherwise: take any g ≠ f such that, if g(i) ≠ f(i), g(i) ∈ A(i, f).

5. f = g and go to step 2.

6. f^{∞} is an α-discounted optimal policy.

The idea to use policy iteration to determine an optimal policy appeared in Howard ^{\underline{ho60}} [122]. Blackwell ^{\underline{bl62}} [27] has provided a strong mathematical treatment of this method. In Porteus ^{\underline{por81}} [184] and in Hartley, Lavercombe and Thomas ^{\underline{hart}} [92] efficient ways to determine v^{α}(f^{∞}) as solution of the linear system L_{f}x = x are analysed.

Remarks

1. There is some freedom in the choice of policy g^{∞} in step 4. A usual choice is to take g such that s_{ig(i)}(f) = max_{a} s_{ia}(f), i.e. g(i) ∈ argmax_{a}s_{ia}(f).

2. It can be shown (see Puterman and Brumelle ^{\underline{put79}} [188] that the policy iteration method, with the above choice for g, is equivalent to solve the optimality equation Ux = x by Newton’s method.

3. Furthermore, we can derive a result on the convergence rate. It can be shown that x^{n} = v^{α}(f_{n}^{∞}), n = 1, 2, …, where x^{n} are the iterates of the Newton method and f_{n}^{∞} the policies of the policy iteration method. Since, it can be shown that ∥ v^{α} − v^{α}(f_{n+1}^{∞}) ∥_{∞}≤ 2α(1 − α)^{−1} ∥ v^{α} − v^{α}(f_{n}^{∞}) ∥_{∞}, there is geometric convergence. Already in Pollatschek and Avi-Itzhak ^{\underline{pol}} [179], in the context of stochastic games, the equivalence between the policy iteration method and Newton’s method was noticed. A related paper is Schweitzer ^{\underline{schw85}} [212]. Puterman and Brumelle ^{\underline{put79}} [188] were the first who derived result for the rate of convergence.

4. We can also include in policy iteration the exclusion of suboptimal actions. We can use e.g. test (3.8) with x = v^{α}(f^{∞}). Since, for x = v^{α}(f^{∞}), (Ux − x)_{i} = max_{a}{r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}^{α}(f^{∞}) − v_{i}^{α}(f^{∞})} = max_{a} s_{ia}(f), i ∈ E, we have span(Ux − x) = max_{i}[max_{a} s_{ia}(f)] − min_{i}[max_{a} s_{ia}(f)]. Hence (3.8) becomes: if s_{ib}(f) < max_{a} s_{ia}(f) − α(1 − α)^{−1}[max_{i} max_{a} s_{ia}(f) − min_{i} max_{a} s_{ia}(f)], then action b ∈ A(i) is suboptimal. Grinold ^{\underline{grin}} [91] pointed out that suboptimality tests can be implemented in policy iteration. The above test is stronger than Grinold’s test.

5. We can implement a modification of the method. Instead of the steps 3 and 4, we take the steps 3’ and 4’ which are as follows: Step 3’. For i = 1 to N do

a. d_{ia}(f) = r_{i}(a) + αΣ_{j=1}^{i−1}p_{ij}(a)x_{j} + αΣ_{j=i}^{N}p_{ij}(a)v_{j}^{α}(f^{∞}), a ∈ A(i); b. if d_{ia}(f) ≤ v_{i}^{α}(f^{∞}) for every a ∈ A(i) : x_{i} = v_{i}^{α}(f^{∞}) and g(i) = f(i); c. if d_{ia}(f) > v_{i}^{α}(f^{∞}) for some a ∈ A(i) : x_{i} = max_{a} d_{ia}(f) and take

g(i) = argmaxd_{ia}(f). Step 4’. If g(i) = f(i) for every i ∈ E, then go to step 6. This modified algorithm, which can be shown to be correct, is proposed in Hastings ^{\underline{hast69}} [94].

6. In Schmitz ^{\underline{schm}} [205] the question is raised: ”Does there exist a polynomial bound for the number of iterations in the policy iteration?”. Meister and Holzbaur ^{\underline{meis}} [166] have shown that this method is polynomially in time. In ng ^{\underline{ng}} [172] is shown that the complexity of one iteration is O(mN^{2}), where m is the number of states i for which g(i) ≠ f(i).

1.3.3 Linear programming

A vector v ∈ ℝ^{N} is said to be α-superharmonic if

v_{i} ≥ r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j} for every (i, a) ∈ E × A.  (3.13)

Theorem 19 v^{α} is the (componentwise) smallest α-superharmonic vector.

Proof. Theorem 13 implies that v_{i}^{α} ≥ r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α} for every (i, a), i.e. v^{α} is α-superharmonic. Suppose that v ∈ ℝ^{N} is also α-superharmonic. Then, v ≥ r(f) + αP (f)v for every f^{∞}, which implies that [I − αP (f)]v ≥ r(f). Since [I − αP (f)]^{−1} = Σ_{t=0}^{∞}α^{t}P (f)^{t} ≥ 0, we obtain v ≥ [I − αP (f)]^{−1} r(f) = v^{α}(f^{∞}). Hence, v^{α} = max_{f} v^{α}(f^{∞}) ≤ v, i.e. v^{α} is the smallest α-superharmonic vector.

Corollary 20 v^{α} is the unique optimal solution of the LP-problem

min{Σ_{j}β_{j}v_{j}|Σ_{j}[δ_{ij} − αp_{ij}(a)]v_{j} ≥ r_{ia}, (i, a) ∈ E × A}  (3.14)

where β_{j} > 0 for every j ∈ E.

By corollary 20, the value vector v^{α} can be found as optimal solution of the linear program (3.14). This program does not give an optimal policy. However, an optimal policy can be obtained from the solution of the dual program

max \{Σ_{i}Σ_{a}r_{i}(a)x_{ia} | \begin{matrix}Σ_{i}Σ_{a}[δ_{ij} − αp_{ij}(a)] & x_{ia} = β_{j}, j ∈ E \\ & x_{ia} ≥ 0, (i, a) ∈ E × A \end{matrix}\} (3.15)

Theorem 21 Let x^{∗} be an optimal solution of (3.15). Then, a policy f^{∞} with x_{jf(j)}^{∗} > 0 for every j ∈ E exists and is an optimal policy. Proof. From the constraints of (3.15) it follows that Σ_{a}x_{ja}^{∗} = β_{j} +αΣ_{i}Σ_{a}p_{ij}(a)x_{ia}^{∗} ≥ β_{j} > 0, j ∈ E. Let f^{∞} be such that x_{jf(j)}^{∗} > 0, j ∈ E. The complementary slackness property of linear programming implies that Σ_{j}[δ_{ij} − αp_{ij}(f(i)]v_{j}^{α} = r_{i}(f), i ∈ E. Hence, [I − αP (f)]^{α} = r(f), implying v^{α} = [I − αP (f)]^{−1}r(f) = v^{α}(f^{∞}), i.e. f^{∞} is an optimal policy.

Moreover, there is a one-to-one correspondence between the set of feasible solutions of (3.15) and the set of stationary policies, given by the following relations. For a stationary policy π^{∞} the feasible solution x(π) satisfies

x_{ia}(π) = [β^{T} (I − αP (π))^{−1}]_{i} · π_{ia}, (i, a) ∈ E × A.  (3.16)

Conversely, for a feasible solution x of (3.15), define π^{∞}(x) by

π_{ia}(x) = x_{ia}/Σ_{a}x_{ia}(i, a) ∈ E × A.  (3.17)

Theorem 22 The mapping (3.16) is a one-to-one mapping of the set of stationary policies onto the set of feasible solutions of the dual program (3.15) with (3.17) as the inverse mapping; furthermore, the set of extreme feasible solutions of (3.15) corresponds to the set of deterministic policies.

Algorithm III (linear programming; discounted rewards)

1. Take any β ∈ ℝ^{N} with β_{j} > 0, j ∈ E.

2. Compute optimal solutions v^{∗} and x^{∗} of the dual pair LP-problems (3.14) and (3.15).

3. Take any f_{∗} such that x_{if_{∗}(i)}^{∗} > 0, i ∈ E.

4. v^{∗} is the value vector and f_{∗}^{∞} is an α-discounted optimal policy.

It turns out that the linear programming method is, in some sense, equivalent to policy iteration. This is formulated in the next theorem, in which the term block-pivoting simplex algorithm is used. A simplex LP-algorithm, which in one iteration more than one pivot step may use, is called a blockpivoting simplex algorithm (cf. Dantzig ^{\underline{dantzig}} [40]).

Theorem 23 (i) Any policy iteration algorithm is equivalent to a blockpivoting simplex algorithm; (ii) any simplex algorithm is equivalent to a particular policy iteration algorithm.

Remarks

1. Since the LP-method and policy iteration are equivalent, exclusion of suboptimal actions can also be implemented in the LP-method. The relevant data s_{ia}(f) for this test (see (3.12)) are available in the simplex tableaus as the so-called reduced costs.

2. The variables x_{ia}(π), defined in (3.16) can be interpreted as discounted state-action frequencies, i.e. if policy π^{∞} is used, then x_{ia}(π) is equal to the total expected discounted number of times that state i is visited and then also action a is chosen, given that the starting state is state j with probability β_{j}, j ∈ E.

3. The linear programming method is the only method which can handle additional constraints. Constrained optimization arises in many MDP applications, e.g. in inventory and queueing models. For examples we refer to Derman ^{\underline{der70}} [58], chapter 7, and to Puterman ^{\underline{put94}} [187], section 8.9. The constraints have to be expressed in terms of the state-action frequencies and added to the dual program (3.15). Constrained problems have a stationary, but not necessarily deterministic optimal policy. For the details we refer to Kallenberg ^{\underline{kal83}} [135], and to Hordijk and Kallenberg ^{\underline{hor84a}} [116]. In Altman and Shwartz ^{\underline{alsh91a}} [4] the sensitivity of constrained MDPs is investigated. Altman, Hordijk and Kallenberg ^{\underline{ahk96}} [3] have analysed the behavior of the value function in constrained MDP.

The idea to use linear programming to compute an optimal policy originated with D’Epenoux ^{\underline{depn60}} [55]. The one-to-one correspondence between the feasible solutions of the dual program and the set of stationary policies can be found in De Ghellinck and Eppen ^{\underline{degh67}} [43]. The equivalence between block-pivoting and policy iteration was mentioned in De Ghellinck ^{\underline{degh60}} [42]. The implementation of the suboptimality tests was proposed by Grinold ^{\underline{grin}} [91] and by Hordijk and Kallenberg ^{\underline{hor84a}} [116]. In Sun ^{\underline{sun}} [239] an implementation of the LP-method is described, based on the revised simplex method. Stein ^{\underline{st}} [234] has investigated the computational aspects of the linear programming method in comparison with other methods. It turns out that the LP-method is preferable if the discount factor is close to unity and the state space is not too large.

1.3.4 Value iteration

In the value iteration method the value vector v^{α} is approximated by a sequence {v^{n}}_{n=1}^{∞}, which converges to v^{α}. Furthermore, a nearly optimal policy is obtained. For ϵ > 0 a vector v ∈ ℝ^{N} is an ϵ-approximation of v^{α} if ∥ v^{α} − v ∥_{∞} ≤ ϵ; a policy R is an ϵ-optimal policy if ∥ v^{α} − v^{α}(R) ∥_{∞} ≤ ϵ, i.e. v^{α}(R) is an ϵ-approximation of v^{α}. From corollary 14(ii) it follows that v^{α} = lim_{n→∞}U^{n}x for every x ∈ ℝ^{N}.

Define the sequence {v^{n}}_{n=1}^{∞} by

\{ \begin{matrix}v^{1} ∈ ℝ^{N} & arbitrarily chosen \\ v^{n+1} = Uv^{n}, & n = 1, 2, … \end{matrix}  (3.18)

with a corresponding sequence f_{1}^{∞}, f_{2}^{∞}, … of policies where f_{n} = f_{v^{n}} for every n ∈ ℕ, i.e.

v^{n+1} = Uv^{n} = L_{f_{n}}v^{n} = r(f_{n}) + αP (f_{n})v^{n}, n ∈ ℕ.  (3.19)

The next lemma shows that f_{n}^{∞} is an ϵ-optimal policy for n sufficiently large. The proof is based on contraction properties as applied in lemma 15.

Lemma 24 ∥ v^{α}(f_{n}^{∞}) − v^{α} ∥_{∞}≤ 2α^{n}(1 − α)^{−1}· ∥ v^{2} − v^{1} ∥_{∞}, n ∈ ℕ.

Algorithm IV (value iteration; discounted rewards)

1. Choose ϵ > 0 and x ∈ ℝ^{N} arbitrarily.

2. Compute y = Ux and take f = f_{x}.

3. If ∥ y − x ∥_{∞}≤ (1 − α)α^{−1}ϵ, then f^{∞} is a 2ϵ-optimal policy and y is an ϵ-approximation of v^{α}(Stop);

Otherwise: x = y and goto step 2.

The correctness of algorithm IV is a consequence of the next theorem, which also follows from the contraction properties.

Theorem 25 (i) ∥ v^{α}(f_{x}^{∞}) − v^{α} ∥_{∞}≤ 2α(1 − α)^{−1}· ∥ Ux − x ∥_{∞}; (ii) ∥ Ux − v^{α} ∥_{∞}≤ α(1 − α)^{−1}· ∥ Ux − x ∥_{∞}.

In the next theorem we summarize some suboptimality tests.

Theorem 26 An action a ∈ A(i) is suboptimal if one of the following tests is satisfied:

r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j} < (Ux)_{i} − 2α(1 − α)^{−1}· ∥ Ux − x ∥_{∞}  (3.20)
r_{i}(a) + αΣ_{j}p_{ij}(a)(Ux)_{j} < (U^{2}x)_{i} − 2α^{2}(1 − α)^{−1}· ∥ Ux − x ∥_{∞} (3.21)
r_{i}(a) + αΣ_{j}p_{ij}(a)x_{j} < (Ux)_{i} − α(1 − α)^{−1}span(Ux − x)  (3.22)
\begin{aligned}r_{i}(a) + αΣ_{j}p_{ij}(a)(Ux)_{j} < & (Ux)_{i} + α(1 − α)^{−1} min_{i}(Ux − x)_{i}− \\ & α^{2}(1 − α)^{−1} max_{i}(Ux − x)_{i} \end{aligned} (3.23)

Remarks

1. In the usual computation scheme of the value iteration algorithm, test (3.22) is the best available test.

2. We also mention two variants of the standard algorithm. In the Pre-Gauss-Seidel variant we use for the computation of y_{i} the components y_{j} = (Ux)_{j} which are already computed, i.e.

\begin{aligned}y_{i} = max_{a}\{r_{i}(a) + αΣ_{j=1}^{i−1}p_{ij}(a)y_{j}+ & αΣ_{j=i}^{N}p_{ij}(a)x_{j}\}, \\ & i = 1, 2, …, N \end{aligned}  (3.24)

In the Gauss-Seidel variant also the i-th component x_{i} is replaced by y_{i}, which gives

\begin{aligned}y_{i} & = max_{a}[1 − αp_{ii}(a)]^{−1} · \{r_{i}(a) + αΣ_{j=1}^{i−1}p_{ij}(a)y_{j} \\ & +αΣ_{j=i+1}^{N}p_{ij}(a)x_{j}\}, i = 1, 2, …, N \end{aligned}  (3.25)

For both variants it can be shown that the corresponding operators are contraction mappings with fixed point v^{α} and with contraction factor at most α. Hence, they may be considered as an acceleration of the basic algorithm.

The proofs can be given by induction of the states. Also suboptimaly tests for the actions can be included.

Howard ^{\underline{ho60}} [122] was the first who studied value iteration for a Markov decision process. For a survey of the basic properties we refer to Federgruen and Schweitzer ^{\underline{fed78}} [70]. The idea to accelerate the convergence by the pre-Gauss-Seidel method was proposed in Hastings ^{\underline{hast69}} [94]. The Gauss-Seidel method can be found in Kushner and Kleinman ^{\underline{kuke71}} [150]. An overview of these variants is presented in Porteus ^{\underline{por80b}} [183]. Other techniques, based on successive overrelaxation and stopping times, in order to accelerate the convergence can be found in Reetz ^{\underline{ree73}} [191] and ^{\underline{ree76}} [192], Schellhaas ^{\underline{sche}} [204], Wessels ^{\underline{wes77}} [272], Van Nunen ^{\underline{nunen76a}} [250], Van Nunen and Wessels ^{\underline{nunen76}} [253] and ^{\underline{nunen77}} [254], Porteus and Totten ^{\underline{por78}} [185], Porteus ^{\underline{por80a}} [182], Herzberg and Yechali ^{\underline{herz}} [105], and Bertsekas ^{\underline{bertse95c}} [20]. Holzbaur ^{\underline{hol94}} [110] has presented a theoretically polynomial bound for the number of steps in the value iteration method.

1.3.5 Modified policy iteration

In section 3.2 the policy iteration method was discussed. This method, with the usual choice for the improving actions, can be considered as Newton’s method for the solution of the optimality equation. A new iterand y is obtained from x by the formula

y = x + A(Ux − x), where A = [I − αP (g)]^{−1} with g such that L_{g}x = Ux

(3.26)

The determination of the matrix [I − αP (g)]^{−1}, which is equal to Σ_{i=0}^{∞} α^{i}[P (g)]^{i}, requires in general a lot of work. In the modified policy iteration method the matrix A is truncated by

A^{(k)} = Σ_{i=0}^{k−1}α^{i}[P (g)]^{i} for some 1 ≤ k ≤ ∞  (3.27)

For k = 1, A^{(k)} = I and the value iteration method is obtained; for k = ∞, A^{(k)} = A, and we have policy iteration. For 1 < k < ∞, the modified policy iteration method can be considered as a combination of policy iteration and value iteration, or as an inexact Newton method for the solution of the optimality equation.

We may allow that in each iteration another value of k is chosen, and we denote k(n) for the value in iteration n. Hence, we obtain the following iteration scheme, where f_{n}^{∞} is the policy in iteration n, i.e. L_{f_{n}}x^{n} = Ux^{n}.

x^{n+1} = x^{n} + A^{(k(n))}(Ux^{n} − x^{n})
= x^{n} + Σ_{i=0}^{k(n)−1}α^{i}P^{i}(f_{n})[r(f_{n}) + αP (f_{n})x^{n} − x^{n}]

= r(f_{n}) + αP (f_{n})r(f) + ⋯ + [αP (f_{n})]^{k(n)−1}r(f_{n}) + [αP (f_{n})]^{k(n)}x^{n}

= L_{f_{n}}^{k(n)}x^{n}.

Algorithm V (modified policy iteration; discounted rewards)

1. Choose x ∈ ℝ^{N}, ϵ > 0 and a deterministic policy f^{∞}.

2. a. Choose k with 1 ≤ k ≤ ∞;

b. Determine g such that L_{g}x = Ux, where g(i) = f(i) if possible.

3. If ∥ Ux − x ∥_{∞}≤ (1 − α)ϵ: g^{∞} is an 2ϵ-optimal policy and Ux is an αϵ-approximation of v^{α} (STOP);

Otherwise: x = L_{g}^{k}x, f = g and go to step 2.

Remarks

1. Since x^{n+1} = L_{f_{n}}^{k(n)}x^{n}, the iteration operator depends on n, and it is not obvious that this operator is monotone and/or contracting. Indeed, in general, this operator is neither a contraction nor monotone. Although this operator is neither a contraction nor monotone, it can be shown that v^{α} = lim_{n→∞} L_{f_{n}}^{k(n)}x^{n} for any starting vector x^{1}.

2. Also in this method, it is possible to implement tests for the exclusion of suboptimal actions.

Puterman and Shin ^{\underline{put78}} [189] and independently Van Nunen ^{\underline{nunen76a}} [250], ^{\underline{nunen76b}} [251] and ^{\underline{nunen76c}} [252] have developed the modified policy iteration method. The first authors have shown the convergence under the assumption that the starting vector x satisfies Ux ≥ x. The convergence of the method for an arbitrary starting vector was proved by Rothblum ^{\underline{rot}} [202]. In Van Nunen ^{\underline{nunen76a}} [250] an example is given which shows that the operator of the modified policy iteration method can be neither contracting nor monotonic. The observation that the modified policy iteration method can be viewed as an inexact Newton method was made by Dembo and Haviv ^{\underline{dembo}} [44]. The exclusion of suboptimal actions for this method was developed by Puterman and Shin ^{\underline{put82}} [190]. Puterman ^{\underline{put81}} [186] reviews computational results for the modified policy iteration method.

1.4 AVERAGE REWARD CRITERION

1.4.1 Introduction

We start this section with some properties of the transition matrix P, i.e. a matrix with nonnegative elements and with every row sum equal to 1. Note that, for every stationary policy π^{∞}, P (π) is a transition matrix. The stationary matrix P^{∗} of P is defined by the so-called Cesaro-limit of P^{n}, i.e.

P^{∗} = lim_{n→∞} \frac{1}{n}Σ_{k=1}^{n}P^{k−1}  (4.1)

The stationary matrix has some nice properties, summarized in the next theorem.

Theorem 27 (i) P^{∗}P = P P^{∗} = P^{∗}P^{∗} = P^{∗}; (ii) [P − P^{∗}]^{n} = P^{n} − P^{∗}, n ≥ 1; (iii) lim_{α↑1}(1 − α)Σ_{n=0}^{∞}α^{n}(P^{n} − P^{∗}) = 0; (iv) [I − P + P^{∗}] is nonsingular with inverse [I−P +P^{∗}]^{−1} = lim_{n→∞} \frac{1}{n}Σ_{k=1}^{n}Σ_{i=1}^{k}[P −P^{∗}]^{i−1}; (v) for every stationary policy π^{∞}, the average reward ϕ(π^{∞}) satisfies ϕ(π^{∞}) = P^{∗}(π)r(π), where P^{∗}(π) is the stationary matrix of the transition matrix P (π); (vi) ϕ(π^{∞}) = lim_{α↑1}(1 − α)v^{α}(π^{∞}).

The inverse matrix [I − P + P^{∗}]^{−1} is denoted by Z and is called the fundamental matrix. Furthermore, we introduce the deviation matrix D by

D = Z − P^{∗}  (4.2)

Theorem 28 The deviation matrix satisfies (i) D = lim_{n→∞} \frac{1}{n}Σ_{k=1}^{n}Σ_{i=1}^{k} [P^{i−1} − P^{∗}] (ii) P^{∗}D = DP^{∗} = [I − P]D + P^{∗} − I = D[I − P] + P^{∗} − I = 0.

For the proofs of the theorems 27 and 28 we refer to books on Markov chains (e.g. Kemeny and Snell ^{\underline{kem}} [145] [1960]). A treatment, related to MDPs, of the stationary, the fundamental and the deviation matrix can be found in Veinott ^{\underline{vei74}} [259] [1974]. The deviation matrix of the transition matrix P (π) is denoted by D(π).

We continue this section with a classification of MDPs based on the ergodic structure. We distinguish between multichain, unichain and irreducible MDPs. The reason for this distinction is that MDPs can be analysed easier in case they are unichain or irreducible, which may lead to simplified algorithms for solving these MDPs. We assume the reader familiar with concepts from Markov chains as recurrent state, transient state, recurrent class and irreducibility.

An MDP is irreducible if the Markov chain P (f) is irreducible for every policy f^{∞}. We say that an MDP is unichain if for every policy f^{∞} the Markov chain P (f) has exactly one recurrent class plus a (possibly empty) set of transient states. Hence, an irreducible MDP is unichained (the reverse statement is not true, in general). An MDP is multichain if there exists a policy f^{∞} for which the Markov chain P (f) has at least two ergodic classes. If the ergodic structure is unknown, one can always use the general approach for multichain MDPs. The determination whether or not an MDP is irreducible is an easy problem, i.e. polynomially solvable, which means that the number of steps is bounded by a polynomial function of the problem’s data (see Kallenberg ^{\underline{kal99}} [138].

Open problem Does there exist a polynomial algorithm to determine whether an MDP is unichain or multichain?

Next, we will formulate a theorem on the existence of a Blackwell optimal policy f_{0}^{∞}, i.e. f_{0}^{∞} is α-discounted optimal for all discount factors α ∈ [α_{0}, 1) for some 0 ≤ α_{0} < 1. The next theorem shows even more, namely that the interval [0, 1) can be partitioned in a finite number of subintervals such that in each subinterval there exists a policy which is discounted optimal over the whole subinterval.

Theorem 29 There are numbers α_{m}, α_{m−1}, ..., α_{0}, α_{−1} and policies f_{m}^{∞}, f_{m−1}^{∞}, ..., f_{0}^{∞} such that (i) 0 = α_{m} < α_{m−1} < ⋯ < α_{0} < α_{−1} = 1; (ii) v^{α}(f_{j}^{∞}) = v^{α} for all α ∈ [α_{j}, α_{j−1}), j = m, m − 1, ..., 0. Proof. We give an outline of the proof. Since v^{α}(f^{∞}) is the solution of the system [I − αP (f)]x = r(f), each component v_{i}^{α}(f^{∞}) is a rational function in α. Suppose that a Blackwell optimal policy does not exist. Since for any fixed α a deterministic α-discounted optimal policy exists, this implies that there are series {α_{k} | k = 1, 2, … } and {f_{k} | k = 1, 2, … } such that α_{1} ≤ α_{2} ≤ ⋯ with lim_{k→∞} α_{k} = 1 and v^{α} = v^{α}(f_{k}^{∞}) > v^{α}(f_{k−1}^{∞}) for α = α_{k}, k = 2, 3, . . .. Because there is a finite number of deterministic policies this implies the existence of two policies, say f^{∞} and g^{∞}, that both are in turn optimal for an infinite number of increasing α’s with limit α = 1. Let h(α) = v^{α}(f^{∞}) − v^{α}(g^{∞}), then for any i ∈ E, h_{i}(α) is a continuous rational function in α on [0, 1), which has an infinite number of zeros. This contradicts the rationality of h_{i}(α). Hence, there exists a Blackwell optimal policy. With similar arguments, it can be shown that for each fixed α ∈ (0, 1] there is an interval around α and a policy which is optimal in that interval. These intervals are a covering of the closed bounded set [0, 1]. Hence, by the Heine-Borel-Lebesque theorem, it follows that there is a covering by a finite number of intervals.

We close this section with the treatment of the Laurent expansion of a stationary policy π^{∞}.

Theorem 30 Let u^{k}(π), k = −1, 0, … be defined by u^{−1}(π) = P^{∗}(π)r(π), u^{0}(π) = D(π)r(π) and u^{k+1}(π) = −D(π)u^{k}(π), k ≥ 0. Then, for α_{0}(π) < α < 1, we have v^{α}(π^{∞}) = α^{−1} · Σ_{k=−1}^{∞}[(1 − α)/α]^{k} · u^{k}(π), where α_{0}(π) =∥ D(π) ∥ /[∥ D(π) ∥ +1]. Proof. Let x(π) = α^{−1} · Σ_{k=−1}^{∞}[(1 − α)/α]^{k} · u^{k}(π). Then, x(π) = \frac{ϕ(π^{∞})}{1−α} + \frac{D(π)}{α} · Σ_{k=0}^{∞}\{[(α − 1)/α] · D(π)\}^{k}r(π) for ∥ [(α − 1)/α] · D(π) ∥< 1, i.e. α_{0}(π) < α < 1. Since v^{α}(π^{∞}) is the unique solution of the linear system [I −αP (π)]x = r(π), it is sufficient to show that r(π)−[I −αP (π)]x(π) = 0. This can be done in the following steps, using the results of theorem 27(i) and theorem 28(ii). r(π) − [I − αP (π)]x(π) = r(π) − [I − αP (π)](1 − α)^{−1}P^{∗}(π)r(π) − [I − αP (π)]α^{−1}D(π) · Σ_{k=0}^{∞}{[(α − 1)/α]D(π)}^{k}r(π) = r(π) − P^{∗}(π)r(π) − [α{I − P (π)}+(1−α)I]α^{−1}D(π)·Σ_{k=0}^{∞}{[(α−1)/α]D(π)}^{k}r(π) = [I −P^{∗}(π)]r(π)− [I − P^{∗}(π)]Σ_{k=0}^{∞}{[(α − 1)/α]D(π)}^{k}r(π) + Σ_{k=0}^{∞}{[(α − 1)/α]D(π)}^{k+1}r(π) = [I − P^{∗}(π)]r(π) − [I − P^{∗}(π)]Σ_{k=0}^{∞}{[(α − 1)/α]D(π)}^{k} · r(π) + Σ_{k=1}^{∞}{[(α − 1)/α]D(π)}^{k}r(π) = [I − P^{∗}(π)]r(π) − [I − P^{∗}(π)]r(π) − [I − P^{∗}(π) − I] · Σ_{k=1}^{∞}{[(α − 1)/α]D(π)}^{k}r(π) = 0.

Corollary 31 (i) ϕ(π) = lim_{α↑1}(1−α)v^{α}(π); (ii) v^{α}(π^{∞}) = \frac{ϕ(π^{∞})}{1−α} +u^{0}(π)+ ϵ(α), where lim_{α↑1} ϵ(α) = 0.

The first part of the Laurent expansion as presented in corollary 31(ii) was derived by Blackwell ^{\underline{bl62}} [27]. The complete Laurent expansion was proposed by Miller and Veinott ^{\underline{mil}} [167]. The vector u^{0}(π) is called the bias vector of policy π^{∞}.

1.4.2 The optimality equation

The multichain case

Before we introduce the optimality equation, we first give some prerequisites.

Lemma 32 lim_{α↑1}(1 − α)v^{α}(R) ≥ ϕ(R) for any policy R.

The proof of this theorem is based on Tauberian arguments which can be found in Derman ^{\underline{der70}} [58] or Hordijk ^{\underline{hor71}} [111].

Corollary 33 Any stationary Blackwell optimal policy is also average optimal. Proof. Let π^{∞} be any stationary Blackwell optimal policy. Then, by theorem 27(vi) ϕ(π^{∞}) = lim_{α↑1}(1 − α)v^{α}(π^{∞}) = lim_{α↑1}(1 − α)v^{α} ≥ lim_{α↑1}(1 − α)v^{α}(R) ≥ ϕ(R) for any policy R.

In the discounting case, the value vector is the unique solution of an optimality equation. A similar result holds for the average reward criterion, but the derivation is more complex.

Theorem 34 Consider the system

\{ \begin{matrix}x_{i} & = max_{a∈A(i)} Σ_{j}p_{ij}(a)x_{j}, & i ∈ E \\ x_{i} + y_{i} & = max_{a∈A(i,x)}\{r_{i}(a) + Σ_{j}p_{ij}(a)y_{j}\}, & i ∈ E \end{matrix}  (4.3)

where A(i, x) = {a ∈ A(i) | x_{i} = Σ_{j}p_{ij}(a)x_{j}}, i ∈ E. This system has the following properties: (i) x = u^{−1}(f_{0}), y = u^{0}(f_{0}), where f_{0}^{∞} is a Blackwell optimal policy, satisfies (4.3); (ii) If (x, y) is a solution of (4.3), then x equals the value vector ϕ. Proof. Since f_{0}^{∞} is a Blackwell optimal policy, we have for α ∈ [α_{0}, 1) v_{i}^{α}(f_{0}^{∞}) = v_{i}^{α} = max_{a∈A(i)}{r_{i}(a)+αΣ_{j}p_{ij}(a)v_{j}^{α}} ≥ r_{i}(a)+αΣ_{j}p_{ij}(a)v_{j}^{α}(f_{0}^{∞}), (i, a) ∈ E × A. Combining this result with corollary 31(ii) yields (1 − α)^{−1}ϕ_{i}(f_{0}^{∞}) + u_{i}^{0}(f_{0}) + ϵ_{i}(α) = v_{i}^{α}(f_{0}^{∞}) ≥ r_{i}(a) + αΣ_{j}p_{ij}(a)v_{j}^{α}(f_{0}^{∞}) = r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}^{α}(f_{0}^{∞}) − (1 − α)Σ_{j}p_{ij}(a)v_{j}^{α}(f_{0}^{∞}) = r_{i}(a) + Σ_{j}p_{ij}(a). [(1−α)^{−1}ϕ_{j}(f_{0}^{∞})+u_{j}^{0}(f_{0})+ϵ_{j}(α)]−(1−α)Σ_{j}p_{ij}(a)[(1−α)^{−1}ϕ_{j}(f_{0}^{∞})+u_{j}^{0}(f_{0})+ ϵ_{j}(α)], (i, a) ∈ E × A, α ∈ [α_{0}, 1]. This result holds for all α ∈ [α_{0}, 1), so comparing the terms with (1 − α)^{−1} gives ϕ_{i}(f_{0}^{∞}) ≥ Σ_{j}p_{ij}(a)ϕ_{j}(f_{0}^{∞}). Furthermore, when the terms with (1 − α)^{−1} are equal, we compare the terms with (1 − α)^{0}: u_{i}^{0}(f_{0}) ≥ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0}(f_{0}) − Σ_{j}p_{ij}(a)ϕ_{j}(f_{0}^{∞}) = r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0}(f_{0})− ϕ_{i}(f_{0}^{∞}) for each (i, a) with ϕ_{i}(f_{0}^{∞}) = Σ_{j}p_{ij}(a)ϕ_{j}(f_{0}^{∞}). Since ϕ(f_{0}^{∞}) = P (f_{0})ϕ(f_{0}^{∞}) and u^{0}(f_{0}) = D(f_{0})r(f_{0}) = r(f_{0}) − ϕ(f_{0}^{∞}) + P (f_{0})u^{0}(f_{0}), part (i) is shown. Next, we prove part (ii). Let (x, y) be a solution (4.3). Then, for any f^{∞}, x ≥ P (f)x, implying x ≥ P^{∗}(f)x and consequently p_{ij}^{∗}(f){x_{j} −[P (f)x]_{j}} = 0 for every i, j ∈ E. Let i be a recurrent state in the Markov chain induced by P (f). Since p_{ii}^{∗}(f) > 0, f(i) ∈ A(i, x) and x_{i} + y_{i} ≥ r_{i}(f) + Σ_{j}p_{ij}(f)y_{j}. Therefore, P^{∗}(f)[x + y] ≥ P^{∗}(f)[r(f) + P (f)y] = ϕ(f^{∞}) + P^{∗}(f)y, i.e. ϕ(f^{∞}) ≤ P^{∗}(f)x ≤ x. On the other hand, any solution of the system gives a policy g^{∞} which satisfies x = P (g)x and x + y = r(g) + P (g)y. Hence, x = P^{∗}(g)x, and ϕ(g^{∞}) = P^{∗}(g)r(g) = P^{∗}(g)[x + y − P (g)y] = x. This completes the proof that x = max_{f} ϕ(f^{∞}) = ϕ.

The unichain case

In the unichain case, for every policy f^{∞}, the stationary matrix P^{∗}(f) has identical components. Hence, the value vector ϕ is a constant vector, i.e. ϕ_{i} = Σ_{j}p_{ij}(a)ϕ_{j}, i ∈ E, a ∈ A(i). We will denote this constant vector by ϕ·e (ϕ is a scalar). The first part of the optimality equation is always satisfied and the following result can be derived.

Theorem 35 Consider the system x+y_{i} = max_{a}{r_{i}(a)+Σ_{j}p_{ij}(a)y_{j}}, i ∈ E. This system has the following properties: (i) x · e = u^{−1}(f_{0}), y = u^{0}(f_{0}), where f_{0}^{∞} is a Blackwell optimal policy, satisfies this system; (ii) If (x, y) is a solution of the system, then x = ϕ and y = u^{0}(f_{0}) + c · e for some constant c.

The functional equation (4.3) is extensively investigated in Schweitzer and Federgruen ^{\underline{schw78b}} [217]. Another proof for the solution of the optimality equation can also be provided by applying Brouwer’s fixed point theorem (see Federgruen and Schweitzer ^{\underline{fed84a}} [72], and Schweitzer ^{\underline{schw87}} [213]. In the unichain case the solution of the optimality equation can be exhibited as the fixed point of an N-step contraction (cf. Federgruen, Schweitzer and Tijms ^{\underline{fst78}} [74].

1.4.3 Policy iteration

In the policy iteration method a sequence of policies f_{1}^{∞}, f_{2}^{∞}, … is constructed such that ϕ(f_{k+1}^{∞}) ≥ ϕ(f_{k}^{∞}) and v^{α}(f_{k+1}^{∞}) > v^{α}(f_{k}^{∞}) for all α ∈ (α_{k}, 1). Since there are finite deterministic policies and all policies f_{k}^{∞} are different, this method has a finite termination with an optimal policy.

The multichain case

Theorem 36 Consider the following system of linear equations

\begin{cases}[I − P (f)] & x & & = 0 \\ & x + [I − P (f)] & y & = r(f) \\ & & y + [I − P (f)]z & = 0. \end{cases}  (4.4)

Then, (4.4) has a solution (x(f), y(f), z(f)), where x(f) and y(f) are unique with x(f) = u^{−1}(f) and y(f) = u^{0}(f).

Proof. We first show that x(f) = u^{−1}(f), y(f) = u^{0}(f) and z(f) = u^{1}(f) is a solution of (4.4). We can write, I − P (f)]x(f) = [I − P (f)]u^{−1}(f) = [I − P (f)]P^{∗}(f)]r(f) = 0. x(f) + [I − P (f)]y(f) = P^{∗}(f)]r(f) + [I − P (f)]D(f)r(f) = {P^{∗}(f)] + [I − P (f)]D(f)} r(f) = r(f). y(f) + [I − P (f)]z(f) = D(f)r(f) − [I − P (f)]D(f)^{2}r(f) = {I − [I − P (f)]D(f)}D(f)r(f) = P^{∗}(f)D(f)r(f) = 0. Next, let (x, y, z) be any solution of (4.4). Then, x = P (f)x implies x = P^{∗}(f)x = P^{∗}(f){r(f) − [I − P (f)]y} = P^{∗}(f)r(f) = u^{−1}(f). Since y + [I − P (f)]z = 0, P^{∗}(f)y = 0, we can write {[I − P (f)] + P^{∗}(f)}y = [I − P (f)]y = r(f) − P^{∗}(f)r(f), i.e. y = {[I−P (f)]+P^{∗}(f)}^{−1}[I−P^{∗}(f)]r(f) = [D(f)+P^{∗}(f)][I−P^{∗}(f)]r(f) = D(f)r(f) = u^{0}(f).

For every i ∈ E and every policy f^{∞}, we define the action subset B(i, f) by

B(i, f) = \{a ∈ A(i) | \begin{matrix}Σ_{j}p_{ij}(a)ϕ_{j}(f^{∞}) > ϕ_{i}(f^{∞}) or \\ Σ_{j}p_{ij}(a)ϕ_{j}(f^{∞}) = ϕ_{i}(f^{∞}) and \\ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0}(f) > ϕ(f^{∞}) + u_{i}^{0}(f) \end{matrix} \} (4.5)

Theorem 37 (i) If B(i, f) = ∅ for every i ∈ E, then f^{∞} is an average optimal policy; (ii) If B(i, f) ≠ ∅ for at least one i and the policy g^{∞} satisfies g ≠ f and g(i) ∈ B(i, f) if g(f) ≠ f(i), then ϕ(g^{∞}) ≥ ϕ(f^{∞}) and v^{α}(g^{∞}) > v^{α}(f^{∞}) for α sufficiently close to 1. Proof. (i) Since B(i, f) = ∅ for every i ∈ E, we have for any policy h^{∞}, Σ_{j}p_{ij}(h)ϕ_{j}(f^{∞}) ≤ ϕ_{i}(f^{∞}) and r_{i}(h) + Σ_{j}p_{ij}(h)u_{j}^{0}(f) ≤ ϕ_{i}(f^{∞}) + u_{i}^{0}(f), if Σ_{j}p_{ij}(h)ϕ_{j}(f^{∞}) = ϕ_{i}(f^{∞}). Let policy R = (h, f, f, …). Then, v^{α}(R) = r(h) + αP (h)v^{α}(f^{∞}). From theorem 30 it follows that αv^{α}(f^{∞}) = α · \frac{ϕ(f^{∞})}{1−α} + u^{0}(f) + ϵ(α) = \frac{ϕ(f^{∞})}{1−α} + u^{0}(f) − ϕ(f^{∞}) + ϵ_{1}(α), implying v^{α}(R) = r(h)+P (h)\{\frac{ϕ(f^{∞})}{1−α} +u^{0}(f)−ϕ(f^{∞})+ϵ_{1}(α)\} = (1−α)^{−1}P (h)ϕ(f^{∞})+r(h)+ P (h)u^{0}(f) + ϵ_{1}(α). Since v^{α}(f^{∞}) = (1 − α)^{−1}ϕ(f^{∞}) + u^{0}(f) + ϵ_{2}(α), we have

v^{α}(f^{∞}) −v^{α}(R) = (1 − α)^{−1}[ϕ(f^{∞}) − P (h)ϕ(f^{∞})] + u^{0}(f) − r(h)
−P (h)u^{0}(f) + ϵ_{3}(α), where lim_{α↑1} ϵ_{k}(α) = 0, k = 1, 2, 3.

(4.6)

Hence, v^{α}(f^{∞}) ≥ v^{α}(R) + ϵ(α) = r(h) + αP (h)v^{α}(f^{∞}) + ϵ(α) for α close to 1 and [I − αP (h)]v^{α}(f^{∞}) ≥ r(h) + ϵ(α). Therefore, v^{α}(f^{∞}) ≥ [I − αP (h)]^{−1}[r(h) + ϵ(α)] = v^{α}(h^{∞}) + (1 − α)^{−1} · ϵ(α) for α close to 1. From the Laurent expansion it follows that ϕ(f^{∞}) ≥ ϕ(h^{∞}), i.e. policy f^{∞} is an average optimal policy. (ii) Let R = (g, f, f, …). Then, if g(i) = f(i), row i of P (f) is identical to row i of P (g) and r_{i}(g) = r_{i}(f) i.e. v_{i}^{α}(R) = [r(g) + αP (g)v^{α}(f^{∞})]_{i} = [r(f)+αP (f)v^{α}(f^{∞})]_{i} = v_{i}^{α}(f^{∞}). If g(i) ≠ f(i), then g(i) ∈ B(i, f), and by formula (4.6) for h = g, v_{i}^{α}(f^{∞})−v_{i}^{α}(R) = (1−α)^{−1}[ϕ(f^{∞})−P (g)ϕ(f^{∞})]_{i} + [u^{0}(f) − r(g) − P (g)u^{0}(f) − P (g)ϕ(f^{∞})]_{i} + ϵ_{3}(α) < 0 for α sufficiently close to 1. Hence, for α sufficiently close to 1, v^{α}(R) = r(g)+αP (g)v^{α}(f^{∞}) = L_{g}v^{α}(f^{∞}) > v^{α}(f^{∞}), and, by lemma 17, v^{α}(g^{∞}) > v^{α}(f^{∞}). Then, by the Laurent expansion, it follows that ϕ(g^{∞}) ≥ ϕ(f^{∞}).

Algorithm VI (policy iteration; average rewards, multichain case)

1. Start with any deterministic policy f^{∞}.

2. Determine ϕ(f^{∞}) and u^{0}(f) as unique (x, y)-part in a solution of the linear system (4.4).

3. Determine for every i ∈ E : B(i, f) defined in (4.5).

4. If B(i, f) = ∅ for every i ∈ E: go to step 6.

Otherwise: take any g ≠ f such that, if g(i) ≠ f(i), g(i) ∈ B(i, f).

5. f = g and go to step 2.

6. f^{∞} is an average optimal policy.

The unichain case

In the unichain case, since the average reward vectors are constant, the set B(i, f) can be simplified to

B(i, f) = {a ∈ A(i)|r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0} > ϕ(f) + u_{i}^{0}(f)}  (4.7)

The following result can be shown.

Theorem 38 The linear system x · e + [I − P (f)]y = r(f) with y_{1} = 0, has a unique solution x = ϕ(f^{∞}) and y = u^{0}(f) − u_{1}^{0}(f).

Algorithm VII (policy iteration; average rewards, unichain case)

1. Start with any deterministic policy f^{∞}.

2. Determine ϕ(f^{∞}) and u^{0}(f) as unique solution of the linear system

x · e + [I − P (f)]y = r(f) with y_{1} = 0.

3. Determine for every i ∈ E : B(i, f) defined in (4.7).

4. If B(i, f) = ∅ for every i ∈ E: go to step 6.

Otherwise: take any g ≠ f such that, if g(i) ≠ f(i), g(i) ∈ B(i, f).

5. f = g and go to step 2.

6. f^{∞} is an average optimal policy.

The concept of policy iteration is originated by Howard ^{\underline{ho60}} [122] who considered the first two parts of the system (4.4). However, in that case, the convergence is not always guaranteed and cycling can occur. Blackwell ^{\underline{bl62}} [27] has given a convergent version by imposing on y the constraint P^{∗}(f)y = 0. In order to compute P^{∗}(f) the chain structure of the transition matrix P (f) has to be analysed. The formulation with system (4.4) was proposed by Miller and Veinott ^{\underline{mil}} [167]. Other anti-cycling rules, which avoid the analysis of the chain structure, are introduced in Schweitzer and Federgruen ^{\underline{schw78a}} [216], Federgruen and Spreen ^{\underline{fedspre80}} [75], and Spreen ^{\underline{spr}} [233]. Various treatments of the policy iteration method in the unichain case (or other special cases) can be found in Schweitzer ^{\underline{schw71a}} [209], Denardo ^{\underline{den73}} [49], Haviv and Puterman ^{\underline{haviv}} [100], and Lasserre ^{\underline{las94a}} [152].

1.4.4 Linear programming

A vector v ∈ ℝ^{N} is said to be average-superharmonic if there exists a vector u ∈ ℝ^{N} such that the pair (u, v) satisfies

\{ \begin{matrix}v_{i} & ≥ Σ_{j}p_{ij}(a)v_{j} & for every (i, a) ∈ E × A \\ v_{i} + u_{i} & ≥ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j} & for every (i, a) ∈ E × A \end{matrix}  (4.8)

Theorem 39 The value vector ϕ is the (componentwise) smallest averagesuperharmonic vector. Proof. Let f_{0}^{∞} be a Blackwell optimal policy. From theorem 34 it follows that ϕ_{i} ≥ Σ_{j}p_{ij}(a)ϕ_{j}, (i, a) ∈ E × A, and ϕ_{i} + u_{i}^{0}(f_{0}) ≥ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0}(f_{0}) for every i ∈ E and a ∈ A(i, ϕ), where A(i, ϕ) = {a ∈ A(i) | ϕ_{i} = Σ_{j}p_{ij}(a)ϕ_{j}}. Let A^{∗}(i) = {a ∈ A(i) | ϕ_{i} + u_{i}^{0}(f_{0}) < r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}^{0}(f_{0})}, i ∈ E, and s_{ia} = ϕ_{i} −Σ_{j} p_{ij}(a)ϕ_{j}, t_{ia} = ϕ_{i} +u_{i}^{0}(f_{0})−r_{i}(a)+ Σ_{j}p_{ij}(a)u_{j}^{0}(f_{0}), a ∈ A(i), i ∈ E. Define M = min{s_{ia}/t_{ia} | a ∈ A^{∗}(i), i ∈ E} (M = 0 if ∪_{i∈E}A^{∗}(i) = ∅) and u = u^{0}(f_{0}) − M · ϕ. For a ∈ A(i, ϕ), we have ϕ_{i} = Σ_{j}p_{iaj}ϕ_{j} and ϕ_{i} + u_{i} = ϕ_{i} + u_{i}^{0}(f_{0}) − M · ϕ_{i} ≥ r_{i}(a) + Σ_{j}p_{ij}(a)[u_{j}^{0}(f_{0}) − M · ϕ_{j}] = r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}. For a ∈ A^{∗}(i) or a ∉ A(i, ϕ) ∪ A^{∗}(i), we can derive: ϕ_{i} > Σ_{j}p_{ij}(a)ϕ_{j} and ϕ_{i} + u_{i} ≥ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}. Hence, ϕ is average-superharmonic. Suppose that y is also average-superharmonic with corresponding x. Then, y ≥ P (f_{0})y, implying that y ≥ P^{∗}(f_{0})y ≥ P^{∗}(f_{0}){r(f_{0}) + [P (f_{0}) − I]x} = P^{∗}(f_{0})r(f_{0}) = ϕ(f_{0}^{∞}) = ϕ, i.e. ϕ is the smallest average-superharmonic vector.

The multichain case

Corollary 40 Let (u, v) be an optimal solution of the linear program

min \{Σ_{j}β_{j}v_{j} |\begin{matrix}& Σ_{j}[δ_{ij} − p_{ij}(a)v_{j}] ≥ 0 & , (i, a) ∈ E × A \\ v_{i}+ & Σ_{j}[δ_{ij} − p_{ij}(a)u_{j}] ≥ r_{i}(a) & , (i, a) ∈ E × A \end{matrix}\}  (4.9)

where β_{j} > 0, j ∈ E, is arbitrarily chosen, then u = ϕ.

The dual program of (4.9) is

max \{Σ_{i,a}r_{i}(a)x_{ia} | \begin{matrix}Σ_{i,a}[δ_{ij} − p_{ij}(a)]x_{ia} & = 0 & , j ∈ E \\ Σ_{a}x_{ja} + Σ_{i,a}[δ_{ij} − p_{ij}(a)y_{ia} & = β_{j} & , j ∈ E \\ x_{ia}, y_{ia} ≥ 0, (i, a) ∈ E × A \end{matrix} \} (4.10)

For any feasible solution (x, y) of (4.10) we denote by E_{x}

E_{x} = {j ∈ E | Σ_{a}x_{ja} > 0}  (4.11)

Theorem 41 Let (x, y) be an extreme optimal solution of (4.10). Then, any

policy f^{∞} such that\{ \begin{matrix}x_{if(i)} > 0 & if & i ∈ E_{x} \\ y_{if(i)} > 0 & if & i ∉ E_{x} \end{matrix} is an average optimal policy.

Proof. We will give an outline of the proof. First, we show that f^{∞} is well defined, because for every j ∈ E, Σ_{a}x_{ja} + Σ_{a}y_{ja} = Σ_{i,a}p_{ij}(a)y_{ia} + β_{j} > 0. Since x_{if(i)} > 0, i ∈ E_{x} and y_{if(i)} > 0, i ∉ E_{x}, it follows from the complementary slackness of linear programming that ϕ_{i} + Σ_{j}[δ_{ij} − p_{ij}(f(i))]u_{j} = r_{i}(f), i ∈ E_{x} and Σ_{j}[δ_{ij} − p_{ij}(f(i))]ϕ_{j} = 0, i ∉ E_{x}. Program (4.9) implies that Σ_{j}[δ_{ij} − p_{ij}(a)]ϕ_{j} ≥ 0, i ∈ E, a ∈ E. Suppose that Σ_{j}[δ_{kj} − p_{kj}(f(k))]ϕ_{j} > 0 for some k ∈ E_{x}. Since x_{kf(k)} > 0, Σ_{j}[δ_{kj} − p_{kj}(f(k))]ϕ_{j} · x_{kf(k)} > 0. Furthermore, Σ_{j}[δ_{ij} − p_{ij}(a)]ϕ_{j} · x_{ia} ≥ 0, (i, a) ∈ E × xA. Hence, Σ_{i,a}Σ_{j}[δ_{ij} − p_{ij}(a)ϕ_{j} · x_{ia} > 0. On the other hand, this result is contradictory to the constraints of program (4.10) because Σ_{i,a}Σ_{j}[δ_{ij} − p_{ij}(a)]ϕ_{j} · x_{ia} = Σ_{j}{[Σ_{i,a}[δ_{ij} − p_{ij}(a)x_{ia}]}ϕ_{j} = 0. Thus, we have shown that Σ_{j}[δ_{ij} − p_{ij}(f(i))]ϕ_{j} = 0 for every i ∈ E, i.e. ϕ = P (f)ϕ, and consequently ϕ = P^{∗}(f)ϕ. Next, it can easily be shown that E_{x} is closed under P (f), i.e. p_{ij}(f(i)) = 0 for i ∈ E_{x}, j ∉ E_{x}. Then, we can prove that the states of E\E_{x} are transient in the Markov chain induced by P (f) (therefore we use the property that the columns corresponding to the basic variables of a basic solution of an LP are linear independent). This implies that the columns of E\E_{x} in P^{∗}(f) are zero. Now, we can finish the proof as follows. For every k ∈ E, we can write, ϕ_{k}(f^{∞}) = [P^{∗}(f)r(f)]_{k} = Σ_{i}[P^{∗}(f)]_{ki}r_{i}(f) = Σ_{i∈E_{x}}[P^{∗}(f)]_{ki}r_{i}(f) = Σ_{i∈E_{x}}[P^{∗}(f)]_{ki}{ϕ_{i}+Σ_{j}[δ_{ij}−p_{ij}(f(i))]u_{j}} = [P^{∗}(f){ϕ+{(I−P (f))u}]_{k} = ϕ_{k}. Hence, f^{∞} is an average optimal policy.

Algorithm VIII (linear programming; average rewards, multichain case)

1. Take any β with β_{j} > 0, j ∈ E, and compute extreme optimal solutions (u, v) and (x, y) of the dual pair linear programs (4.9) and (4.10) respectively.

2. Choose f^{∞} such that x_{if(i)} > 0 if i ∈ E_{x} and y_{if(i)} > 0 if i ∉ E_{x}. Then, f^{∞} is an average optimal policy and v is the value vector ϕ.

In the average reward case there is no one-to-one correspondence between the feasible solutions of the dual program (4.10) and the stationary policies. However, there are interesting relations. For a feasible solution (x, y) of (4.10) we define a stationary policy π^{∞}(x, y) by

π_{ia}(x, y) = \{ \begin{matrix}x_{ia}/Σ_{a}x_{ia} & a ∈ A(i), & i ∈ E_{x} \\ y_{ia}/Σ_{a}y_{ia} & a ∈ A(i), & i ∉ E_{x} \end{matrix}  (4.12)

Conversely, consider a stationary policy π^{∞}, and define (x(π), y(π)) by

\begin{cases}x_{ia}(π) & = [Σ_{k}β_{k}p_{ki}^{∗}(π)] · π_{ia} & a ∈ A(i), & i ∈ E \\ y_{ia}(π) & = [Σ_{k}β_{k}d_{ki}(π) + Σ_{k}γ_{k}p_{ki}^{∗}(π)] · π_{ia} & a ∈ A(i), & i ∈ E \end{cases}  (4.13)

with γ_{k} = max_{i∈E_{j}}{−Σ_{k}β_{k}d_{ki}(π)/Σ_{k}p_{ki}^{∗}(π)}, k ∈ E_{j}, where E_{j} is the j-th ergodic set of the transition matrix P (π), and γ_{k} = 0 for k a transient state. Then, the following results can be derived (see Kallenberg ^{\underline{kal83}} [135]).

Theorem 42 (i) (x(π), y(π)) is feasible for (4.10) and for a deterministic policy f^{∞} (x(f), y(f)) is an extreme point of (4.10); (ii) if π^{∞} is an average optimal policy, then (x(π), y(π)) is an optimal solution of (4.10) and viceversa.

Remarks

– As mentioned before, the only available methods for MDPs with constraints are based on linear programming. In the multichain case, there is no optimal stationary policy, in general. The variables x_{ia} of program (4.10) can, analogously to the discounted case, be interpreted as average state-action frequencies, but the analysis is much more complex. For the unichain case, this analysis can be found in Derman ^{\underline{der70}} [58]; the multichain case is treated by Hordijk and Kallenberg ^{\underline{hor84b}} [117]. An interpretation of the second type of variables, the variables y_{ia}, is not obvious. They are related to the deviation matrix (Kallenberg ^{\underline{kal83}} [135] and can be interpreted as biased deviation measures (Altman and Spieksma ^{\underline{alsp95}} [8]). Other contributions in this area, based on the sample path approach, are Ross ^{\underline{ross89}} [196] and Ross and Varadarajan ^{\underline{ross91}} [197]. Beutler and Ross ^{\underline{beut85}} [25] discuss the constrained MDP by a Lagrangean approach. In Altman and Shwartz ^{\underline{alsh91a}} [4] the sensitivity of constrained MDPs is investigated.

– MDPs with multi-objectives can be treated as constrained MDPs. For this topic we refer to Hordijk and Kallenberg ^{\underline{hor84b}} [117], and to Durinovics, Lee, Katehakis and Filar ^{\underline{dur}} [65].

– Only expected values can be insufficient for a decision maker. It may be desirable to consider also the variability. The last fifteen years dozens of papers on this subject are published. We mention Sobel ^{\underline{so85}} [229], ^{\underline{so94}} [230], Kawai and Katoh ^{\underline{kaka87}} [144], White ^{\underline{white882}} [283], ^{\underline{white92}} [284] and ^{\underline{white94}} [287], Filar, Kallenberg and Lee ^{\underline{filar89}} [78], Chung ^{\underline{chung89}} [37], ^{\underline{chung92}} [38] and ^{\underline{chung94}} [39], Bayal-Gursoy and Ross ^{\underline{bayros92}} [12], and Huang and Kallenberg ^{\underline{huang}} [124].

Open problem For MDPs with constraints, an interesting question is find the best policy in the class of stationary policies π^{∞} or in the class of deterministic policies f^{∞}. In the multichain case, no satisfactory algorithm is known for these problems. For the problem in stationary policies, the natural candidate π^{∞}(x, y) with (x, y) the optimal solution of (4.10) with additional constraints does not satisfy (see Kallenberg ^{\underline{kal83}} [135]).

The unichain case

Since ϕ is a vector with identical components, in the unichain case the property average-superharmonic is equivalent to the existence of a scalar v and a vector u such that v + u_{i} ≥ r_{i}(a) + Σ_{j}p_{ij}(a)u_{j} for every (i, a) ∈ E×A. Hence, the LP-problem for the smallest average-superharmonic vector becomes

min{v | v + Σ_{j}[δ_{ij} − p_{ij}(a)]u_{j} ≥ r_{i}(a) for every (i, a) ∈ E × A} (4.14)

with dual program

max \{Σ_{i,a}r_{i}(a)x_{ia} | \begin{matrix}Σ_{i,a}[δ_{ij} − p_{ij}(a)] & x_{ia} & = 0, & j ∈ E \\ Σ_{i,a}x_{ia} & & = 1 \\ & x_{ia} & ≥ 0, & (i, a) ∈ E × A \end{matrix}\} (4.15)

Algorithm IX (linear programming; average rewards, unichain case)

1. Compute extreme optimal solutions (u, v) and x of the dual pair LPs (4.14) and (4.15) respectively.

2. Choose f^{∞} such that x_{if(i)} > 0 if i ∈ E_{x} and f(i) arbitrary if i ∉ E_{x}. Then, f^{∞} is an average optimal policy and v · e is the value vector ϕ.

Remarks

1. In the irreducible case any feasible solution of (4.14) satisfies Σ_{a}x_{ia} > 0, i ∈ E. Furthermore, the mapping x_{ia} → π^{∞}(x) with π_{ia}(x) = x_{ia}/Σ_{a}x_{ia} is a one-to-one mapping of the feasible solutions of (4.14) onto the stationary policies with as inverse mapping π^{∞} → x_{ia}(π), where x_{ia}(π) = p_{i}^{∗}(π) · π_{ia} with p^{∗}(π) the equilibrium distribution. The set of deterministic policies corresponds to the set of extreme solutions of (4.14). In this case, similar to the discounted reward criterion, it can be shown that the linear programming method is equivalent to policy iteration. For the relation between the discounted linear program and the undiscounted linear program in the irredicuble case, we refer also to Nazareth and Kulkarni ^{\underline{naz}} [171].

2. In the unichain case, also a suboptimality test can be implemented, in the policy iteration method as well as in the linear programming method (cf. Hastings ^{\underline{hast76}} [96] and Lasserre ^{\underline{las94b}} [153]). Furthermore, in the unichain case, problems with constraints have a sulution in the set of stationary policies: if (x, y) is the optimal solution of the LP -problem with constraints, then π^{∞}(x, y) with π_{ia}(x, y) = x_{ia}/Σ_{a}x_{ia}, a ∈ A(i), i ∈ E_{x} (and arbitrary decisions in E\E_{x}) is a stationary optimal policy (see Derman ^{\underline{der70}} [58]).

The pioneering work in solving MDPs by linear programming was made by Manne ^{\underline{manne60}} [165] and De Ghellinck ^{\underline{degh60}} [42], who considered the irreducible case. The first analysis in the general multichain case was described in Denardo and Fox ^{\underline{denfox68}} [51] and Denardo ^{\underline{den70}} [47], who proposed a sequential procedure. Hordijk and Kallenberg ^{\underline{hor79}} [115] have shown that also in the multichain case one linear program suffices. Many results about the linear programming method can be found in Kallenberg ^{\underline{kal83}} [135].

1.4.5 Value iteration

It seems natural to investigate for value iteration the formula of the discounted rewards with discount factor α = 1, i.e.

\{ \begin{matrix}v_{i}^{n+1} = max_{a}\{r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}^{n}\}, i ∈ E, n ≥ 0 \\ v_{i}^{0} arbitrary, i ∈ E \end{matrix}  (4.16)

with corresponding policies f_{0}^{∞}, f_{1}^{∞}, … such that v^{n+1} = r(f_{n}) + P (f_{n})v^{n}, n ≥ 0.

This approach, however, causes difficulties: in general, there is no convergence of the sequences {v^{n} | n ≥ 0} or {v^{n} − v^{n−1} | n ≥ 1}. Since v^{n} corresponds to total rewards during n periods, the sequence {v^{n} | n ≥ 0} is in general unbounded and grows linearly in n. Therefore, it is plausible to consider the sequence {v^{n} − n · ϕ| n ≥ 0}. The next lemma, which appeared in Brown ^{\underline{brown}} [29], shows that this sequence is bounded. The behaviour of this sequence is also studied by Lanery ^{\underline{lan}} [151].

Lemma 43 The sequence {v^{n} − n · ϕ | n ≥ 0} is bounded. Proof. Let f_{∗}^{∞} be a Blackwell optimal policy. From the proof of theorem 39 it follows that (v, u) with v = ϕ(f_{∗}^{∞}) = ϕ and u = u^{0}(f_{∗})−M ·ϕ(f_{∗}^{∞}), for the choice of M see the proof of theorem 39, satisfies the superharmonicity inequalities, i.e. ϕ ≥ P (f)ϕ and ϕ + u ≥ P (f)u + r(f) with equality for f = f_{∗}. It is sufficient to show that the sequence {e^{n} = v^{n}−n·ϕ−u | n ≥ 0} is bounded. For n ≥ 1, we have, P (f_{∗})e^{n−1} = P (f_{∗})v^{n−1} −(n−1)ϕ−P (f_{∗})u ≤ v^{n} −r(f_{∗})−(n−1)ϕ+r(f_{∗})− ϕ − u = v^{n} − n · ϕ − u = e^{n}, implying that P^{n}(f_{∗})e^{0} ≤ e^{n}. Furthermore, P (f_{n−1})e^{n−1} ≥ P (f_{n−1})v^{n−1} −(n−1)ϕ+[r(f_{n−1})−ϕ−u] = v^{n} −n·ϕ−u = e^{n}. Hence, P^{n}(f_{∗})e^{0} ≤ e^{n} ≤ P (f_{n−1})P (f_{n−2}) ⋯ P (f_{0})e^{0}, and consequently [min_{i} e_{i}^{0}] · e ≤ e^{n} ≤ [max_{i} e_{i}^{0}] · e, n ≥ 0.

Corollary 44 (i) ϕ = lim_{n→∞} \frac{1}{n}v^{n}; (ii) ϕ = lim_{n→∞} \frac{1}{n}Σ_{k=1}^{n}(v^{k} − v^{k−1}).

Although corollary 44 shows that ϕ can be approximated by the sequence \{\frac{1}{n}v^{n} | n ≥ 1\}, this result does not provide sufficient information for the computation of an ϵ-optimal policy or an ϵ-approximation of ϕ. Therefore, we need stronger results, e.g. the convergence of the sequence {v^{n}−n·ϕ}_{n=0}^{∞}. In general, however, this sequence may fail to converge if some of the transition matrices P (f) are periodic. Fortunately, periodicity can be avoided by the following data transformation, proposed by Schweitzer ^{\underline{schw71b}} [210]. Schweitzer and Federgruen ^{\underline{schw77}} [215] have given necessary and sufficient conditions which guarantee the convergence of the sequence {v^{n} − n · ϕ}_{n=0}^{∞}.

Consider for an arbitrary λ ∈ (0, 1) the modified transition probabilities

p_{ij}^{λ}(a) = λδ_{ij} + (1 − λ)p_{ij}(a), i, j ∈ E and a ∈ A(i)  (4.17)

Since p_{ii}^{λ}(f) ≥ λ > 0, the transition matrix P^{λ}(f) is aperiodic. Let ϕ^{λ}(f^{∞}) be the average reward of policy f^{∞} with respect to the transitions (4.17), then the next lemma shows that ϕ^{λ}(f^{∞}) = ϕ(f^{∞}). Hence, we may assume that for every f^{∞} the Markov chain with transition matrix P (f) is aperiodic, in which case P^{∗}(f) = lim_{n→∞} P^{n}(f). The next lemma can be shown by the properties of the stationary and the deviation matrix as mentioned in theorem 28.

Lemma 45 ϕ^{λ}(f^{∞}) = ϕ(f^{∞}) for every deterministic policy f^{∞}.

To show that, under the aperiodicity assumption, the sequence {e^{n}}_{n=0}^{∞} is convergent, we need the following theorem.

Theorem 46 Let b_{ia} = r_{i}(a) − ϕ_{i} + Σ_{j}p_{ij}(a)u_{j} − u_{i}; m_{i} = lim inf_{n→∞} e_{i}^{n}, i ∈ E; M_{i} = lim sup_{n→∞} e_{i}^{n}, i ∈ E and A_{∗}(i) = {a ∈ A(i)|ϕ_{i} = Σ_{j}p_{ij}(a)ϕ_{j}}, i ∈ E. Then, max_{a∈A_{∗}(i)}{b_{ia} + Σ_{j}p_{ij}(a)m_{j}} ≤ m_{i} ≤ M_{i} ≤ max_{a∈A_{∗}(i)}{b_{ia} + Σ_{j}p_{ij}(a)M_{j}}.

Let F_{0} = {f^{∞}|P (f)ϕ = ϕ and r(f) + P (f)u = ϕ + u}, where u is the vector mentioned in the proof of theorem 43.

Theorem 47 Assume that the aperiodicity assumption holds. Then, the sequence {e^{n}|n ≥ 0} is convergent. Proof. Let α and β be two limit vectors of the sequence {e^{n}}_{n=0}^{∞}, and suppose that n_{k} and m_{k} satisfy α_{j} = lim_{k→∞} e_{j}^{n_{k}} and β_{j} = lim_{k→∞} e_{j}^{m_{k}}, j ∈ E. Choose for every k an integer h(k) such that r_{k} = m_{h(k)} − n_{k} ≥ k. From theorem 43(i), we obtain e^{m_{h(k)}} = e^{r_{k}+n_{k}} ≥ [P (f)]^{r_{k}}e^{n_{k}}, k ∈ N Hence, for any policy f^{∞} ∈ F_{0}, β = lim_{k→∞} e^{m_{h(k)}} ≥ lim_{k→∞}[P (f)]^{r_{k}} · e^{n_{k}} ≥ lim_{k→∞}[P (f)]^{k} · e^{n_{k}} = P^{∗}(f)α Similarly we obtain α ≥ P^{∗}(f)β. Since α ≥ P^{∗}(f)β ≥ P^{∗}(f)α, we have for every recurrent state j, α_{j} = [P^{∗}(f)α]_{j} and similarly β_{j} = [P^{∗}(f)β]_{j}. Therefore, m_{j} = α_{j} ≥ [P^{∗}(f)β]_{j} = β_{j} = M_{j} for every recurrent state j, i.e. m_{j} = M_{j} for every state which is recurrent under P (f) for some f^{∞} ∈ F_{0}.

Let f_{∗} such that f_{∗}(i) ∈ A_{∗}(i), i ∈ E, and b(f_{∗}) + P (f_{∗})M = max_{E×A_{∗}}{b + P M}. By theorem 46, b(f_{∗}) + P (f_{∗})M ≥ M, implying P^{∗}(f_{∗})b(f_{∗}) ≥ 0. Since (ϕ, u) is superharmonic, b(f_{∗}) ≤ 0, i.e. b_{j}(f_{∗}) = 0 for j recurrent under f_{∗}. Take f^{∞} equal to f_{∗}^{∞} on the states which are recurrent under f_{∗}, and equal to a policy f_{0}^{∞} ∈ F_{0} on the transient states. Then, the states which are recurrent under f_{∗} are a subset of the states which are recurrent under f, i.e. m_{j} = M_{j} for the states j recurrent under f_{∗}. By theorem 46, we obtain b(f_{∗})+P (f_{∗})m ≤ m ≤ M ≤ b(f_{∗})+P (f_{∗})M, i.e. P (f_{∗})(M −m) ≥ M −m ≥ 0, and consequently, P^{∗}(f_{∗})(M −m) ≥ M −m ≥ 0. Since m_{j} = M_{j} for the states j recurrent under f_{∗}, P^{∗}(f_{∗})(M − m) = 0, implying that by M = m.

Lemma 48 Assume that the sequence {v^{n} − n · ϕ}_{n=0}^{∞} converges. Then, (i) f_{n}^{∞} is average optimal for n sufficiently large; (ii) ϕ = lim_{n→∞}(v^{n+1} − v^{n}). Proof. (i) Let v^{∗} = lim_{n→∞}[v^{n} − n · ϕ], i.e. v^{∗} = v^{n} − n · ϕ + O(1). Hence, v^{n+1} = r(f_{n})+P (f_{n})[v^{∗}+n·ϕ+O(1)]. On the other hand, v^{n+1} = v^{∗}+ (n+ 1)ϕ + O(1). From r(f_{n}) + P (f_{n})v^{∗} + n · P (f_{n})ϕ + O(1) = v^{∗} + (n + 1)ϕ for all n, we have for n sufficiently large, P (f_{n})ϕ = ϕ and r(f_{n})+P (f_{n})v^{∗} = v^{∗} +ϕ, which implies that ϕ = P^{∗}(f_{n})ϕ = P^{∗}(f_{n})[r(f_{n}) + P (f_{n})v^{∗} − v^{∗}] = ϕ(f_{n}^{∞}). (ii) ϕ = (v^{n+1} − v^{n}) − (e^{n+1} − e^{n}). Since the sequence {e^{n}}_{n=0}^{∞} converges, ϕ = lim_{n→∞}(v^{n+1} − v^{n}).

The multichain case

Since, for large n, ϕ ≈ v^{n+1} − v^{n}, ∥ v^{n+1} − v^{n} ∥ and span(v^{n+1} − v^{n}) do not provide a valid stopping criterion. If ϕ is constant, no stopping criteria are available. Therefore, another approach is necessary. Schweitzer ^{\underline{schw84}} [211] employs a hierarchical decomposition of the MDP into a set of communicating MDPs. This decomposition was proposed by Bather ^{\underline{bath73b}} [11]. Schweitzer and Federgruen ^{\underline{schw78b}} [217] have shown that this decomposition is unique.

Open problem Formulate a value iteration algorithm (without a hierarchical decomposition of the MDP and without chain analysis) for multichain undiscounted MDPs.

Fundamental research of value iteration for undiscounted multichain MDPs was made by Schweitzer and Federgruen. In Schweitzer and Federgruen ^{\underline{schw79}} [218] it is shown, without any assumptions about the periodicity or the chain structure, that if the sequence {v^{n} −n·ϕ}_{n=0}^{∞} is convergent, the convergence rate is geometric. This is surprising because the operator of the mapping (4.16) is, in general, no contraction or a J-step contraction with respect to any norm or the seminorm span. Conditions, other than aperiodicity, for the convergence of \{v^{n} − n · ϕ\}_{n=0}^{∞} are given by Schweitzer ^{\underline{schw68}} [208], Denardo ^{\underline{den73}} [49] and Bather ^{\underline{bath73a}} [10]. Surveys on value iteration for undiscounted multichain MDPs can be found in Schweitzer and Federgruen ^{\underline{schw77}} [215] and in Federgruen and Schweitzer ^{\underline{fed78}} [70] and ^{\underline{fed80}} [71].

The unichain case

In this section we assume that the value vector is constant, i.e. ϕ = ϕ_{0} · e, where ϕ_{0} ∈ ℝ. This assumption is more general than the unichain assumption. Furthermore, we assume aperiodicity, which implies (cf. lemma 48) that ϕ = lim_{n→∞}(v^{n+1} − v^{n}). We will formulate an algorithm to compute an ϵ-optimal policy.

Theorem 49 Let l_{n} = min_{i}(v_{i}^{n} − v_{i}^{n−1}) and u_{n} = max_{i}(v_{i}^{n} − v_{i}^{n−1}), n ∈ ℕ. Then, (i) l_{n} ↑ ϕ_{0} and u_{n} ↓ ϕ_{0}; (ii) l_{n} · e ≤ ϕ(f_{n−1}^{∞}) ≤ ϕ_{0} · e ≤ u_{n} · e, n ≥ 1.

Proof. (i) Since ϕ = lim_{n→∞}(v^{n+1} −v^{n}), it is sufficient to show that l_{n+1} ≥ l_{n} and u_{n+1} ≤ u_{n}. We have, v^{n+1} − v^{n} ≥ [r(f_{n−1}) + P (f_{n−1})v^{n}] − [r(f_{n−1}) + P (f_{n−1})v^{n−1}] = P (f_{n−1})(v^{n} − v^{n−1}) ≥ P (f_{n−1}) · min_{i}(v^{n} − v^{n−1})_{i} · e = l_{n} · e, i.e. l_{n+1} ≥ l_{n}. Similarly, it can be shown that u_{n+1} ≤ u_{n}. (ii) From part (i), we have u_{n} ≥ ϕ_{0}, n ≥ 1. Furthermore, we can write ϕ(f_{n−1}^{∞}) = P^{∗}(f_{n−1})r(f_{n−1}) = P^{∗}(f_{n−1})[v^{n}−P (f_{n−1})v^{n−1}] = P^{∗}(f_{n−1})[v^{n}− v^{n−1}] ≥ P^{∗}(f_{n−1}) · min_{i}(v^{n} − v^{n−1})_{i} · e = l_{n} · e.

By the results of theorem 49 an algorithm can be formulated. Since v^{n} grows linearly in n, a direct application of (4.15) may cause numerical difficulties. Therefore, we use the following transformation. Let w_{i}^{n} = v_{i}^{n} − v_{N}^{n}, i ∈ E, n ≥ 0; g^{n} = v_{N}^{n} − v_{N}^{n−1}, n ≥ 1. Then, we have w_{i}^{n} = [e_{i}^{n} + nϕ + u_{i}] − [e_{N}^{n} + nϕ + u_{N}] = [e_{i}^{n} − e_{N}^{n}] + [u_{i} − u_{N}], which is a bounded sequence, and g^{n} = [e_{N}^{n} +nϕ+u_{N}]−[e_{N}^{n−1} +(n−1)ϕ+u_{N}] = [e_{N}^{n} − e_{N}^{n−1}]+ϕ, which is also bounded. Furthermore, the relations become g^{n+1} = v_{N}^{n+1} − v_{N}^{n} = max_{a∈A(N)}{r_{N}(a) + Σ_{j}p_{Nj}(a)[v_{j}^{n} − v_{N}^{n}]} = max_{a∈A(N)}{r_{N}(a) + Σ_{j}p_{Nj}(a)w_{j}^{n}}, and w_{i}^{n+1} = v_{i}^{n+1} − v_{N}^{n+1} = max_{a∈A(i)}{r_{i}(a) + Σ_{j}p_{ij}(a) · [v_{j}^{n} − v_{N}^{n}]} + [v_{N}^{n} − v_{N}^{n+1}] = max_{a∈A(i)}{r_{i}(a) + Σ_{j}p_{ij}(a)w_{j}^{n}} − g^{n+1}, i ∈ E. For the bounds l_{n} and u_{n}, we have l_{n} = min_{i}(v_{i}^{n} − v_{i}^{n−1}) = min_{i}(w_{i}^{n} − w_{i}^{n−1}) + g^{n} and u_{n} = max_{i}(v_{i}^{n} − v_{i}^{n−1}) = max_{i}(w_{i}^{n} − w_{i}^{n−1}) + g^{n}.

Algorithm X (relative value iteration; average rewards; aperiodic; constant value vector)

1. Choose ϵ > 0, and take v ∈ ℝ^{N} arbitrarily.

2. Compute:

a. s_{ia} = r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}, (i, a) ∈ E × xA; b. g = max_{a∈A(N)} s_{Na};

c. w_{i} = max_{a∈A(i)} s_{ia} − g, i ∈ E and take f such that w = r(f) + P (f)v − g;

d. u = max_{i}(w_{i} − v_{i}); l = min_{i}(w_{i} − v_{i});

3. If u−l ≤ ϵ: f^{∞} is an ϵ-optimal policy and (u+l)/2 is a \frac{1}{2}ϵ-approxiation of the value ϕ_{0} (STOP);

Otherwise: v = w and go to step 2.

One may ask whether exclusion of suboptimal actions can be implemented for the average reward criterion. Similar to formula (3.7) of the discounted rewards, it can be shown that an action a ∈ A(i) is suboptimal if

ϕ + u_{i} > r_{i}(a) + Σ_{j}p_{ij}(a)u_{j},  (4.18)

where (ϕ, u) is a solution of the optimality equation of theorem 35. Since such a solution is unknown in advance, in order to apply (4.17) in an algorithm, we need bounds for ϕ and u. Theorem 49 provides bounds for ϕ; however, bounds for u are unknown. One may well apply a suboptimality test in one iteration of formula (4.16). In fact, v^{n} is the total reward over a horizon of n stages. Hence, suboptimality tests for finite horizon models can be used (see Hastings ^{\underline{hast68}} [93], Hastings and Van Nunen ^{\underline{hast77}} [99], and Hübner ^{\underline{hub77}} [125]).

Bounds on the value vector as formulated in theorem 49 can be found in Hastings ^{\underline{hast71}} [95], Odoni ^{\underline{od}} [173], Hordijk and Tijms ^{\underline{hortym74}} [119], and Platzman ^{\underline{pla}} [178]. Hordijk and Tijms ^{\underline{hortym75}} [121] have proposed an approximation method with a sequence of discounted value iterations with discount factors tending to 1. Algorithm X is established by White ^{\underline{white63}} [278]. Recently, a new value iteration algorithm was proposed by Bertsekas ^{\underline{bertse98}} [21], under the assumption that all policies are unichain and that there exists a state that is recurrent under all policies. This method is inspired by a relation with an associated stochastic shortest path problem.

1.4.6 Modified policy iteration

As in the discounted reward case, modified policy iteration can be applied. However, we assume in this section the strong aperiodicity assumption, i.e. for some 0 < λ < 1, p_{ii}(a) ≥ λ > 0 for all i ∈ E, a ∈ A(i). As shown in section 4.5 by Schweitzer’s aperiodicity transformation, any MDP can be transformed to an equivalent MDP with the strong aperiodicity property.

Furthermore, we assume that the value vector ϕ is a constant vector: ϕ = ϕ_{0} · e.

Let U and L_{f} be the operators as defined in (3.2) and (3.5), repectively, with α = 1.

Lemma 50 Let l_{n} = min_{i}(Ux^{n} − x^{n})_{i}, n ∈ ℕ. Then, the sequence {l_{n}}_{n=1}^{∞} is monotonically nondecreasing. Proof. Ux^{n} − x^{n} ≥ L_{f_{n−1}}x^{n} − x^{n} = L_{f_{n−1}}^{k+1}x^{n−1} − L_{f_{n−1}}^{k}x^{n−1} = P^{k}(f_{n−1}) [L_{f_{n−1}}x^{n−1} − x^{n−1}] = P^{k}(f_{n−1})[Ux^{n−1} − x^{n−1}] ≥ P^{k}(f_{n−1})l_{n−1} · e = l_{n−1} · e. Hence, l_{n} ≥ l_{n−1}.

Remark Let u_{n} = max_{i}(Ux^{n} − x^{n})_{i}, n ∈ ℕ. Then the sequence {u_{n} | n ∈ ℕ} is in general not monotonically nonincreasing, unless k = 1 (for k = 1, see theorem 49).

Without proof we present the following result.

Theorem 51 (i) The sequences {l_{n} | n ∈ ℕ} and {u_{n} | n ∈ ℕ} both converge to the value ϕ_{0}; (ii) the convergence of span(Ux^{n} − x^{n}) to zero is geometrically fast; (iii) algorithm XI (see below) terminates with an ϵoptimal policy f_{n} and \frac{1}{2}[u_{n} + l_{n}] is an \frac{1}{2}ϵ-approximation of ϕ_{0}.

Algorithm XI (modified policy iteration; average rewards; aperiodic; constant value vector)

1. Choose x ∈ ℝ^{N} and ϵ > 0 arbitrarily.

2. a. Choose k with 1 ≤ k ≤ ∞;

b. Determine f such that L_{f}x = Ux;

c. Let l = min_{i}(Ux − x)_{i} and u = max_{i}(Ux − x)_{i}.

3. If u−l ≤ ϵ: f^{∞} is an ϵ-optimal policy and (u+l)/2 is a \frac{1}{2}ϵ-approxiation of the value ϕ_{0} (STOP);

otherwise: x = L_{f}^{k}x and go to step 2.

Remark If k = 1 the method becomes the standard value iteration (without White’s relative values). We will also make it plausible that, in the unichain case, policy iteration corresponds to k = ∞. By theorem 28, we have ϕ(f^{∞}) + [I − P (f)]u(f) = r(f), L_{f_{n}}^{k}x^{n} = L_{f_{n}}^{k}[u(f_{n})] + P^{k}(f_{n})[x^{n} − u(f_{n})] = u(f_{n}) + k · ϕ(f_{n}^{∞}) + P^{k}(f_{n})[x^{n} − u(f_{n+1})]. If k tends to infinity, P^{k}(f_{n}) converges to P^{∗}(f_{n}), a matrix with equal rows, i.e. P^{k}(f_{n})[x^{n} − u(f_{n})] converges to a constant vector. Since, ϕ(f_{n}^{∞}) is also a constant vector, the difference between L_{f_{n}}^{k}x^{n} and u(f_{n}) converges to a constant vector. In the policy iteration algorithm VII with best improving actions, a new policy corresponds to maximization of r_{i}(a) + Σ_{j}p_{ij}(a)u_{j}(f_{n}), which is the same as U[L_{f_{n}}^{k}x^{n}]. Hence, both methods are very similar.

The modified policy iteration method was first mentioned by Morton ^{\underline{mor}} [170]. Vander Wal ^{\underline{wal80}} [246] and ^{\underline{wal81}} [247] has analysed this method extensively under various chain structure assumptions (irreducible case, unichain case, communicating case and simply connected case).

1.5 MORE SENSITIVE OPTIMALITY CRITE-RIA

1.5.1 Introduction

In section 1.3 the concepts of an n-discount optimal and an n-average optimal policy R_{∗}, for n = −1, 0, 1, …, are introduced, respectively by

lim_{α↑1}(1 − α)^{−n}[v^{α}(R_{∗}) − v^{α}] = 0  (5.1)

and

lim inf_{T →∞} \frac{1}{T} [v^{n,T} (R_{∗}) − v^{n,T} (R)] ≥ 0 for every policy R,  (5.2)

where

v^{n,t}(R) = \{ \begin{matrix}v^{t}(R) & for n = −1 \\ Σ_{s=1}^{t}v^{n−1,s}(R) & for n = 0, 1, … \end{matrix}

Without proof we state that for both criteria optimal deterministic policies exist.

Theorem 52 The criteria (-1)-discount optimal and (-1)-average optimal are equivalent, and also equivalent to average optimal. Proof. From corollary 31 it follows that lim_{α↑1}(1 − α)v^{α}(f^{∞}) = ϕ(f^{∞}) for every deterministic policy. Hence, using a Blackwell optimal policy, we obtain lim_{α↑1}(1 − α)v^{α} = ϕ. Therefore, if f_{∗}^{∞} is (-1)-discount optimal, then we have 0 = lim_{α↑1}(1 − α)[v^{α}(f_{∗}^{∞}) − v^{α}] = ϕ(f_{∗}^{∞}) − ϕ, i.e. f_{∗}^{∞} is average optimal. (-1)-average optimality means that lim_{T →∞} \frac{1}{T} [v^{T} (f_{∗}) − v^{T} (f)] ≥ 0, i.e. lim_{T →∞} \frac{1}{T} [Σ_{t=1}^{T}P^{t−1}(f_{∗})r(f_{∗}) − Σ_{t=1}^{T}P^{t−1}(f)r(f)] ≥ 0 for every policy f^{∞}. Since lim_{T →∞} \frac{1}{T} Σ_{t=1}^{T}P^{t−1}(f)r(f) = ϕ(f^{∞}) for every policy f^{∞}, an average optimal policy is also (-1)-average optimal. Finally, let f_{∗}^{∞} be (-1)-average optimal and let f_{0}^{∞} be a Blackwell optimal policy. Then, by the Laurent expansion, 0 ≥ lim_{α↑1}(1−α)[v^{α}(f_{∗}^{∞})−v^{α}] = lim_{α↑1}(1−α)[v^{α}(f_{∗}^{∞})−v^{α}(f_{0}^{∞})] = ϕ(f_{∗}^{∞}) − ϕ(f_{0}^{∞}) = lim_{T →∞} \frac{1}{T} [Σ_{t=1}^{T}P^{t−1}(f_{∗})r(f_{∗}) − Σ_{t=1}^{T}P^{t−1}(f_{0})r(f_{0})] ≥ 0, i.e. f_{∗}^{∞} (-1)-discount optimal.

Theorem 53 The criteria 0-discount optimal and 0-average optimal are equivalent (such policy is called a bias optimal policy). Proof. Suppose that f_{∗}^{∞} is a 0-optimal policy, and let f_{0}^{∞} be Blackwell optimal. Using the properties of the stationary and the deviation matrix, it can be shown that Σ_{s=1}^{t}P^{s−1}(f)r(f) = tϕ(f^{∞}) + u^{0}(f) − P^{t}(f)D(f)r(f). Therefore, 0 ≤ lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}Σ_{s=1}^{t}\{P^{s−1}(f_{∗})r(f_{∗}) − P^{s−1}(f_{0})r(f_{0})\} = lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}\{[tϕ(f_{∗}^{∞})+u^{0}(f_{∗})−P^{t}(f_{∗})D(f_{∗})r(f_{∗})]−[tϕ(f_{0}^{∞})+u^{0}(f_{0})− P^{t}(f_{0})D(f_{0})r(f_{0})]\} = lim inf_{T →∞}[\frac{1}{2}(T +1)\{ϕ(f_{∗}^{∞})−ϕ\}+\{u^{0}(f_{∗})−u^{0}(f_{0})\}− \frac{1}{T} Σ_{t=1}^{T}\{P^{t}(f_{∗})D(f_{∗})r(f_{∗}) − P^{t}(f_{0})D(f_{0})r(f_{0})\}]. Since lim_{T →∞} \frac{1}{T} Σ_{t=1}^{T}P^{t}(f) D(f) = P^{∗}(f)D(f) = 0 and ϕ(f_{∗}^{∞}) − ϕ ≤ 0, we have ϕ(f_{∗}^{∞}) = ϕ = ϕ(f_{0}^{∞}) and u^{0}(f_{∗}) − u^{0}(f_{0}) ≥ 0. Hence, we obtain, by the Laurent expansion, 0 ≥ lim_{α↑1}[v^{α}(f_{∗}^{∞}) − v^{α}] = lim_{α↑1}[v^{α}(f_{∗}^{∞}) − v^{α}(f_{0}^{∞})] = lim_{α↑1}{(1 − α)^{−1}[ϕ(f_{∗}^{∞}) − ϕ(f_{0}^{∞})] + [u^{0}(f_{∗}) − u^{0}(f_{0})]} = u^{0}(f_{∗}) − u^{0}(f_{0}) ≥ 0. On the other hand, suppose that lim_{α↑1}[v^{α} (f_{∗}^{∞}) − v^{α}] = 0. For any f^{∞}, also by the Laurent expansion, ϕ(f_{∗}^{∞}) ≥ ϕ(f^{∞}) and if ϕ_{i}(f_{∗}^{∞}) = ϕ_{i}(f^{∞}), then u_{i}^{0}(f_{∗}) ≥ u_{i}^{0}(f). Hence, we obtain lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}Σ_{s=1}^{t}\{P^{s−1}(f_{∗})r(f_{∗}) − P^{s−1}(f)r(f)\} = lim inf_{T →∞}[\frac{1}{2}(T + 1)\{ϕ(f_{∗}^{∞}) − ϕ(f^{∞})\} + \{u^{0}(f_{∗}) − u^{0}(f)\} + \frac{1}{T} Σ_{t=1}^{T}\{P^{t}(f_{∗})D(f_{∗})r(f_{∗}) − P^{t}(f_{0}) D(f_{0})r(f_{0})}] ≥ 0.

In Blackwell ^{\underline{bl62}} [27] the concept of bias optimality was introduced. Veinott^{\underline{vei66b}} [257] presented a policy iteration algorithm for finding a bias optimal policy. In Veinott ^{\underline{vei66b}} [257] is also shown that an average overtaking deterministic optimal policy is bias optimal, and conjectured that the reverse statement is also true. A policy R_{∗} is average overtaking optimal if lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T}[v^{t}(R_{∗})− v^{t}(R)] ≥ 0 for every policy R. The conjecture was proved by Denardo and Miller ^{\underline{denmil68}} [52]. Lippman ^{\underline{lipp}} [155] showed the equivalence for general (possibly nonstationary) policies. Other contributions to the computation of a bias optimal policy are Denardo ^{\underline{den70}} [47] and ^{\underline{den73}} [49], Fox ^{\underline{fox}} [80] and Kallenberg ^{\underline{kal81c}} [134]. We refer also to Rieder’s chapter in this book on bias optimality. Denardo and Rothblum ^{\underline{den79b}} [54] have studied the stronger criterion of overtaking optimality. A policy R_{∗} is overtaking optimal if lim inf_{T →∞} Σ_{t=1}^{T}[v^{t}(R_{∗})−v^{t}(R)] ≥ 0 for every policy R. This criterion may have no optimal policy, as already was shown in Brown ^{\underline{brown}} [29]. Denardo and Rothblum ^{\underline{den79b}} [54] provided conditions under which a stationary overtaking optimal policy exists. The n-discount optimality criterion was proposed in Veinott ^{\underline{vei69}} [258]. Sladky ^{\underline{sla}} [224] has introduced the concept of n-average optimality; furthermore, he showed the equivalence between this criterion and the n-discount optimality.

1.5.2 Lexicographic ordering of Laurent series

Instead of the discount factor α we can also use the interest rate ρ, where the relations between α and ρ are given by ρ = (1 − α)/α. From theorem 30 it follows that the total discounted reward v^{α}(f^{∞}) can be written as the Laurent series v^{ρ}(f^{∞}) = (1 + ρ)Σ_{k=−1}^{∞}ρ^{k}u^{k}(f) for 0 < ρ <∥ D(f) ∥^{−1}. Let

H^{ρ}(f) = (1 + ρ){P^{∗}(f) + Σ_{k=0}^{∞}(−1)^{k}ρ^{k+1}D^{k+1}(f)} for 0 < ρ <∥ D(f) ∥^{−1} .

(5.3)

Theorem 54 (i) H^{ρ}(f) = ρ[I−(1+ρ)^{−1}P (f)]^{−1}; (ii) H^{ρ}(f)r(f) = ρv^{ρ}(f^{∞}); (iii) ρ[v^{ρ}(f^{∞}) − x] = H^{ρ}(f)[r(f) + (1 + ρ)^{−1}P (f)x − x]. Proof. The proof is based on the properties of the stationary and deviation matrix as stated in theorem 28.

Define the sets LS_{1} and LS_{2} of Laurent series by

\begin{aligned}LS_{1} = \{u(ρ)|u(ρ) = Σ_{k=−1}^{∞}ρ^{k}u^{k}; & u^{k} ∈ ℝ^{N}, k ≥ −1; \\ & lim sup_{k→∞} ∥ u^{k} ∥^{1/k}< ∞\} \end{aligned}  (5.4)

and

LS_{2} = \{x(ρ) | \begin{matrix}x(ρ) = (1 + ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k}; x^{k} ∈ ℝ^{N}, k ≥ 1 \\ lim sup_{k→∞} ∥ x^{k} ∥^{1/k}< ∞ \end{matrix} \} (5.5)

Lemma 55 LS_{1} = LS_{2}. Proof. The proof can be given by showing that any u(ρ) ∈ LS_{1} satisfies u(ρ) = Σ_{k=−1}^{∞}ρ^{k}u^{k} = (1 + ρ)[Σ_{j=0}^{∞}(−ρ)^{j}]Σ_{k=−1}^{∞}ρ^{k}u^{k} = (1 + ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k}, where x^{k} = Σ_{j=−1}^{k}(−1)^{k−j}u^{j}. Hence, u(ρ) is also an element of LS_{2}. Similarly, the reverse statement can be shown.

Corollary 56. The sets LS_{1} and LS_{2} are the same, and will be denoted by LS.

Notice that LS is a linear vector space. We define a lexicographic ordering on LS by: u(ρ) is nonnegative (positive) if the first nonzero vector of (u^{−1}, u^{0}, …) is nonnegative (positive), i.e.

\{ \begin{matrix}u(ρ) ≥_{ℓ} 0 & if lim inf_{ρ↓0} ρ^{−k}u(ρ) ≥ 0 for k = −1, 0, 1, … \\ u(ρ) >_{ℓ} 0 & if u(ρ) ≥_{ℓ} 0 and u(ρ) ≠ 0. \end{matrix}  (5.6)

Let L_{f}^{ρ} : LS → LS be defined by

L_{f}^{ρ}x(ρ) = r(f) + (1 + ρ)^{−1}P (f)x(ρ).  (5.7)

The Laurent expansion of L_{f}^{ρ}x(ρ)−x(ρ) for x(ρ) = (1+ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k} satisfies L_{f}^{ρ}x(ρ)−x(ρ) = r(f)+(1+ρ)^{−1}P (f)(1+ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k} −(1+ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k} = r(f) + Σ_{k=−1}^{∞}ρ^{k}P (f)x^{k} − Σ_{k=−1}^{∞}ρ^{k}x^{k} − Σ_{k=0}^{∞}ρ^{k}x^{k−1} = ρ^{−1}[P (f)x^{−1} − x^{−1}] + [r(f) + P (f)x^{0} − x^{0} − x^{−1}] + Σ_{k=1}^{∞}ρ^{k}[P (f)x^{k} − x^{k} − x^{k−1}], which implies L_{f}^{ρ}x(ρ) ∈ LS. From theorem 11, we obtain

L_{f}^{ρ}v^{ρ}(f^{∞}) − v^{ρ}(f^{∞}) = 0.  (5.8)

For x ∈ ℝ^{N}, let y = max_{E×A}[r+P x], i.e. y_{i} = max_{a∈A(i)}[r_{i}(a)+Σ_{j}p_{ij}(a)x_{j}], i ∈ E, and argmax_{E×A}[r + P x] = {f| max_{E×A}[r + P x] = r(f) + P (f)x}.

Consider the mapping B : LS → LS where, for x(ρ) = (1 + ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k}, Bx(ρ) is given by

Bx(ρ) = Σ_{k=−1}^{∞}ρ^{k}B^{(k)}(x^{−1}, x^{0}, …, x^{k})  (5.9a)

with

\{ \begin{matrix}B^{(−1)}(x^{−1}) & = max_{E×A}[P x^{−1} − x^{−1}] \\ A^{(−1)}(x^{−1}) & = argmax_{E×A}[P x^{−1} − x^{−1}] \end{matrix}  (5.9b)

\{ \begin{matrix}B^{(0)}(x^{−1}, x^{0}) & = max_{E×A^{−1}(x^{−1})}[r + P x^{0} − x^{0} − x^{−1}] \\ A^{(0)}(x^{−1}, x^{0}) & = argmax_{E×A^{−1}(x^{−1})}[r + P x^{0} − x^{0} − x^{−1}] \end{matrix}  (5.9c)

and for k ≥ 1 we define B^{(k)}(x^{−1}, x^{0}, …, x^{k}) and A^{(k)}(x^{−1}, x^{0}, …, x^{k}) by

\{ \begin{matrix}B^{(k)}(x^{−1}, x^{0}, …, k) & = max_{E×A^{k−1}(x^{−1},x^{0},... ,x^{k})}[P x^{k} − x^{k} − x^{k−1}] \\ A^{(k)}(x^{−1}, x^{0}, …, k) & = argmax_{E×A^{k−1}(x^{−1},x^{0},... ,k)}[P x^{k} − x^{k} − x^{k−1}] \end{matrix} (5.9d)

Because ρ^{−1}[P (f)x^{−1} − x^{−1}] + [r(f) + P (f)x^{0} − x^{0} − x^{−1}] + Σ_{k=1}^{∞}ρ^{k}[P (f)x^{k} − x^{k} − x^{k−1}] = r(f)+Σ_{k=−1}^{∞}ρ^{k}P (f)x^{k}−(1+ρ)Σ_{k=−1}^{∞}ρ^{k}x^{k} = r(f)+(1+ρ)^{−1}P (f)x(ρ)− x(ρ) = L_{f}^{ρ}x(ρ) − x(ρ), Bx(ρ) ∈ LS, which is the result of lexicographically maximizing r(f) + (1 + ρ)^{−1}P (f)x(ρ) − x(ρ), i.e. Bx(ρ) = lexmax_{f}[r(f) + (1 + ρ)^{−1}P (f)x(ρ) − x(ρ)] = lexmax_{f}[L_{f}^{ρ}x(ρ) − x(ρ)] Since L_{g}^{ρ}[v^{ρ}(g^{∞})] − v^{ρ}(g^{∞}) = 0, we have for every g^{∞}

Bv^{ρ}(g^{∞}) = lexmax_{f}[L_{f}^{ρ}v^{ρ}(g^{∞})−v^{ρ}(g^{∞})] ≥_{ℓ} L_{g}^{ρ}v^{ρ}(g^{∞})−v^{ρ}(g^{∞}) = 0. (5.10)

H^{ρ}(f) is a positive operator if \begin{cases}H^{ρ}(f)[u(ρ)] ≥_{ℓ} 0 & when u(ρ)_{ℓ} ≥ 0 \\ H^{ρ}(f)[u(ρ)] >_{ℓ} 0 & when u(ρ)_{ℓ} > 0 \end{cases} (5.11)

Then, the following results can be proven.

Theorem 57 (i) H^{ρ}(g)[r(g)+(1+ρ)^{−1}P (g)v^{ρ}(f^{∞})−v^{ρ}(f^{∞})] = ρ[v^{ρ}(g^{∞})− v^{ρ}(f^{∞})]; (ii) H^{ρ}(f) is a positive operator.

Theorem 58 (i) Bx = 0 has in LS a unique solution x = v^{ρ}(f_{0}^{∞}), where f_{0}^{∞} is Blackwell optimal; (ii) If g satisfies Bx = r(g) + (1 + ρ)^{−1}P (g)x − x = 0, then g^{∞} is a Blackwell optimal policy.

The representation of the expected discounted rewards as a Laurent series is provided by Miller and Veinott ^{\underline{mil}} [167]. They also introduced the lexicographic ordering. The approach of the mapping B on the set LS is developed by Hordijk and Dekker ^{\underline{hor88}} [113].

1.5.3 n-Discount optimality and policy iteration

In this section we derive a policy iteration algorithm to compute a policy that lexicographically maximizes the vector (u^{−1}(f), u^{0}(f), …, u^{n}(f)) over all deterministic policies, i.e. an n-discount optimal policy, for n = −1, 0, 1, . . .. For n = −1 an average optimal policy and for n = 0 a bias optimal policy is obtained. Furthermore, we will show that for all n ≥ N − 1 an n-discount optimal policy is a Blackwell optimal policy. The algorithm is as follows.

Algorithm XII (policy iteration; n-discount optimality)

1. Take an arbitrary policy f^{∞}.

2. Determine (u^{−1}(f), u^{0}(f), …, u^{n+1}(f)) as unique solution of the linear system

\{ \begin{matrix}[I − P (f)]x^{−1} & = 0 \\ x^{−1} + [I − P (f)]x^{0} & = r(f) \\ x^{k−1} + [I − P (f)]x^{k} & = 0 1 ≤ k ≤ n + 1; P^{∗}(f)x^{n+1} = 0 \end{matrix} \}

3.

a If max_{E×A}[P u^{−1}(f)−u^{−1}(f)] > 0, then A^{(−1)} = argmax_{E×A}[P u^{−1}(f)− u^{−1}(f)], choose g from A^{(−1)} and go to step 5. b If max_{E×A^{(−1)}}[r + P u^{0}(f) − u^{0}(f) − u^{−1}(f)] > 0, then

A^{(0)} = argmax_{E×A^{(−1)}}[r + P u^{0}(f) − u^{0}(f) − u^{−1}(f)], choose g from A^{(0)} and go to step 5.

c For k = 0 until n do:

If max_{E×A^{(k)}}[P u^{k+1}(f) − u^{k+1}(f) − u^{k}(f)] > 0, then

A^{(k+1)} = argmax_{E×A^{(k)}}[P u^{k+1}(f) − u^{k+1}(f) − u^{k}(f)], choose g from A^{(k+1)} and go to step 5.

4. f^{∞} is n-discount optimal (STOP);

5. f(i) = g(i), i ∈ E, and go to step 2.

Theorem 59 The linear system

\{ \begin{matrix}[I − P (f)]x^{−1} & = 0 \\ x^{−1} + [I − P (f)] & = r(f) \\ x^{k−1} + [I − P (f)]x^{k} & = 0 1 ≤ k ≤ n + 1; P^{∗}(f)x^{n+1} = 0 \end{matrix} \}

has the unique solution (u^{−1}(f), u^{0}(f), …, u^{n+1}(f)). Proof. Suppose that (x^{−1}, x^{0}, …, x^{n+1}) is a solution. Then, x^{−1} = P (f)x^{−1} implies that x^{−1} = P^{∗}(f)x^{−1}. From x^{0} + [I − P (f)]x^{1} = 0 we obtain P^{∗}(f)x^{0} = 0. Hence, x^{−1} = P^{∗}(f)x^{−1} = P^{∗}(f){r(f) − [I − P (f)]x^{0}} = P^{∗}(f)r(f) = u^{−1}(f) and r(f) = x^{−1}+[I−P (f)]x^{0} = P^{∗}(f)r(f)+[I−P (f)+P^{∗}(f)]x^{0}, i.e. x^{0} = [I −P (f)+P^{∗}(f)]^{−1}[I −P^{∗}(f)]r(f) = [D(f)+P^{∗}(f)][I −P^{∗}(f)]r(f) = u^{0}(f). By induction on k, we obtain x^{k−1} = u^{k−1}(f), P^{∗}(f)x^{k} = 0 and 0 = x^{k−1}+[I −P (f)]x^{k} = u^{k−1}(f)+[I −P (f)+P^{∗}(f)]x^{k} = (−1)^{k−1}D^{k}(f)r(f)+ [I − P (f) + P^{∗}(f)]x^{k} i.e. x^{k} = [D(f) + P^{∗}(f)](−1)^{k}D^{k}(f)r(f) = (−1)^{k}D^{k+1}(f)r(f) = u^{k}(f), k ≥ 1.

Remarks

1. Instead of P^{∗}(f)x^{n+1} = 0, we can also consider x^{n+1}+[I −P (f)]x^{n+2} = 0, since multiplication with P^{∗}(f) gives P^{∗}(f)x^{n+1} = 0.

2. For n = −1 the algorithm is equivalent to algorithm VI.

In order to show that algorithm XII determines an n-discount optimal policy, we use the following notation and lemma (which is stated without proof).

\{ \begin{matrix}ψ^{−1}(f, g) & = P (g)u^{−1}(f) − u^{−1}(f) \\ ψ^{0}(f, g) & = r(g) + P (g)u^{0}(f) − u^{0}(f) − u^{−1}(f) \\ ψ^{k}(f, g) & = P (g)u^{k}(f) − u^{k}(f) − u^{k−1}(f), k ≥ 1 \end{matrix}  (5.12)

Lemma 60 For every f^{∞}, g^{∞} and every m ∈ ℕ, we have αv^{α}(g^{∞}) = Σ_{k=−1}^{m−1}ρ^{k}{u^{k}(f) + Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)} + ρ^{m}Σ_{t=1}^{∞}α^{t}P^{t−1}(g)u^{m−1}(f).

Theorem 61 Let f^{∞} and g^{∞} be subsequent policies in algorithm XII, then v^{ρ}(g^{∞}) > v^{ρ}(f^{∞}) for ρ sufficiently small. Proof. From theorem 59 it follows that ψ^{k}(f, f) = 0 for k = −1, 0, . . .. Hence, by lemma 60 with n = m + 2, v^{ρ}(g^{∞}) − v^{ρ}(f^{∞}) = (1 + ρ){Σ_{k=−1}^{n+1}ρ^{k} [Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)] + ρ^{n+2}Σ_{t=1}^{∞}α^{t}[P^{t−1}(f) − P^{t−1}(g)]u^{n+1}(f)}. Since ∥ ρ^{n+2}Σ_{t=1}^{∞}α^{t}[P^{t−1}(f) − P^{t−1}(g)]u^{n+1}(f) ∥≤ ρ^{n+2}(1 − α)^{−1} ∥ P^{t−1}(f) − P^{t−1}(g) ∥ · ∥ u^{n+1}(f) ∥≤ 2ρ^{n+1}(1 + ρ) ∥ u^{n+1}(f) ∥, lim_{ρ↓0}(1 + ρ)ρ^{n+2} Σ_{t=1}^{∞}α^{t}[P^{t−1}(f) − P^{t−1}(g)]u^{n+1}(f) = 0 for n ≥ 0. On the other hand, since f^{∞} and g^{∞} are subsequent policies, ψ^{k}(f, g) = 0, −1 ≤ k ≤ m − 1 and ψ^{m}(f, g) > 0 for some −1 ≤ m ≤ n + 1. Hence, if we define ψ^{k}(f, g) = 0 for k ≥ n+2, we have Σ_{k=−1}^{∞}ρ^{k}ψ^{k}(f, g) ∈ LS and Σ_{k=−1}^{∞}ρ^{k}ψ^{k}(f, g) >_{ℓ} 0. Since, by theorem 57 (ii), H^{ρ}(g) = ρ[I−(1+ρ)^{−1}P (g)]^{−1} is a positive operator, [I− (1+ρ)^{−1}P (g)]^{−1} is also positive, i.e. [I−(1+ρ)^{−1}P (g)]^{−1}[Σ_{k=−1}^{∞}ρ^{k}ψ^{k}(f, g)] >_{ℓ} 0. Since [I−(1+ρ)^{−1}P (g)]^{−1}[Σ_{k=−1}^{∞}ρ^{k}ψ^{k}(f, g)] = Σ_{t=1}^{∞}α^{t−1}P^{t−1}(g)[Σ_{k=−1}^{∞}ρ^{k} ψ^{k}(f, g)] = Σ_{t=1}^{∞}α^{t−1}P^{t−1}(g)Σ_{k=−1}^{n+1}ρ^{k}ψ^{k}(f, g) = α^{−1}{Σ_{k=−1}^{n+1}ρ^{k}[Σ_{t=1}^{∞}α^{t} P^{t−1}(g)ψ^{k}(f, g)]} = (1 + ρ){Σ_{k=−1}^{n+1}ρ^{k}[Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)]}, it follows that v^{ρ}(g^{∞}) − v^{ρ}(f^{∞}) = (1 + ρ){Σ_{k=−1}^{n+1}ρ^{k}[Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)]} + (1 + ρ)ρ^{n+2}Σ_{t=1}^{∞}α^{t} · [P^{t−1}(f) − P^{t−1}(g)]u^{n+1}(f)} >_{ℓ} 0 : v^{ρ}(g^{∞}) > v^{ρ}(f^{∞}) for ρ sufficiently small.

Theorem 62 Algorithm XII terminates in a finite number of iterations with an n-discount optimal policy. Proof. From theorem 61 it follows that algorithm XII produces a sequence of different deterministic policies. Since the set of deterministic policies is finite, the algorithm terminates after a finite number of iterations. Let f^{∞} be the last policy. We obtain by applying lemma 60, v^{ρ}(g^{∞}) − v^{ρ}(f^{∞}) = (1 + ρ){Σ_{k=−1}^{n+1}ρ^{k}[Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)] + ρ^{n+2}Σ_{t=1}^{∞}α^{t}[P^{t−1}(f) − P^{t−1}(g)] u^{n+1}(f)}. Since the algorithm terminates, Σ_{k=−1}^{∞} ρ^{k}ψ^{k}(f, g) ≤_{ℓ} 0, where ψ^{k}(f, g) = 0 for k ≥ n+2. This implies that (1+ρ){Σ_{k=−1}^{n+1}ρ^{k}[Σ_{t=1}^{∞}α^{t}P^{t−1}(g) ψ^{k}(f, g)] ≤_{ℓ} 0 and ∥ ρ^{n+2}Σ_{t=1}^{∞}α^{t}[P^{t−1}(f) − P^{t−1}(g)]u^{n+1}(f) ∥≤ 2ρ^{n+1}(1 + ρ) ∥ u^{n+1}(f) ∥. Hence, lim_{ρ↓0} ρ^{−n}[v^{ρ}(f^{∞}) − v^{ρ}(g^{∞})] ≥ 0 for every policy g^{∞}, i.e. f^{∞} is an n-discount optimal policy.

Finally, we show that an n-discount optimal policy is a Blackwell optimal policy if n ≥ N − 1.

Lemma 63 If ψ^{k}(f, g) = 0 for 1 ≤ k ≤ N, then also ψ^{k}(f, g) = 0 for all k ≥ N + 1. Proof. Let L = {x ∈ ℝ^{N}|[P (f) − P (g)]x = 0}. Since, for k ≥ 1, ψ^{k}(f, g) = P (g)u^{k}(f) − u^{k}(f) − u^{k−1}(f) = P (g)u^{k}(f) − (−1)^{k}[D(f) − I]D^{k}(f)r(f) = P (g)u^{k}(f) − (−1)^{k}[P (f)D(f) − P^{∗}(f)]D^{k}(f)r(f) = P (g)u^{k}(f) − P (f)u^{k}(f) ,i.e. u^{k}(f) ∈ L for k = 1, 2, …, N. Since L is a linear vector space in ℝ^{N}, the N + 1 vectors u^{k}(f), 1 ≤ k ≤ N + 1, are linear dependent. Because u^{k}(f) = B^{k}x_{0} for x_{0} = u^{1}(f) and B = −D(f), the set {x_{0}, Bx_{0}, …, B^{N}x_{0}} is dependent, i.e. for some 1 ≤ k ≤ N, we have B^{k}x_{0} = Σ_{j=0}^{k−1}λ_{j}B^{j}x_{0} for some scalars λ_{j}, 1 ≤ j ≤ k − 1, i.e. B^{k}x_{0} ∈ L. Hence we have B^{k+1}x_{0} = Σ_{j=0}^{k−1}λ_{j}B^{j+1}x_{0}, which is a linear combination of the elements Bx_{0}, …, B^{k}x_{0} from L, so B^{k+1}x_{0} ∈ L. Similarly, by induction, it can be shown that u^{k}(f) = B^{k}x_{0} ∈ L for every k ≥ 1, implying that ψ^{k}(f, g) = 0 for k ≥ 1.

Theorem 64 If algorithm XII is used to determine an (N − 1)-discount optimal policy f^{∞} then f^{∞} is also a Blackwell optimal policy. Proof. If the algorithm terminates with f^{∞}, we have Σ_{k=−1}^{N} ρ^{k}ψ^{k}(f, g) ≤_{ℓ} 0 for every policy g^{∞}, i.e. either Σ_{k=−1}^{N}ρ^{k}ψ^{k}(f, g) <_{ℓ} 0 or Σ_{k=−1}^{N}ρ^{k}ψ^{k}(f, g) = 0. In the first case, v^{ρ}(g^{∞}) < v^{ρ}(f^{∞}) for ρ sufficiently small; in the second case ψ^{k}(f, g) = 0, 1 ≤ k ≤ N. From lemma 63 it follows that ψ^{k}(f, g) = 0, k ≥ 1. Then, by lemma 60 with m → ∞, αv^{α}(g^{∞}) = Σ_{k=−1}^{∞}ρ^{k}{u^{k}(f) + Σ_{t=1}^{∞}α^{t}P^{t−1}(g)ψ^{k}(f, g)} = Σ_{k=−1}^{∞}ρ^{k}u^{k}(f) = αv^{α}(f^{∞}) for all α ∈ [0, 1). Hence, f^{∞} is Blackwell optimal.

The policy iteration method of this section was proposed in Veinott ^{\underline{vei69}} [258] and in Miller and Veinott ^{\underline{mil}} [167]. They have also shown that Blackwell optimality is the same as n-discount optimality for n ≥ N − 1. In Veinott ^{\underline{vei74}} [259] refined results are given. In Federgruen and Schweitzer ^{\underline{fed84b}} [73] a value iteration method is suggested for solving nested functional equations. These equations arise e.g. when more sensitive discount optimal policies are found. In particular, a method is given to find the optimal bias vector and a bias-optimal policy.

1.5.4 Blackwell optimality and linear programming

In this section we show how linear programming in the space of the rational functions can be developed to compute optimal policies over the entire range of the discount factor. Especially, a procedure is presented for the computation of a Blackwell optimal policy.

Let ℝ be the ordered field of the real numbers with the usual ordering denoted by >. By P (ℝ) we denote the set of all polynomials with real coefficients:

P(ℝ) = {p(x)|p(x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n}, a_{i} ∈ ℝ, 1 ≤ i ≤ n}. (5.13)

By p_{0} and p_{1} we denote the polynomials p_{0}(x) = 0 and p_{1}(x) = 1 for every x. The field F (ℝ) of rational functions with real coefficients consists of the elements \frac{p(x)}{q(x)}, where p and q are from P (ℝ) and q ≠ p_{0}. The polynomial p(x) is

considered as identical to the rational function \frac{p(x)}{p_{1}(x)}. Two rational functions \frac{p}{q} and \frac{r}{s} are considered identical, denoted \frac{p}{q} =_{ℓ} \frac{r}{s}, if p(x)s(x) = q(x)r(x). The operations + and · are the natural addition and multiplication, i.e. \frac{p(x)}{q(x)} + \frac{r(x)}{s(x)} =_{ℓ} \frac{p(x)s(x)+r(x)q(x)}{q(x)s(x)} and \frac{p(x)}{q(x)} · \frac{r(x)}{s(x)} =_{ℓ} \frac{p(x)r(x)}{q(x)s(x)}. The polynomials p_{0} and p_{1} are the identities with respect to the operations addition and multiplication. A complete ordereing in F (ℝ) is obtained by \frac{p}{q} >_{ℓ} p_{0} if and only if d(p)d(q) > 0. If \frac{p}{q} >_{ℓ} p_{0}, then the rational function \frac{p}{q} is called positive. \frac{p}{q} ≥_{ℓ} p_{0} means that either p =_{ℓ} p_{0} or \frac{p}{q} >_{ℓ} p_{0}. F (ℝ) is a non-Archimedean ordered field. The continuity of polynomials implies that the rational function \frac{p}{q} is positive if and only if \frac{p(x)}{q(x)} > 0 for all x sufficiently close to 0. Hence, we obtain the following result.

Theorem 65 The rational function \frac{p}{q} is positive if and only if there exists

an x_{0} > 0 such that \frac{p(x)}{q(x)} > 0 for every x ∈ (0, x_{0}].

The total expected discounted reward v^{ρ}(f) for a deterministic policy f^{∞} is the unique solution of the linear system [(1 + ρ)I − P (f)]x = (1 + ρ)r(f). Solving this equation by Cramer’s rule shows that v_{i}^{ρ}(f^{∞}), i ∈ E, is an element of F (ℝ), say \frac{p}{q}, where the degree of the polynomials p and q is at most N. It is well known (theorem 29) that the interval [0,1) of the discount factor can be divided into a finite number of intervals, say [0 = α_{m}, α_{m−1}), …, [α_{0}, α_{−1} = 1), in such a way that there exist policies f_{i}^{∞}, 0 ≤ i ≤ m, where f_{i}^{∞} is α-optimal for all α ∈ [α_{i}, α_{i−1}). Hence, on any of these intervals the components of the value vector v^{ρ} are elements of F (ℝ).

Furthermore, the optimality equation (3.2) implies that (1 + ρ)v_{i}^{ρ} ≥ (1 + ρ)r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}^{ρ}, (i, a) ∈ E × A, ρ > 0. Therefore, in the ordered field F (ℝ), we have (1 + ρ)v_{i}^{ρ} ≥_{ℓ} (1 + ρ)r_{i}(a) + Σ_{j}p_{ij}(a)v_{j}^{ρ}, (i, a) ∈ E × A. In general, v_{i}^{ρ} is not an element of F (ℝ), but there are elements of F (ℝ) which coincide piecewise with v_{i}^{ρ}.

An N-vector w(ρ) with components in F (ℝ) is called superharmonic if (1 + ρ)w_{i}(ρ) ≥_{ℓ} (1 + ρ)r_{i}(a) + Σ_{j}p_{ij}(a)w_{j}(ρ), (i, a) ∈ E × A. Hence, v^{ρ} is superharmonic. The concept of superharmonicity is useful to derive linear programs for MDP’s.

Lemma 66 v^{ρ} is the smallest superharmonic vector with components in F (ℝ), i.e. for any superharmonic vector w(ρ), w_{i}(ρ) ≥_{ℓ} v_{i}^{ρ}, i ∈ E. Proof. Let w(ρ) be a superharmonic vector. Because there are only a finite number of states and actions, there exists a ρ_{0} > 0 such that (1 + ρ)w_{i}(ρ) ≥ (1 + ρ)r_{i}(a) + Σ_{j}p_{ij}(a)w_{j}(ρ), (i, a) ∈ E × A, ρ ∈ (0, ρ_{0}]. Therefore, by the results of discounted rewards, w_{i}(ρ) ≥ v_{i}^{ρ}, i ∈ E, for every ρ ∈ (0, ρ_{0}], i.e. w_{i}(ρ) ≥_{ℓ} v_{i}^{ρ}, i ∈ E.

Lemma 66 implies that the value vector v^{ρ} on the interval (0, ρ_{0}] can be found as optimal solution of the following linear program in F (ℝ):

min{Σ_{j}w_{j}(ρ)|Σ_{j}[(1+ρ)δ_{ij} −p_{iaj}]w_{j}(ρ) ≥_{ℓ} (1+ρ)r_{ia}, (i, a) ∈ E ×A}. (5.14)

Consider also the following linear program in F (ℝ), called the dual program:

max \{Σ_{i,a}(1 + ρ)r_{i}(a) · x_{ia}(ρ)| \begin{matrix}Σ_{i,a}[(1 + ρ) & δ_{ij} − p_{ij}(a)]· \\ & x_{ia}(ρ) =_{ℓ} p_{1}, j ∈ E \\ x_{ia} ≥_{ℓ} p_{0}, & (i, a) ∈ E × A \end{matrix}\} (5.15)

For a fixed real value of ρ, the linear programs (5.14) and (5.15) are the linear programs (3.14) and (3.15) respectively. Also from section 3.3 4 it is known that there is a one-to-one correspondence between the extreme points of (5.15) and the set of deterministic policies.

As in the simplex method, we will rewrite the equalities of (5.15) such that at each iteration there is precisely one positive x(ρ) component in each state. The main difference with the usual simplex method for a fixed value of ρ is that, instead of real numbers, the elements are rational functions. During any iteration, the set of constraints is written in the special form

x_{B} = B^{−1}e − B^{−1}Ax_{N}  (5.16)

where e is the vector with the right-hand-side of (5.15) as components, i.e. p_{1}; x_{B} and x_{N} are the basis and nonbasis variables, B is the basic matrix and A consists of the remaining (nonbasis) columns of (5.15).

We solve the dual program (5.15) in such a way that the optimality of some basic solution, or equivalently some policy f^{∞}, is shown on a certain interval for the value of ρ. This is possible, because for every fixed ρ in that interval the corresponding simplex tableau is an optimal one. At any iteration of the simplex tableau there is a feasible solution x(ρ) of (5.15) and a corresponding ”trial solution” w(ρ) of (5.14), i.e. w(ρ) satisfies the complementary slackness conditions

x_{ia}(ρ)·{Σ_{j}[(1+ρ)δ_{ij} −p_{ij}(a)]w_{j}(ρ)−(1+ρ)r_{i}(a)} = 0, (i, a) ∈ E×A (5.17)

for all ρ in the interval which is considered. Since any basic solution corresponds to a policy f^{∞}, in each state i there is exactly one action, namely f(i), such that x_{if(i)}(ρ) > 0 for all ρ in the actual interval. Hence, by (5.17),

[(1 + ρ)I − P (f)w(ρ) = (1 + ρ)r(f), i.e. w(ρ) = v^{ρ}(f).  (5.18)

The organization of the special simplex method with elements rational functions is based on the following theorem.

Theorem 67 (i) The elements of the simplex tableau can be written as rational functions with a common denominator, which is the product of all previous pivot elements; (ii) The numerator and denominator of the rational functions are polynomials with degree N at most, except for the reduced costs where the numerator may have degree N + 1; (iii) For ρ sufficiently large, the optimal solution x(ρ) is given by the basic variables x_{if(i)}(ρ), where f(i) is such that r_{i}(f(i)) = max_{a} r_{i}(a), i ∈ E. (iv) The pivot operations in the simplex tableau are as follows (n(ρ) is the common denominator):

(a) the numerator of the pivot becomes the next common denominator, and the last common denominator becomes the new numerator of the pivot; (b) the numerators of the other elements in the pivot row are unchanged and the numerators of the other elements in the pivot column are multiplied by -1; (c) for the other elements, say numerator p(ρ), we replace p(ρ) by \frac{p(ρ)t(ρ)−r(ρ)s(ρ)}{n(ρ)}, which is a polynomial where t(ρ) is the numerator of the last pivot and r(ρ) is the numerator of the pivot row which is in the same column as p(ρ), and s(ρ) is the numerator in the pivot column which is in the same row as p(ρ).

Starting with the artificial variables z_{j}(ρ), j ∈ E, as basic variables, we can compute the optimal simplex tableau for ρ = ∞ by exchanging x_{1f(1)} with z_{1}, x_{2f(2)} with z_{2}, …, x_{Nf(N)} with z_{N}, where f(i) is such that r_{i}(f(i)) = max_{a} r_{i}(a), 1 ≤ i ≤ N. This tableau is optimal for ρ ≥ ρ_{1}, where ρ_{1} is the smallest value such that the reduced costs are nonnegative. To compute ρ_{1} we have to determine the zeroes of some polynomials. The column that determines ρ_{1} becomes the next pivot column. After a pivot transformation the next tableau is optimal for [ρ_{2}, ρ_{1}) for some ρ_{2}. In this way we continue until the last interval [ρ_{m} = 0, ρ_{m−1}).

If we are only interested in computing a Blackwell optimal policy, and not in the computation of the intervals with corresponding optimal policies, the method can be described as follows:

1. Start with any policy f^{∞} and compute the corresponding tableau.

2. If every reduced cost is nonnegative with respect to the ordering in F (ℝ), i.e. the dominating coefficient of the numerator of any reduced cost is nonnegative, then the corresponding policy is Blackwell optimal.

Otherwise: take any column with a negative reduced cost as pivot column and execute a pivot transformation.

3. Go to step 2.

Remarks

1. Since in any tranformation the value of the objective function increases, none of the basis can return and therefore the method is finite.

2. The complexity of one pivot transformation is as follows: multiplication and division of the polynomials in the tableaux is O(N^{2}). Hence, the computation of a new element is of order N^{2}, i.e. the computation of a new column is of order N^{3}. Since there are Σ_{i=1}^{N}#A(i) columns, the complexity of one transformation is of order N^{3}[Σ_{i=1}^{N}#A(i)].

Hordijk, Dekker and Kallenberg ^{\underline{hor85}} [114] have developed the simplex method for rational functions for the computation of discounted optimal policies over the whole range of the discount factors, including the computation of a Blackwell optimal policy. Related works are Smallwood ^{\underline{sma66}} [225], Jeroslow ^{\underline{jero}} [129] and Holzbaur ^{\underline{hol86a}} [108], ^{\underline{hol86b}} [109].

1.6 A VARIETY OF OTHER TOPICS

1.6.1 Mean-variance trade-offs

The standard criteria for MDPs based on average or (sensitive) discounted rewards are not always satisfactory. In this section we consider another approach. This approach is especially suitable for a decision maker who prefers to use a criterion which also considers the variability induced by a given policy. How do we measure this variability? We want to have a variability measure which is sensible, mathematically tractable, and for which an optimality concept can be used. It turns out that optimality for all starting states simulaneously is a too strong requirement. Therefore, we will consider the criterion for a fixed initial distribution β. Then, as mean of the rewards for a given policy R, we use

ϕ(β, R) = lim inf_{T →∞} \frac{1}{T} Σ_{t=1}^{T} 𝔼_{β,R}[r_{X}(Y_{t})]  (6.1)

If a policy R satisfies ϕ(β, R) = Σ_{i}β_{i}ϕ_{i}, where ϕ is the value vector, then R is called a β-average-optimal policy.

As variance of the rewards for a given policy R, we use the definition

v(β, R) = lim sup_{T →∞} \frac{1}{T} Σ_{t=1}^{T}𝔼_{β,R}[r_{X_{t}}(Y_{t}) − ϕ(β, R)]^{2}\}  (6.2)

The quantities ϕ(β, R) and v(β, R) can be expressed in the so called stateaction frequencies. For any policy R, any T ∈ ℕ, and any initial distribution β, we denote the expected state-action frequencies in the first T periods by the x^{T} (R), i.e.

x_{ja}^{T}(R) = \frac{1}{T} Σ_{t=1}^{T}ℙ_{β,R}[X_{t} = j, Y_{t} = a], (i, a) ∈ E × A  (6.3)

For a stationary policy π^{∞}, we have

x_{ja}^{T}(π^{∞}) = \frac{1}{T} Σ_{t=1}^{T}Σ_{i}β_{i} · P^{t−1}(π)_{ij}π_{ja}, (i, a) ∈ E × A  (6.4)

By X(R) we denote the limit points of the vectors {x^{T} (R), T = 1, 2, … }. Since 0 ≤ x^{T} (R) ≤ e for every T ∈ ℕ, X(R) ≠ ∅. Any x^{T} (R) satisfies Σ_{j,a}x_{ja}^{T}(R) = 1 and therefore Σ_{j,a}x_{ja}(R) = 1 for every x(R) ∈ X(R). For a stationary policy π^{∞}, we can write

lim_{T →∞} x_{ja}^{T}(π^{∞}) = Σ_{i}β_{i} · [P^{∗}(π)]_{ij}π_{ja}, (i, a) ∈ E × A  (6.5)

i.e. X(π^{∞}) consists of the unique element x(π^{∞}). Furthermore, Σ_{j,a}r_{ja}x_{ja} (π^{∞}) = Σ_{i}β_{i} · ϕ_{i}(π^{∞})_{i}. We introduce the notation L, L(M), L(S) and L(D) for the elements of X(R) corresponding to general, Markov, stationary and deterministic policies, respectively. For policies R with #X(R) = 1, e.g. stationary policies, we denote the unique element of X(R) by x(R). For such policies the variance satisfies

v(β, R) = Σ_{j,a}x_{ja}(R)r_{j}^{2}(a) − [Σ_{j,a}x_{ja}(R)r_{j}(a)]^{2}  (6.6)

Let X be the projection of the feasible solutions (x, y) of the linear program (4.10) on the x-space, i.e.

X = \{x | \begin{matrix}Σ_{i,a}[δ_{ij} − p_{ij}]x_{ia} & = 0, & j ∈ E \\ Σ_{a}x_{ja} + Σ_{i,a}[δ_{ij} − p_{ij}(a)]y_{ia} & = β_{j}, & j ∈ E for some y \\ x_{ia}, y_{ia} ≥ 0, & & (i, a) ∈ E × A \end{matrix}\} (6.7)

Then, the next theorem can be shown.

Theorem 68 \overline{L(D)} = \overline{L(S)} = L(M) = L = X, where \overline{S} is the closed convex hull of a set S.

There are several sensible formulations for the mean-variance problem. We consider the following three formulations.

(1) Maximal mean-variance ratio with lower bound on the mean

max \{\frac{[ϕ(β, R]^{2}}{v(β, R)} |ϕ(β, R) ≥ L\}  (6.8)

This problem can equivalently be written as

max \{\frac{−Σ_{j,a}x_{ja}(R)r_{j}^{2}(a)}{[Σ_{j,a}x_{ja}(R)r_{j}(a)]^{2}} | Σ_{j,a}x_{ja}(R)r_{j}(a) ≥ L\}  (6.9)

For this problem we consider the mathematical programming problem

max \{\frac{−Σ_{j,a}x_{ja}r_{j}^{2}(a)}{[Σ_{j,a}x_{ja}r_{j}^{2}(a)]} | \begin{matrix}x ∈ X, \\ Σ_{j,a}x_{ja}r_{j}(a) ≥ L \end{matrix}\}  (6.10)

(2) Minimal variance with lower bound on the mean

min{v(β, R)|ϕ(β, R) ≥ L}  (6.11)

This problem can be rewritten as

max {−Σ_{j,a}x_{ja}(R)r_{j}^{2}(a)+[Σ_{j,a}x_{ja}(R)r_{j}(a)]^{2} | Σ_{j,a}x_{ja}(R)r_{j}(a)≥L} (6.12)

with as mathematical programming formulation

max \{−Σ_{j,a}x_{ja}r_{j}^{2}(a) + [Σ_{j,a}x_{ja}r_{j}(a)]^{2} | \begin{matrix}x ∈ X \\ Σ_{j,a}x_{ja}r_{j}(a) ≥ L \end{matrix}\}  (6.13)

(3) Variance-penalized formulation

max{ϕ(β, R) − λ · v(β, R)} for some penalty λ > 0  (6.14)

This problem is equivalent to

max{Σ_{j,a}x_{ja}(R)r_{j}(a) − λ · [Σ_{j,a}x_{ja}(R)r_{j}^{2}(a) − (Σ_{j,a}x_{ja}(R)r_{j}(a))^{2}]} (6.15)

which yields the mathematical program

max {Σ_{j,a}x_{ja}r_{j}(a) − λ · {Σ_{j,a}x_{ja}r_{j}^{2}(a) − [Σ_{j,a}x_{ja}r_{j}(a)]^{2}} |x ∈ X } (6.16)

The mathematical programs (6.10), (6.13) and (6.16) are special cases of the following unifying program

max \{\frac{Σ_{j,a}B_{ja}x_{ja}}{D(Σ_{j,a}R_{ja}x_{ja}]} + C(Σ_{j,a}R_{ja}x_{ja}) | \begin{matrix}x ∈ X \\ L ≤ Σ_{j,a}R_{ja}x_{ja} ≤ U \end{matrix} \} (6.17)

with (a) C is a convex function; (b) if D is not a constant, then (i) D is positive, convex and nondecreasing, (ii) C is nondecreasing and (iii) Σ_{j,a}B_{ja}x_{ja} ≤ 0 for every x ∈ X.

In order to solve (6.17), we consider a parametric version of (4.10) with B_{ia} + ϑR_{ia} instead of r_{i}(a), (i, a) ∈ E × xA, i.e.

max\{Σ_{i,a}x_{ia}[B_{ia} + ϑR_{ia}] | \begin{matrix}Σ_{i,a}[δ_{ij} − p_{ij}]x_{ia} & = 0, & j ∈ E \\ Σ_{a}x_{ja} + Σ_{i,a}[δ_{ij} − p_{ij}(a)]y_{ia} & = β_{j}, & j ∈ E \\ x_{ia}, y_{ia} ≥ 0, (i, a) ∈ E × A \end{matrix}\} (6.18)

with ϑ ∈ (−∞, +∞) as the parameter. It is well known that the optimal solution x(ϑ) is a piecewise constant function of ϑ with values being extreme points of X, and the optimal value is a piecewise linear, convex function of ϑ. Thus, there exist ϑ_{0} ≡ −∞ < ϑ_{1} < ⋯ < ϑ_{m−1} < ϑ_{m} ≡ +∞ such that x(ϑ) = x^{n} for ϑ ∈ [ϑ_{n−1}, ϑ_{n}], 1 ≤ n ≤ m, with x^{n} an extreme point of X.

Let k + 1 and j + 1 be respectively the smallest integers among 0, 1, …, m such that Σ_{i,a}R_{ia}x_{ia}^{k+1} > U and Σ_{i,a}R_{ia}x_{ia}^{j+1} ≥ L. Furthermore, let α ∈ (0, 1] and β ∈ [0, 1) be such that x^{U} = αx^{k}+(1−α)x^{k+1} and x^{L} = βx^{j}+(1−β)x^{j+1} satisfy Σ_{i,a}R_{ia}x_{ia}^{U} = U and Σ_{i,a}R_{ia}x_{ia}^{L} = L. Let G(x) = Σ_{j,a}B_{ja}x_{ja}, g(x) = Σ_{j,a}R_{ja}x_{ja} and V (x) = \frac{G(x)}{D(g(x))} + C(g(x)) for x ∈ X, and let G_{n} = G(x^{n}), g_{n} = g(x^{n}) and V^{n} = V (x^{n}), 1 ≤ n ≤ m. Furthermore, define Vopt = max{max_{j+1≤n≤k} V^{n}, V (x^{L}), V (x^{U})}.

Theorem 69 (i) Program (6.17) is feasible if and only if g(x^{m}) ≥ L and g(x^{1}) ≤ U; (ii) If program (6.17) is feasible, then Vopt is the optimal value of (6.17), and the maximizing x is the optimal solution xopt.

If there are no bounds L and U for Σ_{j,a}R_{ja}x_{ja}, then Vopt = V (x^{n}) for some extreme point x^{n} of X. Theorem 69 provides a way to find an optimal solution for the program (6.17). But it does not provide a procedure to construct an optimal policy for the corresponding Markov decision chain. The next two theorems give the answer.

Theorem 70 If (x, y) is an extreme optimal solution for (6.18) for all ϑ in an open interval, then any deterministic policy f^{∞} with x_{if(i)} > 0 if Σ_{a}x_{ia} > 0 and y_{if(i)} > 0 if Σ_{a}x_{ia} = 0 ∧ Σ_{a}y_{ia} > 0 has a state-action frequency vector x(f^{∞}) satisfying Σ_{i,a}B_{ia}x_{ia}(f^{∞}) = Σ_{i,a}B_{ia}x_{ia}, Σ_{i,a}R_{ia}x_{ia}(f^{∞}) = Σ_{i,a}R_{ia}x_{ia} and V (x(f^{∞})) = V (x).

Theorem 71 If program (6.17) is feasible, then either xopt = x^{n} for some j +1 ≤ n ≤ k and there exists an optimal deterministic policy, or xopt = x^{L} (or x^{U}) and an initial randomization of two deterministic policies is optimal for the mean-variance trade-off problem. These policies can be determined analogously to the policy in theorem 70.

Corollary 72 For an unconstrained mean-variance trade-off problem, i.e. without the constraint L ≤ Σ_{i,a}R_{ia}x_{ia} = U, there exists a deterministic optimal policy.

Remarks

1. The discounted and the average-unichain case can be treated in the same way as above. In fact, these cases are more simple. In the discounted case, there is a one-to-one correspondence between the deterministic policies and the extreme solutions. In the unichain case the initial distribution has no influence and the parametric linear program is more simple.

2. The optimal policy R_{∗} is also Pareto-optimal with respect to the pair (ϕ(R), −V (R)), i.e. there doesn’t exist a policy R such that ϕ(R) ≥ ϕ(R_{∗}) and −V (R) ≥ −V (R_{∗}), with a strict inequality holding for at least one of the two inequalities.

State-action frequencies for the unichain case are discussed in Derman ^{\underline{der70}} [58]. The multichain case is analysed in Kallenberg ^{\underline{kal83}} [135] and Hordijk en Kallenberg ^{\underline{hor84b}} [117], who have shown theorem 68. State-action frequencies play also an important role in multiple-objective MDP and for MDPs with additional constraints. Contributions in this area are made by Derman and Veinott ^{\underline{der72}} [62], Thomas ^{\underline{th83}} [241], Ross ^{\underline{ross89}} [196], Ross and Varadarajan ^{\underline{ross91}} [197], Altman and Shwartz ^{\underline{alsh91}} [7] and by Liu and Ohno ^{\underline{liu92}} [157]. The mean-variance formulations (6.8), (6.11) and (6.14) were proposed by Sobel ^{\underline{so85}} [229], Kawai ^{\underline{kawai87}} [143] and Filar, Kallenberg and Lee ^{\underline{filar89}} [78], respectively. Other contributions in this area are Kawai and Katoh ^{\underline{kaka87}} [144], White ^{\underline{white882}} [283], ^{\underline{white92}} [284] and ^{\underline{white94}} [287], Chung ^{\underline{chung89}} [37], ^{\underline{chung92}} [38] and ^{\underline{chung94}} [39], Bayal-Gursoy and Ross ^{\underline{bayros92}} [12], and Sobel ^{\underline{so94}} [230]. The unifying framework is proposed by Huang and Kallenberg ^{\underline{huang}} [124], who also have shown the theorems 69, 70 and 71. Another model with a different criterion is an MDP in which a (weighted) sum of a number of discounting rewards, each with a different discount factor, has to be maximized. This model is studied in Feinberg and Shwartz ^{\underline{fein}} [77].

1.6.2 Optimal stopping

Optimal stopping problems were introduced in section 1.1.4. In an optimal stopping problem there are two actions in each state. The first action is the stopping action and the second action corresponds with continue. If the stopping action is chosen in state i, then a final reward r_{i} is earned and the process terminates. If the second action is chosen in state i, then a cost c_{i} is incurred and the probability of being in state j at the next time point is p_{ij}. Therefore the MDP model is:

\begin{matrix}E = \{1, 2, …, N\}; A(i) = \{1, 2\}, i ∈ E; r_{i}(1) = r_{i}, i ∈ E; \\ r_{i}(2) = −c_{i}, i ∈ E; p_{ij}(1) = 0, i, j ∈ E; p_{ij}(2) = p_{ij}, i, j ∈ E. \end{matrix}

We are interested in finding an optimal stopping rule, i.e. we consider only transient policies. A policy R is called transient if Σ_{t=1}^{∞}ℙ_{i,R}[X_{t} ∈ X] < ∞ for all i ∈ E, i.e. for any starting state i the process terminates in a finite time with probability 1. As optimality criterion the total expected reward is considered i.e.

v_{i}(R) = Σ_{t=1}^{∞}Σ_{j,a}ℙ_{i,R}[X_{t} = j, Y = a] · r_{j}(a)  (6.19)

For the computation of an optimal transient policy, the usual properties of discounted MDPs hold (cf. Kallenberg ^{\underline{kal83}} [135] chapter 3). Let v be the value vector, i.e. v = sup{v(R)|R is transient}. Then, similar to the discounted reward criterion, it can be shown that v is the smallest superharmonic vector, i.e. the smallest vector that satisfies

\{ \begin{matrix}v_{i} ≥ r_{i} & , i ∈ E \\ v_{i} ≥ −c_{i} + Σ_{j}p_{ij}v_{j} & , i ∈ E. \end{matrix}  (6.20)

Hence, the value vector is the unique solution of the linear program

min \{Σ_{j}v_{j}| \begin{matrix}v_{i} ≥ r_{i} & , i ∈ E \\ v_{i} ≥ −c_{i} + Σ_{j}p_{ij}v_{j} & , i ∈ E \end{matrix}\}  (6.21)

As in the discounted case, an optimal policy can be obtained by the dual program. Therefore, the following algorithm can be used.

Algorithm XIII (optimal stopping; linear programming)

1. Determine an optimal solution (x, y) of the dual program

max \{Σ_{i}r_{i}x_{i} − Σ_{i}c_{i}y_{i}|\begin{matrix}x_{j} + y_{j} − Σ_{i} & p_{ij}y_{i} & = 1, & j ∈ E \\ & x_{j}, y_{j} & ≥ 0, & j ∈ E \end{matrix}\}

2. Choose f^{∞} such that f(i) \{ \begin{matrix}1 if x_{j} > 0 \\ 2 if x_{j} = 0. \end{matrix}

Let S = {i ∈ E|r_{i} ≥ −c_{i} + Σ_{j}p_{ij}r_{j}}, i.e. S is the set of states in which immediate stopping is not worse than continuing for one period and than choose the stopping action. An optimal stopping problem is monotone if p_{ij} = 0 for all i ∈ S, j ∉ S, i.e. S is closed under P.

Theorem 73 In a monotone optimal stopping problem the policy f^{∞}, where f(i) = 1 if and only if i ∈ S, is optimal.

Proof. Let w be such that w_{i} = \{ \begin{matrix}r_{i}, i ∈ S \\ v_{i}, i ∉ S. \end{matrix} Then, w is superharmonic,

namely

i ∈ S : w_{i} = r_{i} ≥ −c_{i} + Σ_{j}p_{ij}r_{j} = −c_{i} + Σ_{j∈S}p_{ij}r_{j} = −c_{i} + Σ_{j}p_{ij}w_{j}.
i ∉ S : w_{i} = v_{i} ≥ −c_{i} + Σ_{j}p_{ij}v_{j} ≥ −c_{i} + Σ_{j∈S}p_{ij}r_{j} + Σ_{j∉S}p_{ij}v_{j}
= −c_{i} + Σ_{j}p_{ij}w_{j} and w_{i} = v_{i} ≥ r_{i}.

Since v is the smallest superharmonic vector, it follows that w ≥ v. Hence, i ∈ S : r_{i} = w_{i} ≥ v_{i} ≥ r_{i}, i.e. r_{i} = w_{i} = v_{i} and f(i) = 1 is optimal; i ∉ S : r_{i} < −c_{i} + Σ_{j}p_{ij}r_{j} ≤ −c_{i} + Σ_{j}p_{ij}v_{j} ≤ v_{i}, i.e. f(i) = 2 is optimal.

For monotone stopping problems it is sufficient to determine the set S. The determination of S has complexity of order O(N). For instance, the house selling problem of section 1.4 is monotone with S = {i ∈ E|c ≥ Σ_{j>i}(j − i)p_{j}} = {i ∈ E|i ≥ i_{∗}} where i_{∗} = min{i|c ≥ Σ_{j>i} (j − i)p_{j}}, i.e. S consists of the states i for which the expected income above i in the next week is at most the costs in that week. Furthermore, an optimal policy is to accept an offer as soon as it is at least i_{∗}. Such a policy is said to be a control-limit policy.

A classical paper on optimal stopping problems is Breiman ^{\underline{brei}} [28]. Other papers in this area are Chen ^{\underline{chen73}} [34], Ross ^{\underline{ross69}} [198], Yasuda ^{\underline{yas}} [292] and Sonin ^{\underline{sonin}} [232]. We refer also to the chapter ”Optimal stopping: old and new results and methods” in this book, written by Sonin.

1.6.3 Multi-armed bandit problems

We have introduced this model in section 1.4. At each decision time point the decision maker has the option to work on exactly one project. Any project may be in a finite number of states, say project j in the set E_{j}, 1 ≤ j ≤ n. Hence, the state space is the Cartesian product: E = E_{1} × E_{2} × ⋯ × E_{n}. Each state has the same action set {1, 2, …, n}, where action k means that project k is chosen, 1 ≤ k ≤ n. When project k is chosen, i.e. project k is the active project, the immediate reward and the transition probabilities only depend on project k and the state i ∈ E_{k}. Let r_{i}(k) and p_{ij}(k), j ∈ E_{k}, denote these quantities. The states of the inactive projects are frozen. As utility function the discounted reward is used.

The one-armed bandit stopping problem Consider the one-armed bandit stopping problem, i.e. in each state there are two actions: action 1 is the stopping action where we earn a final reward M and by action 2 the process continues with immediate reward r_{i} and transition probabilities p_{ij}. Let v^{α}(M) be the value vector of this optimal stopping problem. In the previous section it was discussed how this vector v^{α}(M) and an optimal policy can be computed by the linear programming programs

min \{Σ_{j}v_{j} | \begin{matrix}v_{i} ≥ r_{i} + αΣ_{j}p_{ij}v_{j}, & i ∈ E \\ v_{i} ≥ M, & i ∈ E \end{matrix}\}  (6.22)

and its dual

max \{Σ_{i}r_{i}x_{i} + M · Σ_{i}y_{i} | \begin{matrix}Σ_{i}(δ_{ij} − αp_{ij}) & x_{i} + y_{j} & = 1, j ∈ E \\ & x_{i}, y_{i} & ≥ 0, i ∈ E \end{matrix}\} (6.23)

Lemma 74 For all i ∈ E, v_{i}^{α}(M) − M is a nonnegative continuous nonincreasing function in M. Proof. The nonnegativity of v_{i}^{α}(M) − M is obvious. By the method of value iteration v^{α}(M) can be approximated by v_{i}^{1}(M) = M, i ∈ E; v_{i}^{n+1}(M) = max{M, r_{i} + αΣ_{j}p_{ij}v_{j}^{n}(M)}, i ∈ E, n ≥ 1. Substituting w_{i}^{n} = v_{i}^{n} − M for all i and n, we obtain w_{i}^{1}(M) = 0, i ∈ E; w_{i}^{n+1}(M) = max{0, r_{i} + αΣ_{j}p_{ij}w_{j}^{n}(M) − (1 − α)M}, i ∈ E, n ≥ 1. By induction on n, it can be shown that w_{i}^{n}(M) is continuous and nonincreasing in M. Hence, the limit v_{i}^{α}(M)−M is also a continuous nonincreasing function in M for all i ∈ E.

Let M_{i}^{α} = min{M|v_{i}^{α}(M) = M}, i ∈ E, called the Gittins indices.

Theorem 75 The policy f^{∞}, which chooses the stopping action in state i if and only if M_{i}^{α} ≤ M, is optimal. Proof. Let (x, y) be an extreme optimal solution of linear program (6.23). Then in each state i only one of the variables x_{i} or y_{i} is basic and positive.

When x_{i} > 0 then continuing is optimal; otherwise it is optimal to stop. Suppose that, M_{i}^{α} > M, i.e. v_{i}^{α}(M) > M. Then, by the complementary slackness, y_{i} = 0 and it is optimal to continue. Otherwise, suppose that when the stopping action is chosen, i.e. M_{i}^{α} ≤ M, this action is not optimal. This implies, v_{i}^{α}(M) = r_{i} + αΣ_{j}p_{ij}v_{j}^{α}(M) > M and consequently M < M_{i}^{α}, wich yields a contradiction.

For M = M_{i}^{α} both actions (stop or continue) are optimal in state i. Hence, an interpretation of the Gittins index M_{i}^{α} is the value of M where both actions are simultaneously optimal, and therefore M_{i}^{α} is also called the indifference value.

Multi-armed bandits Next, we assume that there are in each state n + 1 actions: action k, 1 ≤ k ≤ n, means continue with project k, and action 0 stops the process with a terminal reward M. Let v^{α}(M) be the value vector, f_{M}^{∞} the optimal policy and T (M) the stopping time, i.e. the expected time before the process terminates with the final reward M. Let C = (1 − α)^{−1} · max_{i,k} |r_{i}(k)|, then C is an upper bound of the total discounted rewards (without the terminal rewards). Hence, if M ≥ C, then immediate stopping is optimal in all states.

The following results are in some sense obvious: v^{α}(M) is nondecreasing in M and a small change in M will change the value (per unit change) with the discounted (unit) terminal reward α^{T (M)}.

Lemma 76 For all i ∈ E, (i) v_{i}^{α}(M) is a nondecreasing, convex function in M; (ii) \frac{∂}{∂M} v_{i}^{α}(M) = 𝔼_{i,f_{M}^{∞}}[α^{T (M)}].

The next theorem is the key theorem for the multi-armed bandit problem. It says that an optimal action in a state i = (i_{1}, i_{2}, …, i_{n}) is to choose the project which has, for the given state of the project, the smallest Gittins index. This is an interesting result. It is surprising that these indices depend only on the individual project and not on the other projects. Hence, they can be computed independently for each project. By this property, the dimensionality of the problem is considerably reduced.

Theorem 77 In state i = (i_{1}, i_{2}, …, i_{n}) the optimal policy chooses action k, where k is such that M_{i_{k}}^{α} = max_{j} M_{i_{j}}^{α}.

Alternative interpretation of the Gittins index Consider the one-armed bandit process with initial state i. If M = M_{i}^{α} the optimal policy is indifferent between stopping and continuing, so that for any stopping time T, M_{i}^{α} ≥ 𝔼[discounted reward before T] + M_{i}^{α} · 𝔼[α^{T}], with equality for the optimal policy. Hence, (1 − α)M_{i}^{α}=max_{T ≥1} 𝔼[discounted reward before T]/[{1 − 𝔼(α^{T})}/(1 − α)] =max_{T ≥1} 𝔼[discounted reward before T]/𝔼[discounted time before T],

where the expectations are conditional on the initial state i. Thus, another way to describe the optimal policy in the multi-armed bandit problem is as follows. For each individual project look for the stopping time T whose ratio of expected discounted reward and expected discounted time prior to T is maximal. Then work on the project with the largest ratio. In the case there also is the extra option of stopping, one should stop if all ratios are smaller than (1 − α)M.

Computation of the Gittins indices by parametric linear programming We have already seen that for one project the Gittins index is related to the linear programs (6.22) and (6.23). For M big enough, an optimal solution (x, y) of (6.23) will satisfy y_{i} > 0, i ∈ E. Decreasing M will give that some y_{i} becomes 0 for a certain value of M. For this M there is indifference between stopping and continuing, i.e. this M is the Gittins index in state i. By further decreasing M one can compute the next Gittins index, and so on. Hence, by parametric linear programming with parameter M which goes from +∞ to −∞, all Gittins indices can be computed for one project. In the first tableau the y-variables are the basic variables. Setting up this tableau is of O(N^{2}). Then, there are N transformations, by each transformation one Gittins index, is computed and each transformation is of O(N^{2}). Therefore, the overall complexity is O(N^{3}).

Interpretation as restart-in-k problem We will derive another interpretation for the Gittins index M_{k}^{α} in a fixed state k. For any terminal value M, we have

v_{i}^{α}(M) = max{M, r_{i} + αΣ_{j}p_{ij}v_{j}^{α}(M)}, i ∈ E  (6.24)

and in state k, for M = M_{k}^{α},

v_{k}^{α}(M) = M_{k}^{α} = r_{k} + αΣ_{j}p_{kj}v_{j}^{α}(M_{k}^{α})  (6.25)

Substituting (6.25) in (6.24) gives

v_{i}^{α}(M_{k}^{α}) = max{r_{k} + αΣ_{j}p_{kj}v_{j}^{α}(M_{k}^{α}), r_{i} + αΣ_{j}p_{ij}v_{j}^{α}(M_{k}^{α})}, i ∈ E (6.26)

Hence, M_{k}^{α} is the k-th component of the value vector of the MDP where there are in each state two actions. By the first action the process is restarted in state k, and the second action continues the process. Since M_{k}^{α} can be found as the k-th component of the value vector of the restart-in-k problem, it can be computed by the following linear program

max \{Σ_{j}v_{j} | \begin{matrix}Σ_{j}(δ_{ij} − αp_{ij})v_{j} ≥ r_{i}, & i ≠ k \\ Σ_{j}(δ_{ij} − αp_{kj})v_{j} ≥ r_{k}, & i ∈ E \end{matrix}\}  (6.27)

For this restart-in-k problem, one can also characterize the states where it is optimal to choose action ’continue’.

Theorem 78 Let C_{k} = {i| to continue is optimal for the restart-in-k problem}. Then, C_{k} = {i ∈ E|M_{i}^{α} ≥ M_{k}^{α}}.

Largest remaining index As in parametric linear programming, also by the result on the largest remaining index (see the theorem below) the indices can be computed in a sequence, starting with the largest index.

Theorem 79 Suppose that, for some k, M_{1}^{α} ≥ M_{2}^{α} ≥ ⋯ ≥ M_{k}^{α}, and M_{k}^{α} ≥ M_{i}^{α} for all i > k. Let l_{k} be such that M_{l_{k}}^{α} = max_{i>k} M_{i}^{α} (the largest remaining index).

Then, we have (1−α)M_{l_{k}}^{α} = max_{i>k} \frac{[(I−αP^{k})^{−1}r]_{i}}{[(I−αP^{k})^{−1}e]_{i}}, where [P^{k}]_{ij} =\{ ; \begin{matrix}p_{ij}, & j ≤ k \\ 0, & j > k. \end{matrix}

Proof. v_{i}^{α}(M_{l_{k}}^{α}) ≥ r_{i} + αΣ_{j}p_{ij}v_{j}^{α}(M_{l_{k}}^{α}), i ∈ E, with equality for the state l_{k}. Since v_{i}^{α}(M) = M for M ≥ M_{i}^{α}, v_{i}^{α}(M_{l_{k}}^{α}) ≥ r_{i}+αΣ_{j≤k}p_{ij}v_{j}^{α}(M_{l_{k}}^{α})+αM_{l_{k}}^{α}[1− Σ_{j≤k}p_{ij}], i ∈ E. In vector notation this relation can be written as v ≥ r+αP^{k}v+αM_{l_{k}}^{α}e−αM_{l_{k}}^{α}P^{k}e = r+αP^{k}v−(1−α)M_{l_{k}}^{α}e+M_{l_{k}}^{α}[I −αP^{k}]e, i.e. [I − αP^{k}]v ≥ r − (1 − α)M_{l_{k}}^{α}e + M_{l_{k}}^{α}[I − αP^{k}]e, and consequently, v ≥ [I −αP^{k}]r −(1−α)M_{l_{k}}^{α}[I −αP^{k}]e+M_{l_{k}}^{α}e. Componentwise for i > k, we have M_{l_{k}}^{α} = v_{i}^{α}(M_{l_{k}}^{α}) ≥ [(I − αP^{k})r]_{i} − (1 − α)M_{l_{k}}^{α}[(I − αP^{k})e]_{i} + M_{l_{k}}^{α}, with

equality for i = l_{k}. Hence, we obtain (1 − α)M_{l_{k}}^{α} = max_{i>k} \frac{[(I−αP^{k})^{−1}r]_{i}}{[(I−αP^{k})^{−1}e]_{i}}.

In order to find M_{l_{k}}^{α}, we have to invert [I−αP^{k}]. Since successive P^{k} matrices are similar, this can be done efficiently in a recursive way. The computations can be done in O(k^{2}). Hence, the overall complexity is Σ_{k=1}^{N}O(k^{2}) = O(N^{3}).

The basic results on the multi-armed bandit problem are originated by Gittins (Gittins and Jones ^{\underline{gitt74}} [86] and Gittins ^{\underline{gitt79}} [85]). Other proofs of the optimality of the index rule can be found in Whittle ^{\underline{whittle80}} [289] and ^{\underline{whittle82a}} [290], Ross ^{\underline{ross83}} [201], Tsitsiklis ^{\underline{ts86}} [243] and ^{\underline{ts93}} [244], Katehakis and Veinott ^{\underline{kate87}} [142], Weber ^{\underline{web92}} [268] and Ishikida and Varaiya ^{\underline{ishi}} [128]. In honour of Gittins, Whittle has introduced the term Gittins indices. A first linear programming method of O(N^{4}) is proposed by Chen and Kathehakis ^{\underline{chen86}} [35]. Kallenberg ^{\underline{kal86}} [136] has improved this method to O(N^{3}). The interpretation as restart-in-k problem is made by Kathehakis and Veinott ^{\underline{kate87}} [142]. The method of the largest remaining index rule is due to Varaiya, Walrand and Buyokkoc ^{\underline{var}} [255]. A method based on bisection was proposed in Ben-Israel and Flåm ^{\underline{benis90}} [14]. Extension are made in various directions. Branching bandits were studied, e.g. by Weiss ^{\underline{wei88}} [271]; generalized bandits, e.g. in Glazebrook and Owen ^{\underline{glaze91}} [89], and in Glazebrook and Greatrix ^{\underline{glaze95}} [88]. Bertsimas and Niño-Mora ^{\underline{bertsim96}} [24] have proposed a new approach by generalizing the theory of extended polymatroids. Other papers based on this new approach are Glazebrook and Garbe ^{\underline{glaze96}} [87], and Garbe and Glazebrook ^{\underline{garbe}} [84].

1.6.4 Separable Markov decision problems

Separable MDPs have the property that for certain pairs (i, a) of a state i and an action a: (i) the immediate reward is the sum of terms due to the current state and action, i.e. r_{i}(a) = s_{i}+t(a), (ii) the transition probabilities depend only on the action and not on the state from which the transition occurs, i.e. p_{ij}(a) = p_{j}(a).

For separable problems an LP formulation can be given, which involves a smaller number of variables than in the general LP formulation. In this section we consider the multichain undiscounted case. For the discounted case and the unichain undiscounted case we refer to De Ghellinck and Eppen ^{\underline{degh67}} [43] and to Denardo ^{\underline{den68}} [46], respectively.

A separable Markov decision problem has the following structure:

(1) In some states, say the states of E_{1} = {1, 2, …, m), there are subsets of the action sets, say subset A_{1}(i) in state i ∈ E_{1}, such that:

(i) r_{i}(a) = s_{i} + t(a), i ∈ E_{1}, a ∈ A_{1}(i);

(ii) p_{ij}(a) is independent of i : p_{ij}(a) = p_{j}(a), i ∈ E_{1}, a ∈ A_{1}(i), j ∈ E.

(2) The action subsets are nested: A_{1}(1) ⊇ A_{1}(2) ⊇ ⋯ ⊇ A_{1}(m) ≠ ∅.

Let E_{2} = E\E_{1}, A_{2}(i) = A(i)\A_{1}(i), 1 ≤ i ≤ m, A_{2}(i) = A(i), m + 1 ≤ i ≤ N, and B(i) = A_{1}(i) − A_{1}(i + 1), 1 ≤ i ≤ m − 1, B(m) = A_{1}(m). Then A_{1}(i) = ∪_{j=i}^{m}B(j), and the sets B(j) are disjoint. E_{1}, E_{2}, A_{2}(i) or B(i) may be empty.

If the system is observed in a state i ∈ E_{1}, and the decision maker will choose an action from A_{1}(i), the decision process can be considered as follows. First a reward s_{i} is earned and the systems makes a zero-time transitio n to an additional state N + i. In this state there are two options: either to take an action a ∈ B(i) or to take an action from A_{1}(i) − B(i) = A_{1}(i + 1). In the first case reward t(a) is earned and the process moves to state j with probability p_{j}(a), j ∈ E; in the second case we have the same situation as in state N + i + 1, i.e. a zero-time transition is made from state N + i to state N + i + 1.

This formulation can be interpreted as a semi-Markov decision process (see section 6.5). It can be shown that a linear program, which directly provides a deterministic average optimal policy, can be formulated. This linear program is based on linear programming for semi-Markov decision problems (cf. Kallenberg ^{\underline{kal83}} [135], chapter 7). It is not a straightforward application, because there are zero-time transitions which are not allowed in general.

Consider the linear program

minimize Σ_{j=1}^{N}g_{j} + Σ_{j=1}^{m}h_{j} (6.28) Σ_{j=1}^{N}[δ_{ij} − p_{ij}(a)]g_{j} ≥ 0, 1 ≤ i ≤ N, a ∈ A_{2}(i); g_{i} − h_{i} ≥ 0, 1 ≤ i ≤ m −Σ_{j=1}^{N}p_{j}(a)g_{j} + h_{i} ≥ 0, 1 ≤ i ≤ m, a ∈ B(i); h_{i} − h_{i+1} ≥ 0, 1 ≤ i ≤ m − 1 g_{i}+Σ_{j=1}^{N}[δ_{ij} −p_{ij}(a)]u_{j} ≥ r_{i}(a), 1 ≤ i ≤ N, a ∈ A_{2}(i); u_{i}−v_{i} ≥ s_{i}, 1 ≤ i ≤ m h_{i}−Σ_{j=1}^{N}p_{j}(a)u_{j}+v_{i} ≥ t(a), 1 ≤ i ≤ m, a ∈ B(i); v_{i}−v_{i+1} ≥ 0, 1 ≤ i ≤ m−1

The corresponding dual program is (the dual variables corresponding to the constraints of (6.28) are y_{ia}, μ_{i}, z_{ia}, σ_{i}, x_{ia}, λ_{i}, w_{ia} and ρ_{i}):

maximize Σ_{i=1}^{N}Σ_{a∈A(i)}r_{i}(a)x_{ia} + Σ_{i=1}^{m}s_{i}λ_{i} + Σ_{i=1}^{m}Σ_{a∈B(i)}t(a)w_{ia} (6.29)

\begin{aligned}Σ_{i=1}^{N}Σ_{a∈A(i)}[δ_{ij} − p_{ij}(a)]y_{ia} + Σ_{i=1}^{m}δ_{ij}μ_{i} & −Σ_{i=1}^{m}Σ_{a∈B(i)}p_{j})a)z_{ia} \\ & +Σ_{a∈A(j)}x_{ja} = 1, 1 ≤ j ≤ N \end{aligned}

σ_{j} − σ_{j−1} + Σ_{a∈B(j)}w_{ja} − μ_{j} + Σ_{a∈B(j)}z_{ja} = 1, 1 ≤ j ≤ m Σ_{i=1}^{N}Σ_{a∈A_{2}(i)}[δ_{ij} − p_{ij}(a)]x_{ia} + Σ_{i=1}^{m}δ_{ij}λ_{i} − Σ_{i=1}^{m}Σ_{a∈B(i)}p_{j}(a)w_{ia} = 0,

1 ≤ j ≤ N

ρ_{j} − ρ_{j−1} + Σ_{a∈B(j)}w_{ja} − λ_{j} = 0, 1 ≤ j ≤ m; ρ_{0} = ρ_{m} = σ_{0} = σ_{m} = 0; x_{ia}, y_{ia}, z_{ia}, w_{ia}, λ_{i}, μ_{i}, ρ_{i}, σ_{i} ≥ 0 for all i and a.

A proof for the next result can be found in Kallenberg ^{\underline{kal92}} [137].

Theorem 80 (i) The linear programs (6.28) and (6.29) have finite optimal solutions; (ii) If (g, h, u, v) is an optimal solution of program (6.28), then g is the value vector; (iii) Let (y, μ, z, σ, x, λ, w, ρ) be an extreme optimal solution of program (6.29). Define m_{i} and n_{i} by: m_{i} = min{j ≥ i | Σ_{a}w_{ja} > 0} and n_{i} = min{j ≥ i | Σ_{a}(w_{ja} + z_{ja}) > 0}, i ∈ E. Take a deterministic policy f^{∞} such that in state i : x_{if(i)} > 0 if Σ_{a}x_{ia} > 0; w_{m_{i}f(i)} > 0 if Σ_{a}x_{ia} = 0∧λ_{i} > 0; y_{if(i)} > 0 if Σ_{a}x_{ia} = 0∧λ_{i} = 0∧Σ_{a}y_{ia} > 0; w_{n_{i}f(i)} > 0 if Σ_{a}x_{ia} = 0 ∧ λ_{i} = 0 ∧ Σ_{a}y_{ia} = 0 ∧ Σ_{a}w_{n_{i}a} > 0; z_{n_{i}f(i)} > 0 if Σ_{a}x_{ia} = 0 ∧ λ_{i} = 0 ∧ Σ_{a}y_{ia} = 0 ∧ Σ_{a}w_{n_{i}a} = 0. Then, f^{∞} is well defined and an average optimal policy.

There are many applications which can be formulated as separable MDPs. We mention some of them. Replacement problem (cf. Howard’s ^{\underline{ho60}} [122] automobile problem).

The decision maker has two options in each state i: either to continue or to replace the item by another of a certain state j ∈ {1, 2, …, N}. The linear program to solve this problem as general Markov decision problem contains 2N(N + 1) variables and 2N constraints. The reduced linear programming formulation has only 6N variables and 2N + 1 constraints.

Inventory problem

Consider the following inventory model. At the end of each period, the amount i of inventory is observed, where 0 ≤ i ≤ N. The possible actions are: either to order nothing or to order a − i items, where i + 1 ≤ a ≤ N, with fixed ordering costs K and cost c for each ordered item. We assume that the delivery is instantaneous and that there is no backlogging. The linear program to solve this problem as general Markov decision problem has (N +1)(N +2) variables and 2(N +1) constraints. In the reduced formulation of this separable problem, we have 8N−2 variables and 2(2N+1) constraints. In the case that the optimal policy is an (s, S)-policy the underlying Markov chain is unichained. Then a linear program with 3(N −1) variables and N +2 constraints suffices.

Totally separable problem

Suppose that the Markov decision problem has the following structure: E = {1, 2, …, N}; A(i) = {1, 2, …, M}, i ∈ E; r_{i}(a) = s_{i} + t(a), (i, a) ∈ E × A; p_{ij}(a) = p_{j}(a), (i, a) ∈ E × A and j ∈ E. Examples of this model can be found in Sobel ^{\underline{so81}} [228]. Without exploiting the structure, the linear program has 2NM variables and 2N constraints. It can be shown that an optimal myopic solution exists, i.e. the action a_{∗} is optimal in state i, where a_{∗} is determined by:

t(a_{∗}) + Σ_{j=1}^{N}p_{j}(a)s_{j} = max_{1≤a≤M}{t(a) + Σ_{j=1}^{N}p_{j}(a)s_{j}}  (6.30)

This result is a special case of the stochastic game studied in Sobel ^{\underline{so81}} [228] and Parthasarathy, Tijs and Vrieze ^{\underline{part}} [177].

1.6.5 Further subjects

In this chapter the main topics, but not all, of finite MDPs were discussed. In this section we shortly mention some other aspects of MDPs without going into detail.

Semi-Markov decision models

In many applications the times between consecutive decision time points are not identical but random. Such processes are called semi-Markov decision processes if the time until the next decision depends only on the present state i and the action a chosen in state i. We assume that the distribution function F_{ij}^{a}(t) for the random variable τ_{ij}(a), which is the sojourn time until the next decision point if decision a is chosen when the system is in state i and the transition is into state j, is known for all i, j ∈ E and a ∈ A(i).

Semi-Markov decision models are also called Markov renewal programs. The essential results of MDPs can be generalized to semi-MDPs. The semi-MDP model was introduced by Jewell ^{\underline{jew63a}} [130], ^{\underline{jew63b}} [131], Howard ^{\underline{ho63}} [123], De Cani ^{\underline{decani}} [41] and Schweitzer ^{\underline{schw65}} [207]. Contributions for discounted rewards are e.g. Denardo ^{\underline{den67}} [45] (contraction property), De Ghellinck and Eppen ^{\underline{degh67}} [43] and Kallenberg ^{\underline{kal83}} [135] (linear programming), Wessels and Van Nunen ^{\underline{wes75}} [273] (linear programming and policy iteration), Ohno ^{\underline{ohno}} [175] and Schweitzer ^{\underline{schw91}} [214] (value iteration).

In the average reward case, there is a very elegant data transformation, proposed by Schweitzer ^{\underline{schw71b}} [210], which converts a semi-MDP into an equivalent MDP. Let τ_{i}(a) be the expected time until the next decision epoch if action a is chosen when the system is in state i. For 0 < τ ≤ min_{i,a} τ_{i}(a), let

\{ \begin{matrix}\overline{r}_{1}(a) = r_{i}/τ_{i}(a) & , i ∈ E, a ∈ A(i) \\ \overline{p}_{ij}(a) = δ_{ij} − [δ_{ij} − p_{ij}(a)] · τ/τ_{i}(a) & , i, j ∈ E, a ∈ A(i) \end{matrix}  (6.31)

Then, ϕ(π^{∞}) = \overline{ϕ}(π^{∞}), where ϕ(π^{∞}) is the average reward per unit time of the semi-MDP and \overline{ϕ}(π^{∞}) the average reward of the discrete-time MDP with rewards \overline{r}_{i}(a) and transition probabilities \overline{p}_{ij}(a) as defined in (6.31).

Other papers on average reward MDPs are Schweitzer and Federgruen ^{\underline{schw78b}} [217] (optimality equation), Federgruen and Spreen^{\underline{fedspre80}} [75] (policy iteration), Denardo and Fox ^{\underline{denfox68}} [51] (linear programming and policy iteration), Osaki and Mine ^{\underline{osa}} [176] and Kallenberg^{\underline{kal83}} [135] (linear programming), Schweitzer and Federgruen^{\underline{schw79}} [218], and Schweitzer ^{\underline{schw84}} [211] (value iteration). In Denardo ^{\underline{den71}} [48] more sensitive optimality criteria for semi-MDPs are considered.

MDPs with partial information, partial observation and adaptive control In an MDP with partial information the exact state of the process can not be observed at decision epochs. The only information available about the state is a subset of the state space to which the state belongs. Formally, an MDP has partial information if the state space is partitioned into subsets E_{1}, E_{2}, …, E_{m} such that at each decision epoch the only available information is the subset E_{k} to which the state belongs. In the partial information case not all decision rules are feasible: in all states of a subset E_{k}(1 ≤ k ≤ m) the same decision has to be chosen. Such decision rule is called an admissible decision rule. The objective is to find an optimal admissible policy for some optimality criterion with respect to a given initial distribution. Papers on MDPs with partial information are e.g. Smallwood and Sondik ^{\underline{sma73}} [226], Hastings and Sadjani ^{\underline{hast79}} [98], Hordijk and Loeve ^{\underline{hor94}} [118], and Loeve ^{\underline{loe}} [159].

A related model is an MDP with partial observation. In this model there is probabilistic information about the state. Using Bayes’ rules this model can be translated in a model with full information but with a continuous state space, which incorporates the complete history of the process. Papers in this area are Sondik ^{\underline{sondik}} [231], Albright ^{\underline{albr79}} [1], Monahan ^{\underline{mon}} [169], Altman and Shwartz ^{\underline{alsh91b}} [5] and ^{\underline{alsh91c}} [6], Lovejoy ^{\underline{lov87}} [160], ^{\underline{lov91a}} [161] and ^{\underline{lov91b}} [162], Rieder ^{\underline{rie}} [193], Sernik and Markus ^{\underline{ser}} [220], White III ^{\underline{whi76}} [274] and ^{\underline{whi91}} [275], White III and Scherer ^{\underline{whi89}} [276] and ^{\underline{whi94}} [277], and White ^{\underline{white95}} [288].

In adaptive control models the transition probabilities p_{ij}(a) and the rewards r_{i}(a) depend on an unknown parameter ϑ from a parameter space Θ. About these parameters increasing information is obtained when observing the ongoing process. At each decision epoch the decision maker must estimate the true parameter and then adapt the policy to the estimated value. For a survey on adaptive control we refer to Katehakis’ chapter in this book. Further literature about this topic is e.g. Kurano ^{\underline{kur}} [148], Hübner ^{\underline{hub88}} [126], Hernandez-Lerma ^{\underline{her89}} [102], Cavazos-Cadena ^{\underline{cava}} [32] and Burnetas and Katehakis ^{\underline{burn}} [31].

Vector-valued MDPs

In vector-valued MDPs, when the system is in state i and action a is chosen, there is not a single reward r_{i}(a), but a vector r_{i}^{k}(a), 1 ≤ k ≤ m, of rewards. For this model, the concept of optimality is not unambigious. Given an initial distribution β, a policy R and a utility function u (e.g. discounted or average expected rewards), there is an m-vector u(β, R) of returns, where the k-th component u_{k}(β, R) corresponds to the rewards r_{i}^{k}(a). Optimality is defined with respect to a cone C ⊆ ℝ^{m}. Such cone defines a partial ordering in ℝ^{m} : x ≥_{C} y iff x − y ∈ C. A policy R^{∗} is optimal if u(β, R^{∗}) ≥_{C} u(β, R) for all policies R. In general, there does not exist an optimal policy. Therefore, we use the concept of an efficient policy. A policy R^{∗} is efficient if there is not a ’better’ policy, i.e. there is not a policy R with u(β, R) > u(β, R^{∗}). If the cone C = ℝ_{+}^{m}, then efficient policies are also called Pareto-optimal policies. For vector-valued MDPs also the term multi-objective MDPs is used. Papers about vector-valued MDPs are e.g. Furakawa ^{\underline{fura}} [82], White ^{\underline{white82}} [280], Henig ^{\underline{henig}} [101], Kallenberg ^{\underline{kal83}} [135], Durinovic, Lee, Katehakis and Filar ^{\underline{dur}} [65], Ghosh ^{\underline{ghosh}} [90], Liu, Ohno and Nakayama ^{\underline{liuoh}} [158], and Wakuta ^{\underline{wak92}} [262], ^{\underline{wak95}} [263], ^{\underline{wak96}} [264] and ^{\underline{wak99}} [265].

Acknowledgement

I am grateful to Arie Hordijk for introducing me in the interesting subject of MDPs as well as for the cooperation during a long period.

Bibliography

albr79 [1] Albright,S.C. [1979]: ”Structural results for partially observable Markov decision processes”, Operations Research 27, 1041-1053.

alt99 [2] Altman,E. [1999]: ”Constrained Markov decision processes”, Chapman & Hall/CRC, Boca Raton, Florida.

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

alsh91a [4] Altman,E. and A.Shwartz [1991a]: ”Sensitivity of constrained Markov decision processes”, Annals of Operations Research 33, 1-22.

alsh91b [5] Altman,E. and A.Shwartz [1991b]: ”Adaptive control of constrained Markov chains”, IEEE-Transactions on Automatic Control 36, 454-462.

alsh91c [6] Altman,E. and A.Shwartz [1991c]: ”Adaptive control of constrained Markov decision chains: criteria and policies”, Annals of Operations Research 28, 101-134.

alsh91 [7] Altman,E. and A.Shwartz [1991]: ”Sensitivity of constrained Markov decision processes”, Annals of Operations Research 33, 1-22.

alsp95 [8] Altman,E. and F.M.Spieksma [1995]: ”The linear program approach in Markov decision processes”, Mathematical Methods of Operations Research 42, 169-188.

bmm85 [9] Baras,J.S., D.J.Ma and A.M.Makowsky [1985]: ”K competing queues with linear costs and geometric service requirements: the μc-rule is always optimal” Systems Control Letters 6, 173-180.

bath73a [10] Bather,J. [1973a]: ”Optimal decision procedures for finite Markov chains. Part II: Communicating systems”, Advances in Applied Probability 5, 521-540. bath73b [11] Bather,J. [1973b]: ”Optimal decision procedures for finite Markov

chains. Part III: General convex systems”, Advances in Applied Probability 5, 541-553.

bayros92 [12] Bayal-Gursoy,M. and K.W.Ross [1992]: ”Variability-sensitivity Markov decision processes”, Mathematics of Operations Research 17, 558-571.

be [13] Bellman,R. [1957]: ”Dynamic programming”, Princeton University Press, Princeton.

benis90 [14] Ben-Israel,A. and S.D.Flam [1990]: ”A bisection/successive approximation method for computing Gittins indices”, Zeitschrift für Operations Research 34, 411-422.

bertse76a [15] Bertsekas,D.P. [1976]: ”Dynamic programming and stochastic control”, Academic Press, New York.

bertse76b [16] Bertsekas,D.P. [1976b]: ”On error bounds for successive approximation methods”, IEEE Transactions on Automatic Control 21, 394-396.

bertse87 [17] Bertsekas,D.P. [1987]: ”Dynamic programming: deterministic and stochastic models”, Prentice-Hall, Englewood Cliff.

bertse95a [18] Bertsekas,D.P. [1995]: ”Dynamic programming and optimal control I”, Athena Scientific, Belmont, Massachusetts.

bertse95b [19] Bertsekas,D.P. [1995]: ”Dynamic programming and optimal control II”, Athena Scientific, Belmont, Massachusetts+.

bertse95c [20] Bertsekas,D.P. [1995c]: ”Generic rank-one corrections for value iteration in Markovian decision problems”, OR Letters 17, 111-119.

bertse98 [21] Bertsekas,D.P. [1998]: ”A new value iteration method for the average cost dynamic programming problem”, SIAM Journal on Control and Optimization 36, 742-759.

bertse78 [22] Bertsekas,D.P. and S.E.Shreve [1978]: ”Stochastic optimal control: the discrete time case”, Academic Press, New York.

bertse91 [23] Bertsekas,D.P. and J.N.Tsitsiklis [1991]: ”An analysis of stochastic shortest path problems”, Mathematics of Operations Research 16, 580-595. bertsim96 [24] Bertsimas,D. and J.Niño-Mora [1996]: ”Conservations laws, extended

polymatroids and multi-armed bandit problems; a polyhedral approach to indexable systems”, Mathematics of Operations Research 21, 257-306.

beut85 [25] Beutler,F.J. and K.W.Ross [1985]: ”Optimal policies for controlled Markov chains with a constraint”, Journal of Mathematical Analysis and Applications 112, 236-252.

bier [26] Bierth,K.-J. [1987]: ”An expected average reward criterion”, Stochastic Processes and Applications 26, 133-140.

bl62 [27] Blackwell,D. [1962]: ”Discrete dynamic programming”, Annals of Mathematical Statistics, 719-726.

brei [28] Breiman,L. [1964]: ”Stopping-rule problems”, in: E.F.Beckenbach (ed.), Applied Combinatorial Mathematics”, Wiley, New York, 284-319.

brown [29] Brown,B.W. [1965]: ”On the iterative method of dynamic programming on a finite space discrete time Markov process”, Annals of Mathematical Statistics 36, 1279-1285.

bruno [30] Bruno,J., P.Downey and G.N.Frederickson [1981]: ”Sequencing tasks with exponential service times to minimize the expected flowtime or makespan”, Journal of the Association for Computing Machinery 28, 100-113.

burn [31] Burnetas,A.N. and M.N.Katehakis [1997]: ”Optimal adaptive policies for Markov decision processes”, Mathematics of Operations Research 22, 222-255.

cava [32] Cavazos-Cadena,R. [1991]: ”Nonparametric estimation and adaptive control in a class of finite Markov decision chains”, Annals of Operations Research 28, 169-184.

chang [33] Chang,C.-S., A.Hordijk, R.Righter and G.Weiss [1994]: ”The stochastic optimality of SEPT in parallel machine scheduling”, Probability in the Engineering and Information Sciences 8, 179-188.

chen73 [34] Chen,M.C.Jr. [1973]: ”Optimal stopping in a discrete search problem”, Operations Research 21, 741-747. chen86 [35] Chen,Y.-R. and M.N.Katehakis [1986] : ”Linear programming for finite

state bandit problems”, Mathematics of Operations Research 11, 180-183.

chow [36] Chow,Y.S. and H.Robbins [1961]: ”A martingale system theorem and applications” in: J.Neyman (ed), ”Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability”, Vol.1, University of Berkeley Press, Berkeley, 93-104.

chung89 [37] Chung, K.-J. [1989]: ”A note on maximal mean/standard deviation ratio in an undiscounted MDP”, OR Letters 8, 201-204.

chung92 [38] Chung, K.-J. [1992]: ”Remarks on maximal mean/standard deviation ratio in an undiscounted MDPs”, Opimization 26, 385-392.

chung94 [39] Chung, K.-J. [1994]: ”Mean-variance trade-offs in an undiscounted MDP: the unichain case”, Operations Research 42, 184-188.

dantzig [40] Dantzig,G.B. [1963]: ”Linear programming and extensions”, Princeton University Press, Princeton, New Jersey.

decani [41] De Cani,J.S. [1964]: ”A dynanmic programming algorithm for embedded Markov chains when the planning horizon is at infinity”, Management Science 10, 716-733.

degh60 [42] De Ghellinck,G.T. [1960]: ”Les problèmes de décisions séquentielles”, Cahiers du Centre de Recherche Opérationelle, 161-179.

degh67 [43] De Ghellinck,G.T. and G.D.Eppen [1967]: ”Linear programming solutions for separable Markovian decision problems”, Management Science 13, 371-394.

dembo [44] Dembo,R.S. and M.Haviv [1984]: ”Truncated policy iteration methods”, OR Letters 3, 243-246.

den67 [45] Denardo,E.V. [1967]: ” Contraction mappings in the theory underlying dynamic programming”, SIAM Review 9, 165-167.

den68 [46] Denardo,E.V. [1968]: ”Separable Markovian decision problems”, Management Science 14, 451-462.

den70 [47] Denardo,E.V. [1970]: ”Computing a bias-optimal policy in a discretetime Markov decision problem”, Operations Research 18, 279-289. den71 [48] Denardo,E.V. [1971]: ”Markov renewal programs with small interest

rates”, Annals of Mathematical Statistics 42, 477-496.

den73 [49] Denardo,E.V. [1973]: ”A Markov decision problem”, in: T.C.Hu and S.M.Robinson (eds.), ”Mathematical Programming”, Academic Press, 33-68.

den82 [50] Denardo,E.V. [1982]: ”Dynamic programming: models and applications”, Prentice-Hall, Englewood Cliff.

denfox68 [51] Denardo,E.V. and B.L.Fox [1968]: ”Multichain Markov renewal programs”, SIAM Journal on Applied Mathematics 16, 468-487.

denmil68 [52] Denardo,E.V. and B.L.Miller [1968]: ”An optimality condition for discrete dynamic programming with no discounting”, Annals of Mathematical Statistics 39, 1220-1227.

den79a [53] Denardo,E.V. and U.G.Rothblum [1979a]: ”Optimal stopping, exponential utility and linear programming”, Mathematical Programming 16, 228-244.

den79b [54] Denardo,E.V. and U.G.Rothblum [1979b]: ”Overtaking optimality for Markov decision chains”, Mathematics of Operations Research 4, 144-152.

depn60 [55] D’Epenoux,F. [1960]: ”Sur un problème de production et de stockage dans l’aléatoire”, Revue Française de Recherche Opérationelle, 3-16.

der62 [56] Derman,C. [1962]: ”On sequential decisions and Markov chains”, Management Science 9, 16-24.

der63 [57] Derman,C. [1963]: ”Optimal replacement rules when changes of states are Markovian”, in: R.Bellman (ed.), ”Mathematical optimization techniques”, The Rand Corporation, R-396-PR, 201-212.

der70 [58] Derman,C. [1970]: ”Finite state Markovian decision processes”, Academic Press, New York.

der65 [59] Derman,C. and M.Klein [1965]: ”Some remarks on finite horizon Markovian decision models”, Operations Research 13, 272-278.

der60 [60] Derman,C. and J.Sacks [1960]: ”Replacement of periodically inspected equipment (an optimal stopping rule)”, Naval Research Logistics Quarterly 7, 597-607. der66 [61] Derman,C. and R.Strauch [1966]: ”A note on memoryless rules for con-

trolling sequential control problems”, Annals of Mathematical Statistics 37, 276-278.

der72 [62] Derman.C. and A.F.Veinott Jr. [1972]: ”Constrained Markov decision chains”, Management Science 19, 389-390.

dietz83 [63] Dietz,H.M. and V. Nollau [1983]: ”Markov decision problems with countable state space”, Akademie-Verlag, Berlin.

dubins [64] Dubins,L. and L.J.Savage [1965]: ”How to gamble if you must”, McGraw-Hill, New York.

dur [65] Durinovics,S., H.M.Lee, M.N.Katehakis and J.A.Filar [1986]: ”Multiobjective Markov decision processes with average reward criterion”, Large Scale Systems 10, 215-226.

dyn [66] Dynkin,E.B. [1979]: ”Controlled Markov process”, Springer-Verlag, New York.

eaton [67] Eaton, J.H. and L.A.Zadeh [1962]: ”Optimal pursuit strategies in discrete state probabilistic systems”, Transactions ASME Series D, Journal of Basic Engineering 84, 23-29.

ephr [68] Ephremides,A., P.Varaiya and J.Walrand [1980]: ”A simple dynamic routing problem”, IEEE Transactions on Automatic Control AC-25, 690-693.

fed84 [69] Federgruen,A. [1984]: ”Markovian control problems: functional equations and algorithms”, Mathematical Centre Tract 97, Mathematical Centre, Amsterdam.

fed78 [70] Federgruen,A. and P.J.Schweitzer [1978]: ”Discounted and undiscounted value iteration in Markov decision problems: a survey”, in: M.L.Puterman (ed), ”Dynamic programming and its applications”, Academic Press, New York, 23-52.

fed80 [71] Federgruen,A. and P.J.Schweitzer [1980]: ”A survey of asymptotic value- iteration for undiscounted Markovian decision processes”, in: R.Hartley, L.C. Thomas and D.J.White (eds.), ”Recent development in Markov decision processes”, Academic Press, New York, 73-109.

fed84a [72] Federgruen,A. and P.J.Schweitzer [1984a]: ”A fixed-point approach to undiscounted Markov renewal programs”, SIAM Journal on Algebraic Discrete Methods 5, 539-550. fed84b [73] Federgruen,A. and P.J.Schweitzer [1984b]: ”Successive approximation

methods for solving nested functional equations in Markov decision problems”, Mathematics of Operations Research 9, 319-344.

fst78 [74] Federgruen,A. P.J.Schweitzer and H.C.Tijms [1978]: ”Contraction mappings underlying undiscounted Markov decision problems”, Journal of Mathematical Analysis and Applications 65, 711-730.

fedspre80 [75] Federgruen,A. and D.Spreen [1980]: ”A new specification of the multichain policy iteration algorithm in undiscounted Markov renewal programs”, Management Science 26, 1211-1217.

fedzip84 [76] Federgruen,A. and P.Zipkin [1984]: ”An efficient algorithm for computing optimal (s, S) policies”, Operations Research 34, 1268-1285.

fein [77] Feinberg,E.A. and A.Shwartz [1994]: ”Markov decision models with weighted discounted criteria”, Mathematics of Operations Research 19, 152-168.

filar89 [78] Filar,J.A., L.C.M.Kallenberg and H.M.Lee [1989]: ”Variance-penalized Markov decision processes”, Mathematics of Operations Research 14, 147-161.

filar97 [79] Filar,J.A. and O. J. Vrieze [1997]: ”Competitive Markov decision processes”, Springer-Verlag, New York.

fox [80] Fox,B.L. [1968]: ”(g, w)-optima in Markov renewal programs”, Management Science 15, 210-212.

frost [81] Frostig,E. [1993]: ”Optimal policies for machine repairmen problems”, Journal of Applied Probability 30, 703-715.

fura [82] Furakawa,N. [1980]: ”Characterization of optimal policies in vectorvalued Markovian decision processes”, Mathematics of Operations Research 5, 271-279.

gal [83] Gal,S. [1984]: ”An O(N^{3}) algorithm for optimal replacement problems”, SIAM Journal on Control and Optimization 22, 902-910.

garbe [84] Garbe,R. and K.D.Glazebrook [1998]: ”On a new approach to the analysis of complex multi-armed bandit problems”, Mathematical Methods of Operations Research 48, 419-442.

gitt79 [85] Gittins,J.C. [1979]: ”Bandit processes and dynamic allocation indices”, Journal of the Royal Statistic Society Series B 14, 148-177. gitt74 [86] Gittins,J.C. and D.M.Jones [1974]: ”A dynamic allocation index for the

sequential design of experiments”, in J.Gani (ed.) ”Progress in Statistics”, North Holland, Amsterdam, 241-266.

glaze96 [87] Glazebrook,K.D. and R.Garbe [1996]: ”Reflections on a new approach to Gittins indexation”, Journal of the Operational Research Society 47, 1301-1309.

glaze95 [88] Glazebrook,K.D. and S. Greatrix [1995]: ”On transforming an index for generalized bandit problems”, Journal of Applied Probability 32, 168-182.

glaze91 [89] Glazebrook,K.D. and R.W.Owen [1991]: ”New results for generalized bandit problems”, International Journal of System Sciences 22, 479-494.

ghosh [90] Ghosh,M.K. [1990]: ”Markov decision processes with multiple costs”, OR Letters 9, 257-260.

grin [91] Grinold,R. [1973]:”Elimination of suboptimal actions in Markov decision problems”, Operations Research 21, 848-851.

hart [92] Hartley,R., A.C.Lavercombe and L.C.Thomas [1986]: ”Computational comparison of policy iteration algorithms for discounted Markov decision processes”, Computers and Operations Research 13, 411-420.

hast68 [93] Hastings,N.A.J. [1968]: ”Some notes on dynamic programming and replacement”, Operational Research Quarterly 19, 453-464.

hast69 [94] Hastings,N.A.J. [1969]: ”Optimization of discounted Markov decision problems”, Operations Research Quarterly 20, 499-500.

hast71 [95] Hastings,N.A.J. [1971]: ”Bounds on the gain of a Markov decision process”, Operatios Research 19, 240-243.

hast76 [96] Hastings,N.A.J. [1976]: ”A test for nonoptimal actions in undiscounted finite Markov decision chains”, Management Science 23, 87-92.

hast73 [97] Hastings,N.A.J. and J.M.C.Mello [1973]: ”Tests for nonoptimal actions in discounted Markov decision problems”, Management Science 19, 1019-1022.

hast79 [98] Hastings,N.A.J. and D.Sadjani [1979]: ”Markov programming with policy constraints”, European Journal of Operations Research 3, 253-255. hast77 [99] Hastings,N.A.J. and J.A.E.E. Van Nunen [1977]: ”The action elim-

ination algorithm for Markov decision processes”, in H.C.Tijms and J.Wessels (eds), Markov decision theory, Mathematical Centre Tract 100, 161-170, Mathematical Centre, Amsterdam.

haviv [100] Haviv,M. and M.L.Puterman [1991]: ”An improved algorithm for solving communicating average reward Markov decision processes”, Annals of Operations Research 28, 229-242.

henig [101] Henig,M.I. [1983]: ”Vector-valued dynamic programming”, SIAM Jorrnal on Control and Optimization 21, 490-499.

her89 [102] Hernández-Lerma,O. 1987]: ”Adaptive Markov control processes”, Springer-Verlag, New York.

her96 [103] Hernández-Lerma,O. and J. B. Lasserre [1996]: ”Discrete-time Markov control processes: Basic optimality criteria”, Springer-Verlag, New York.

her99 [104] Hernández-Lerma,O. and J. B. Lasserre [1999]: ”Further topics on discrete-time Markov control processes”, Springer-Verlag, New York.

herz [105] Herzberg,M. and U.Yechiali [1994]: ”Accelerating procedures of the value iteration algorithm for discounted Markov decision processes, based on a one-step look-ahead analysis”, Operations Research 42, 940-946.

hey84 [106] Heyman,D.P. and M. J. Sobel [1984]: ”Stochastic models in Operations Research, Volume II, MacGraw-Hill, New York.

hin70 [107] Hinderer,K. [1970]: ”Foundations of non-stationary dynamic programming with discrete time parameter”, Springer-Verlag, New York.

hol86a [108] Holzbaur,U.D. [1986a]: ”Entscheidungsmodelle über angeordneten Körpern”, Optimization 17, 515-524.

hol86b [109] Holzbaur,U.D. [1986b]: ”Sensitivitätsanalysen in Entscheidungsmodellen”, Optimization 17, 525-533.

hol94 [110] Holzbaur,U.D. [1994]: ”Bounds for the quality and the number of steps in Bellman’s value iteration algorithm”, OR Spektrum 15, 231-234.

hor71 [111] Hordijk,A. [1971]: ”A sufficient condition for the existence of an optimal policy with respect to the average cost criterion in Markovian decision processes”, Transactions of the Sixth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, Academia, Prague, 263-274.

hor74 [112] Hordijk,A. [1974]: ”Dynamic programming and Markov potential theory”, Mathematical Centre Tract 51, Amsterdam.

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

hor85 [114] Hordijk,A., R.Dekker and L.C.M.Kallenberg [1985]: ”Sensitivityanalysis in discounted Markovian decision problems”, OR Spektrum 7, 143-151.

hor79 [115] Hordijk,A. and L.C.M.Kallenberg [1979]: ”Linear programming and Markov decision chains”, Management Science 25, 352-362.

hor84a [116] Hordijk,A. and L.C.M.Kallenberg [1984a]: ”Transient policies in discrete dynamic programming: linear programming including suboptimality tests and additional constraints”, Mathematical Programming 30, 46-70.

hor84b [117] Hordijk,A. and L.C.M.Kallenberg [1984b]: ”Constrained undiscounted stochastic dynamic programming”, Mathematics of Operations Research 9, 276-289.

hor94 [118] Hordijk,A. and J.A.Loeve [1994]: ”Undiscounted Markov decision chains with partial information; an algorithm for computing a locally optimal periodic policy”, Mathematical Methods of Operations Research 40, 163-181.

hortym74 [119] Hordijk,A. and H.C.Tijms [1974]: ”The method of successive approximations and Markovian decision problems”, Operations Research 22, 519-521.

hor75 [120] Hordijk,A. and H.C.Tijms [1975]: ”A modified form of the iterative method of dynamic programming”, Annals of Statictics 3, 203-208.

hortym75 [121] Hordijk,A. and H.C.Tijms [1975]: ”On a conjecture of Iglehart”, Management Science 11, 1342-1345.

ho60 [122] Howard,R.A. [1960]: ”Dynamic programming and Markov processes”, MIT Press, Cambridge. ho63 [123] Howard,R.A. [1963]: ”Semi-Markovian decision processes”, Proceed-

ings International Statistical Institute, Ottawa, Canada.

huang [124] Huang,Y. and L.C.M.Kallenberg [1994]: On finding optimal policies for Markov decision chains: a unifying framework for mean-variance trade-offs”, Mathematics of Operations Research 19, 434-448.

hub77 [125] Hübner,G. [1977]: ”Improved procedures for eliminating suboptimal actions in Markov programming by the use of contraction properties”, Transactions of the 7th Prague Conference on Information Theory, Statistical decision Functions, Reidel, Dordrecht, 257-263.

hub88 [126] Hübner,G. [1988]: ”A unified approach to adaptive control of average reward Markov decision processes”, OR Spektrum 10, 161-166.

igle [127] Iglehart,D. [1963]: ”Optimality of (s, S)-policies in the infinite horizon dynamic inventory problem”, Management Science 9, 259-267.

ishi [128] Ishikida,T. and P.Varaiya [1994]: ”Multi-armed bandit problem revisited”, Journal of Optimization Theory and Applications 83, 113-154.

jero [129] Jeroslow,R.G. [1972]: ”An algorithm for discrete dynamic programming with interest rates near zero”, Management Science Research Report no. 300, Carnegie-Mellon University, Pittsburgh.

jew63a [130] Jewell,W.S. [1963a]: ”Markov renewal programming. I: Formulation, finite return models”, Operations Research 11, 938-948.

jew63b [131] Jewell,W.S. [1963b]: ”Markov renewal programming. II: Infinite return models, example”, Operations Research 11, 949-971.

kal81a [132] Kallenberg,L.C.M. [1981a]: ”Finite horizon dynamic programming and linear programming”, Methods of Operations Research 43, 105-112.

kal81b [133] Kallenberg,L.C.M. [1981b]: ”Unconstrained and constrained dynamic programming over a finite horizon”, Report, University of Leiden, The Netherlands.

kal81c [134] Kallenberg,L.C.M. [1981c]: ”Linear programming to compute a biasoptimal policy”, in: B.Fleischmann et al. (eds.) ”Operations Research Proceedings”, 433-440. kal83 [135] Kallenberg,L.C.M. [1983]: ”Linear programming and finite Markovian

control problems”, Mathematical Centre Tract 148, Mathematical Centre, Amsterdam.

kal86 [136] Kallenberg,L.C.M. [1986]: ”Note on M.N.Katehakis and Y.-R.Chen’s computation of the Gittins index”, Mathematics of Operations Research 11, 184-186.

kal92 [137] Kallenberg, L.C.M. [1992]: ” Separable Markovian decision problem: the linear programming method in the multichain case”, OR Spektrum 14,43-52.

kal99 [138] Kallenberg [1999]: ”Combinatorial problems in MDPs”, Report, University of Leiden, The Netherlands (to appear in the Proceedings of the Changsha International Workshop on Markov Processes & Controlled Markov Chains).

kao [139] Kao.P.C. [1973]: ”Optimal replacement rules when the changes of states are semi-Markovian”, Operations Research 21, 1231-1249.

kate84 [140] Katehakis,M.N. and C.Derman [1984]: ”Optimal repair allocation in a series system”, Mathematics of Operations Research 9, 615-623.

kate89 [141] Katehakis,M.N. and C.Derman [1989]: ”On the maintenance of systems composed of highly reliable components”, Management Science 35, 551-560.

kate87 [142] Katehakis,M.N. and A.F.Veinott Jr. [1987]: ”The multi-armed bandit problem: decomposition and computation”, Mathematics of Operations Research 12, 262-268.

kawai87 [143] Kawai,H. [1987]: ”A variance minimization problem for a Markov decision process”, European Journal of Operational Research 31, 140-145.

kaka87 [144] Kawai,H. and N.Katoh [1987]: ”Variance constrained Markov decision process”, Journal of the Operations Research Society of Japan 30, 88-100.

kem [145] Kemeny,J.G. and J.L.Snell [1960]: ”Finite Markov chains”, Van Nostrand, Princeton.

klein [146] Klein,M. [1962]: ”Inspection-maintenance-replacement schedules under Markovian deterioration”, Management Science 9, 25-32. kol [147] Kolesar,P. [1966]: ”Minimum-cost replacement under Markovian de-

terioration”, Management Science 12, 694-706.

kur [148] Kurano,M. [1983]: ”Adaptive policies in Markov decision processes with uncertain transition matrices”, Journal of Information and Optimization Sciences 4, 21-40.

kush71 [149] Kushner,H. [1971]: ”Introduction to stochastic control”, Holt, Rineholt and Winston, New York.

kuke71 [150] Kushner,H. and A.J.Keinmann [1971]: ”Accelerated procedures for the solution of discrete Markov control problems”, IEEE Transactions on Automatic Control 16, 147-152.

lan [151] Lanery,E. [1967]: ”Etude asymptotique des systèmes Markovien à commande”, Revue d’Informatique et Recherche Operationelle 1, 3-56.

las94a [152] Lasserre,J.B. [1994a]: ”A new policy iteraton scheme for Markov decision processes using Schweitzer’s formula”, Journal of Applied Probability 31, 268-273.

las94b [153] Lasserre,J.B. [1994b]: ”Detecting optimal and non-optimal actions in average- cost Markov decision processes”, Journal of Applied Probability 31, 979-990.

lin [154] Lin,W. and P.R.Kumar [1984]: ”Optimal control of a queueing system with two heterogeneous servers”, IEEE Tansactions on Automatic Control AC-29, 696-705.

lipp [155] Lippman,S.A. [1969]: ”Criterion equivalence in discrete dynamic programming”, Operations Research 17, 920-923.

liu94 [156] Liu,J.Y. and K.Liu [1994]: ”An algorithm on the Gittins index”, Systems Science and Mathematical Science 7, 106-114.

liu92 [157] Liu,Q.-S. and K.Ohno [1992]: ”Multiobjective undiscounted Markov renewal program and its application to a tool replacement problem in an FMS”, Information and Decision Techniques 18, 67-77.

liuoh [158] Liu,Q.-S., K.Ohno and H.Nakayama [1992]: ”Multi-objective discounted Markov processes with expectation and variance criteria”, International Journal of System Science 23, 903-914.

loe [159] Loeve,J.A. [1995]: ”Markov decision chains with partial information”, PhD dissertation, University of Leiden, The Netherlands. lov87 [160] Lovejoy,W.S. [1987]: ”Some monotonicity results for partially observed

Markov processes”, Operations Research 35, 736-743.

lov91a [161] Lovejoy,W.S. [1991a]: ”Computationally feasible bounds for partially observed Markov decision processes”, Operations Research 39, 162-175.

lov91b [162] Lovejoy,W.S. [1991b] ”A survey of algorithmic methods for partially observed Markov decision processes”, Annals of Operations Research 28, 47-66.

mac66 [163] Macqueen,J. [1966]: ”A modified programming method for Markovian decision problems”, Journal of Mathematical Analysis and Applications 14, 38-43.

mac67 [164] Macqueen,J. [1967]: ”A test for suboptimal actions in Markov decision problems”, Operations Research 15, 559-561.

manne60 [165] Manne,A.S. [1960]: ”Linear programming and sequential decisions”, Management Science, 259-267.

meis [166] Meister,U. and U.Holzbaur [1986]: ”A polynomial time bound for Howard’s policy improvement algorithm”, OR Spektrum 8, 37-40.

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

mine70 [168] Mine,H. and S. Osaki [1970]: ”Markov decision processes”, American Elsevier, New York.

mon [169] Monahan,G.E. [1982]: ”A survey of partially observable Markov decision processes: theory, models and algorithms”, Management Science 28, 1-16.

mor [170] Morton,T. [1971]: ”Undiscounted Markov renewal programming via modified successive approximations”, Operations Research 19, 1081-1089.

naz [171] Nazareth,J.L. and R.B.Kulkarni [1986]: ”Linear programming formulations of Markov decision processes”, OR Letters 5, 13-16.

ng [172] Ng,M.K. [1999]: ”A note on policy iteration algorithms for discounted Markov decision problems”, OR Letters 25, 195-197. od [173] Odoni,A. [1969]: ”On finding the maximal gain for Markov decision

processes”, Operations Research 17, 857-860.

oez [174] Oezekici,S. [1988]: ”Optimal periodic replacement of multicomponent reliability systems”, Operations Research 36, 542-552.

ohno [175] Ohno,K. [1981]: ”A unified approach to algorithms with a suboptimality test in discounted semi-Markov decision processes”, Journal of the Operations Research Society of Japan 24, 296-323.

osa [176] Osaki,S. and H.Mine [1968]: ”Linear programming algorithms for semi-Markovian decision processes”, Journal of Mathematical Analysis and Applications 22, 356-381.

part [177] Parthasarathy,T., S.H.Tijs and O.J.Vrieze [1984], ”Stochastic games with state independent transitions and reparable rewards. 262-271 in: G.Hammer and D.Pallaschke (eds), Selected Topics in Operations Research and Mathematical Economics.

pla [178] Platzman,L.K. [1977]: ”Improved conditions for convergence in undiscounted Markov renewal programming”, Operations Research 25, 529-533.

pol [179] Pollatschek,M.A. and B.Avi-Itzhak [1969]: ”Algorithms for stochastic games with geometric interpretation”, Management Science 15, 399-415.

por71 [180] Porteus,E.L. [1971]: ”Some bounds for discounted sequential decision processes”, Management Science 18, 7-11.

por75 [181] Porteus,E.L. [1975]: ”Bounds and transformations for discounted finite Markov decision chains”, Operations Research 23, 761-784.

por80a [182] Porteus,E.L. [1980a]: ”Improved iterative computation of the expected return in Markov and semi-Markov chains”, Zeitschrift für Operations Research 24, 155-170.

por80b [183] Porteus,E.L. [1980b]: ”Overview of iterative methods for discounted finite Markov and semi-Markov chains”, in: R.Hartley, L.C. Thomas and D.J.White (eds.), ”Recent development in Markov decision processes”, Academic Press, New York, 1-20.

por81 [184] Porteus [1981]: ”Computing the discounted return in Markov and semi- Markov chains”, Naval Research Logistics Quarterly 28, 567-577. por78 [185] Porteus,E.L. and J.C.Totten [1978]: ”Accelerated computation of the

expected discounted return in a Markov chain”, Operations Research 26, 350-358.

put81 [186] Puterman,M.L. [1981]: ”Computational methods for Markov decision methods”, Proceedings of 1981 Joint Automatic Control Conference.

put94 [187] Puterman,M.L. [1994]: ”Markov decision processes”, Wiley, New York.

put79 [188] Puterman,M.L. and S.L.Brumelle [1979]: ”On the convergence of policy iteration in stationary dynamic programming”, Mathematics of Operations Research 4, 60-69.

put78 [189] Puterman,M.L. and M.C.Shin [1978]: ”Modified policy iteration algorithms for discounted Markov decision chains”, Management Science 24, 1127-1137.

put82 [190] Puterman,M.L. and M.C.Shin [1982]: ”Action elimination procedures for modified policy iteration algorithms” Operations Research 30, 301-318.

ree73 [191] Reetz,D. [1973]: ”Solution of a Markovian decision problem by successive overrelaxation”, Zeitschrift für Operations Research 17, 29-32.

ree76 [192] Reetz,D. [1976]: ”A decision exclusion algorithm for a class of Markovian decision processes” , Zeitschrift für Operations Research 20, 125-131.

rie [193] Rieder,U. [1991]: ”Structural results for partially observed control problems”, Zeitschrift für Operations Research 35, 473-490.

rig [194] Righter,R. [1994]: ”Scheduling”, in: Shaked,M. and J.G.Shantikumar (eds.), ”Stochastic orders and their applications”, Academic Press, 381-432.

roo [195] Roosta,M. [1982]: ”Routing through a network with maximum reliability”, Journal of Mathematical Analysis and Applications 88, 341-347.

ross89 [196] Ross,K.W. [1989]: ”Randomized and past-dependent policies for Markov decision processes with multiple constraints”, Operations Research 37, 474-477. ross91 [197] Ross,K.W. and R.Varadarajan [1991]: ”Multichain Markov decision

processes with a sample path constraint: a decomposition approach”, Mathematics of Operations Research 16, 195-207.

ross69 [198] Ross,S.M. [1969]: ”A problem in optimal search and stop”, Operations Research 17, 984-992.

ross70 [199] Ross,S.M. [1970]: ”Applied probability models with optimization applications”, Holden-Day, San Francisco.

ross74 [200] Ross,S.M. [1974]: ”Dynamic programming and gambling models”, Advances in Applied Probability 6, 593-606.

ross83 [201] Ross,S.M. [1983]: ”Introduction to stochastic dynamic programming”, Academic Press, New York.

rot [202] Rothblum,U.G. [1979]: ”Iterated successive approximation for sequential decision processes”, in J.W.B. van Overhagen and H.C.Tijms (eds.), ”Stochastic control and optimization”, Free University, Amsterdam, 30-32.

sca [203] Scarf,H. [1960]: ”The optimality of (s, S) polcies in the dynamic inventory problem”, Chapter 13 in: K.J.Arrow, S.Karlin and P.Suppes (eds.), ”Mathematical methods in the social sciences”, Stanford University Press, Stanford.

sche [204] Schellhaas,H. [1974]: ”Zur extrapolation in Markoffschen Entscheidungsmodellen mit Diskontierung”, Zeitschrift für Operations Research 18, 91-104.

schm [205] Schmitz,N. [1985]: ”How good is Howard’s policy improvement algorithm?”, Zeitschrift fur Operations Research 29, 315-316.

schr [206] Schrage,L. [1968]: ”A proof of the optimality of the shortest remaining processing time discipline”, Operations Research 16, 687-690.

schw65 [207] Schweitzer,P.J. [1965]: ”Perturbation theory and Markovian decision processes”, Ph.D. dissertation, M.I.T., Operations Research Center Report 15.

schw68 [208] Schweitzer,P.J. [1968]: ”Perturbation theory and finite Markov chains” Journal of Applied Probability 5, 401-413. schw71a [209] Schweitzer,P.J. [1971a]: ”Multiple policy improvements in undis-

counted Markov renewal programming”, Operations Research 19. 784-793.

schw71b [210] Schweitzer,P.J. [1971b]: ”Iterative solution of the functional equations of undiscounted Markov renewal programming”, Journal of Mathematical Analysis and Applications 34, 495-501.

schw84 [211] Schweitzer,P.J. [1984]: ”A value-iteration scheme for undiscounted multichain Markov renewal programs”, ZOR - Zeitschrift für Operations Research 28, 143-152.

schw85 [212] Schweitzer,P.J. [1985]: ”The variational calculus and approximations in policy space for Markov decision processes”, Journal of Mathematical Analysis and Applications 110, 568-582.

schw87 [213] Schweitzer,P.J. [1987]: ”A Brouwer fixed-point mapping approach to communicating Markov decision processes”, Journal of Mathematical Analysis and Applications 123, 117-130.

schw91 [214] Schweitzer,P.J. [1991]: Block-scaling of value-iteration for discounted Markov renewal programming”, Annals of Operations Research 29, 603-630.

schw77 [215] Schweitzer,P.J. and A.Federgruen [1977]: ”The asymptotic behavior of value iteration in Markov decision problems”, Mathematics of Operations Research 2, 360-381.

schw78a [216] Schweitzer,P.J. and A.Federgruen [1978a]: ”Foolproof convergence in multichain policy iteration”, Journal of Mathematical Analysis and Applications 64, 360-368.

schw78b [217] Schweitzer,P.J. and A.Federgruen [1978b]: ”The functional equations of undiscounted Markov renewal programming”, Mathematics of Operations Research 3, 308-321.

schw79 [218] Schweitzer,P.J. and A.Federgruen [1979]: ”Geometric convergence of value iteration in multichain Markov decision problems”, Advances of Applied Probabilty 11, 188-217.

sen99 [219] Sennott,L.I. [1999]: ”Stochastic dynamic programming and the control of queueing systems”, Wiley, New York. ser [220] Sernik,E.L. and S.I.Markus [1991]: ”On the computation of the opti-

mal cost function for discrete time Markov models with partial observations”, Annals of Operations Research 29, 471-512.

sha [221] Shapiro,J.F. [1975]: ”Brouwer’s fixed point theorem and finite state space Markovian decision theory”, Journal of Mathematical Analysis and Applications 49, 710-712.

sh [222] Shapley,L.S. [1953]: ”Stochastic games”, Proceedings of the National Academy of Sciences, 1095-1100.

she [223] Sherif,Y.S. and M.L.Smith [1981]: ”Optimal maintenance policies for systems subject to failure - A review”, Naval Research Logistics Quarterly 28, 47-74.

sla [224] Sladky,K. [1974]: ”On the set of optimal controls for Markov chains with rewards”, Kybernatika 10, 350-367.

sma66 [225] Smallwood,R.D. [1966]: ”Optimum policy regions for Markov processes with discounting”, Operations Research 14, 658-669.

sma73 [226] Smallwood,R.D. and E.Sondik [1973]: ”The optimal control of partially observable Markov processes over a finite horizon”, Operations Research 21, 1071-1088.

smi [227] Smith,D.R. [1978]: ”Optimal repairman allocation - asymptotic results”, Management Science 24, 665-674.

so81 [228] Sobel,M.J. [1981], ”Myopic solutions of Markov decision processes and stochastic games”, Operations Research 29, 995-1009.

so85 [229] Sobel,M.J. [1985]: ”Maximal mean/standard deviation ratio in an undiscounted MDP”, OR Letters 4, 157-159.

so94 [230] Sobel,M.J. [1994]: ”Mean-variance trade-offs in an undiscounted MDP”, Operations Research 42, 175-183.

sondik [231] Sondik,E. [1978]: ”The optimal control of partially observable Markov processes over the infinite horizon: discounted costs”, Operations Research 26, 282-304.

sonin [232] Sonin, I.M. [1999]: The elimination algorithm for the problem of optimal stopping”, Mathematical Methods of Operations Research 49, 111-124. spr [233] Spreen,D. [1981]: ”A further anti-cycling rule in multi-chain policy

iteration for undiscounted Markov renewal programs”, Zeitschrift für Operations Research 25, 225-234.

st [234] Stein,J. [1988]: ”On efficiency of linear programming applied to discounted Markovian decision problems”, OR Spektrum 10, 153-160.

stid85 [235] Stidham,S.S. Jr. [1985]: ”Optimal control of admission to a queueing system”, IEEE Transactions on Automatic Control AC-30, 705-713.

stid93 [236] Stidham,S.S. Jr. and R.R.Weber [1993]: ”A survey of Markov decision models for control of networks of queues”, Queueing Systems 13, 291-314.

stoer [237] Stoer,J. and R.Bulirsch [1980]: ”Introduction to numerical analysis”, Springer-Verlag, New York.

str [238] Strauch,R. and A.F.Veinott Jr. [1966]: ”A property of sequential control processes”, Report, Rand McNally, Chicago.

sun [239] Sun,M. [1993]: ”Revised simplex algorithm for finite Markov decision processes”, Journal of Optimization Theory and Applications 79, 405-413.

th81 [240] Thomas,L.C. [1981]: ”Second order bounds for Markov decision processes”, Journal of Mathematical Analysis and Applications 80, 294-297.

th83 [241] Thomas,L.C. [1983]: ”Constrained Markov decision processes as multiobjective problems”, in: ”Multi-objective decision making”, Academic Press, 77-94.

ty [242] Tijms,H.C. [1986]: ”Stochastic modelling and analysis: a computational approach”, Wiley, Chichester.

ts86 [243] Tsitsiklis,J.N. [1986]: ”A lemma on the multi-armed bandit problem”, IEEE Transactions on Automatic Control 31, 576-577.

ts93 [244] Tsitsiklis,J.N. [1993]: ”A short proof of the Gittins index theorem”, Annals of Applied Probability 4, 194-199.

duyn [245] Van der Duyn Schouten,F.A. and S.G.Vanneste [1990]: ”Analysis and computation of (n, N)-strategies for maintenance of a two-component system”, European Journal of Operations Research 48, 260-274. wal80 [246] Van der Wal,J. [1980]: ”The method of value oriented successive ap-

proximations for the average reward Markov decision processes”, OR Spektrum 1, 233-242.

wal81 [247] Van der Wal,J. [1981]: ”Stochastic dynamic programming”, Mathematical Centre Tract 139, Mathematical Centre, Amsterdam.

hee78 [248] Van Hee, K.M. [1978]: ”Markov strategies in dynamic programming”, Mathematics of Operations Research 3, 191-201.

hee [249] Van Hee,K.M., A.Hordijk and J. van der Wal [1977]: ”Successive approximations for convergent dynamic programming”, in: H.C.Tijms and J.Wessels (eds.), Markov decision theory, Mathematical Centre Tract no. 93, Mathematical Centre, Amsterdam, 183-211.

nunen76a [250] Van Nunen,J.A.E.E. [1976a]: ”A set of successive approximation method for discounted Markovian decision problems”, Zeitschrift für Operations Research 20, 203-208.

nunen76b [251] Van Nunen,J.A.E.E. [1976b]: ”Contracting Markov decision processes”, Mathematical Centre Tract 71, Mathematical Centre, Amsterdam.

nunen76c [252] Van Nunen,J.A.E.E. [1976c]: ”Improved successive approximation methods for discounted Markovian decision processes”, in: A.Prekopa (ed.), ”Progress in Operations Research”, North Holland, Amsterdam, 667-682.

nunen76 [253] Van Nunen,J.A.E.E. and J.Wessels [1976]: ”A principle for generating optimization procedures for discounted Markov decision processes”, Colloquia Mathematica Societatis Bolyai Janos, Vol. 12, North Holland, Amsterdam, 683-695.

nunen77 [254] Van Nunen,J.A.E.E. and J.Wessels [1977]: ”The generation of successive approximations for Markov decision processes using stopping times”, in: ”Markov decision theory”, H.Tijms and J.Wessels (eds.), Mathematical Centre Tract 93, Mathematical Centre, Amsterdam, 25-37.

var [255] Varaiya,P.P., J.C.Walrand and C.Buyukkoc [1985]: ”Extensions of the multi- armed bandit problem: the discounted case”, IEEE Transactions on Automatic Control 30, 426-439. vei66a [256] Veinott,A.F.Jr. [1966a]: ”On the optimality of (s, S) inventory poli-

cies: new condition and a new proof”, SIAM Journal on Applied Mathematics 14, 1067-1083.

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

vei69 [258] Veinott,A.F. Jr. [1969]: ”Discrete dynamic programming with sensitive discount optimality criteria”, Annals of Mathematical Statistics 40, 1635-1660.

vei74 [259] Veinott,A.F. Jr. [1974]: ”Markov decision chains”, in: G.B.Dantzig and B.C.Eaves (eds.), ”Studies in Optimization”, Studies in Mathematics, Volume 10, The Mathematical Association of America, 124-159.

ver [260] Vergin,R.C. and M.Scribian [1977]: ”Maintenance scheduling for multicomponent equipment”, AIIE Transactions 9, 297-305.

vrieze87 [261] Vrieze,O.J. [1987]: ”Stochastic games with finite state and action spaces”, CWI Tract 33, Centre for Mathematics and Computer Science, Amsterdam.

wak92 [262] Wakuta,K. [1992]: ”Optimal stationary policies in the vector-valued Markov decision process”, Stochastic Processes and its Applications 42, 149-156.

wak95 [263] Wakuta,K. [1995]: ”Vector-valued Markov decision processes and the systems of linear inequalities ”, Stochastic Processes and its Applications 56, 159-169.

wak96 [264] Wakuta,K. [1996]: ”A new class of policies in vector-valued Markov decision processes”, Journal of Mathematical Analysis and Applications 202, 623-628.

wak99 [265] Wakuta,K. [1999]: ”A note on the structure of value spaces in vectorvalued Markov decision processes”, Mathematical Methods of Operations Research 49, 77-86.

wal [266] Walrand,J. [1988]: ”An introduction to queueing networks”, Prentice-Hall, Englewood Cliffs, New Jersey.

web82 [267] Weber,R.R. [1982]: ”Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. web92 [268] Weber,R.R. [1992]: ”On the Gittins index for multi-armed bandits”,

Annals of Applied Probabitily 2, 1024-1033.

web87 [269] Weber,R.R. and S.S.Stidham Jr. [1987]: ”Optimal control of services rates in networks of queues”, Advances in Applied Probability 19, 202-218.

wei82 [270] Weiss,G. [1982]: ”Multiserver stochastic scheduling”, in: Dempster,M.A.H,, J.K.Lenstra and A.H.G. Rinnooy Kan (eds.), ”Deterministic and stochastic scheduling”, Reidel, Dordrecht, Holland, 157-179.

wei88 [271] Weiss,G. [1988]: ”Branching bandit processes”, Probability in the Engineering and Information Sciences 2, 269-278.

wes77 [272] Wessels,J. [1977]: ”Stopping times and Markov programming”, in: ”Transactions of the 7th Prague conference on information theory, statistical decision functions and random processes, Academia, Prague, 575-585.

wes75 [273] Wessels,J. and J.A.E.E. Van Nunen [1975]: ”Discounted semi-Markov decision processes: linear programming and policy iteration”, Statistica Neerlandica 29, 1-7.

whi76 [274] White,C.C. III [1976]: ”Procedures for the solution of a finite-horizon, partially observed, semi-Markov optimization problem”, Operations Research 24, 348-358.

whi91 [275] White,C.C. III [1991]: ”A survey of solution techniques for the partially observed Markov decision process”, Annals of Operations Research 33, 215-230.

whi89 [276] White,C.C. III and W.T.Scherer [1989]: ”Solution procedures for partially observed Markov decision processes”, Operations Research 37, 791-797.

whi94 [277] White,C.C. III and W.T.Scherer [1994]: ”Finite-memory suboptimal design for partially observed Markov decision processes”, Operations Research 42, 439-455.

white63 [278] White,D.J. [1963]: ”Dynamic programming, Markov chains, and the method of successive approximations”, Journal of Mathematical Analysis and Applications 6, 373-376. white78 [279] White,D.J. [1978]: ”Elimination of non-optimal actions in Markov

decision processes”, in: M.L.Puterman (ed.) Dynanmic programming and its applications, Academic Press, New York, 131-160.

white82 [280] White,D.J. [1982]: ”Multi-objective infinite-horizon discounted Markov decision processes”, Journal of Mathematical Analysis and Applications 89, 639-647.

white85 [281] White,D.J. [1985]: ”Real applications of Markov decision theory”, Interfaces 15:6, 73-83.

white881 [282] White,D.J. [1988]: ”Further real applications of Markov decision theory”, Interfaces 18:5, 55-61.

white882 [283] White,D.J. [1988]: ”Mean, variance and probabilistic criteria in finite Markov decision processes: a review”, Journal of Optimization Theory and Applications 56, 1-30.

white92 [284] White,D.J. [1992]: ”Computational approaches to variance-penalized Markov decision processes”, OR Spektrum 14, 79-83.

white931 [285] White,D.J. [1993]: ”A survey of applications of Markov decision processes”, Journal of the Operational Research Society 44, 1073-1096.

white932 [286] White,D.J. [1993]: ”Markov decision processes”, Wiley, Chichester.

white94 [287] White,D.J. [1994]: ”A mathematical programming approach to a problem in variance penalised Markov decision processes”, OR Spektrum 15, 225-230.

white95 [288] White,D.J. [1995]: ”A superharmonic approach to solving infinite horizon partially observable Markov decision problems”, Mathematical Methods of Operations Research 41, 71-88.

whittle80 [289] Whittle,P. [1980]: ”Multi-armed bandits and the Gittins index”, Journal of the Royal Statistical Society, Series B 42, 143-149.

whittle82a [290] Whittle,P. [1982]: ”Optimization over time; dynamic programming and stochastic control”, Volume I, Wiley, New York.

whittle82b [291] Whittle,P. [1982]: ”Optimization over time; dynamic programming and stochastic control”, Volume II, Wiley, New York. yas [292] Yasuda,M. [1988]: ”The optimal value of Markov stopping problems

with one-step look ahead policy”, Journal of Applied Probability 25, 544-552.

zhe [293] Zheng,Y.-S. and A.Federgruen [1991]: ”Finding optimal (s, S)-policies is about as simple as evaluating a single policy”, Operations Research 39, 654-665.