Dynamic Programming

and Markov Processes

Dynamic Programming
and Markov Processes

RONALD A. HOWARD

Assistant Professor of Electrical Engineering

Massachusetts Institute of Technology

Published jointly by

The Technology Press of

The Massachusetts Institute of Technology
and
John Wiley & Sons, Inc., New York : London
 Copyright © 1960
by
The Massachusetts Institute of Technology

All Rights Reserved

This book or any part thereof must not

be veproduced in any form without the
written permission of the publisher.

Library of Congress Catalog Card Number: 60-11030

Printed in the United States of America
Preface

This monograph is the outgrowth of an Sc.D. thesis submitted to

the Department of Electrical Engineering, M.I.T., in June, 1958. It
contains most of the results of that document, subsequent extensions,
and sufficient introductory material to afford the interested technical
reader a complete understanding of the subject matter.
The monograph was stimulated by widespread interest in dynamic
programming as a method for the solution of sequential problems.
This material has been used as part of a graduate course in systems
engineering and operations research offered in the Electrical Engineering
Department of M.I.T. Asa result, the present text emphasizes above
all else clarity of presentation at the graduate level. It is hoped that
it will find use both as collateral reading in graduate and advanced
undergraduate courses in operations research, and as a reference for
professionals whoare interested in the Markovprocess as a system model.
The thesis from which this work evolved could not have been
written without the advice and encouragement of Professors Philip
M. Morse and George E. Kimball. Professor Morse aroused myinterest
in this area; Professor Kimball provided countless helpful suggestions
that guided my thinking on basic problems. Conversations with Pro-
fessors Samuel J. Mason and Bernard Widrow and with Dr. Jerome
D. Herniter were also extremely profitable.
The final text was carefully reviewed by Dr. Robert L. Barringer,
to whom I owe great appreciation. He and his colleagues at the
Operations Research Group of Arthur D. Little, Inc., have continually
offered sympathy and encouragement.
v
vt PREFACE
This work was done in part at the Massachusetts Institute of Tech-
nology Computation Center, Cambridge, Massachusetts, and was
supported in part by the Research Laboratory of Electronics.
RONALD A. HOWARD
Cambridge, Massachusetts
February, 1960
Contents

PREFACE
INTRODUCTION
CHAPTER 1 Markov Processes
The Toymaker Example—State Probabilities
The z-Transformation
z-Transform Analysis of Markov Processes
Transient, Multichain, and Periodic Behavior
CHAPTER 2 Markov Processes with Rewards
Solution by Recurrence Relation
The Toymaker Example
z-Transform Analysis of the Markov Process with Rewards
Asymptotic Behavior
CHAPTER 3 The Solution of the Sequential Decision Process by
Value Iteration 26
Introduction of Alternatives 26
The Toymaker’s Problem Solved by Value Iteration 28
Evaluation of the Value-Iteration Approach 30
CHAPTER 4 The Policy-Iteration Method for the Solution of Sequential
Decision Processes 32
The Value-Determination Operation 34
The Policy-Improvement Routine 37
The Iteration Cycle 38
The Toymaker’s Problem 39
A Proof of the Properties of the Policy-Iteration Method 42
vit
vite CONTENTS
CHAPTER 5 Use of the Policy-Iteration Method in Problems of
Taxicab Operation, Baseball, and Automobile Replace-
ment
An Example—Taxicab Operation 44
A Baseball Problem 49
The Replacement Problem 54
CHAPTER 6 The Policy-Iteration Method for Multiple-Chain Processes 60
The Value-Determination Operation 61
The Policy-Improvement Routine 63
A Multichain Example 65
Properties of the Iteration Cycle 69
CHAPTER 7 The Sequential Decision Process with Discounting 76
The Sequential Decision Process with Discounting Solved
by Value Iteration 79
The Value-Determination Operation 81
The Policy-Improvement Routine 83
An Example 84
Proof of the Properties of the Iteration Cycle 86
The Sensitivity of the Optimal Policy to the Discount
Factor 87
The Automobile Problem with Discounting 89
Summary 91
CHAPTER 8 The Continuous-Time Decision Process 92
The Continuous-Time Markov Process 92
The Solution of Continuous-Time Markov Processes by
Laplace Transformation 94
The Continuous-Time Markov Process with Rewards 99
The Continuous-Time Decision Problem 104
The Value-Determination Operation 106
The Policy-Improvement Routine 107
Completely Ergodic Processes 109
The Foreman’s Dilemma 111
Computational Considerations 112
The Continuous-Time Decision Process with Discounting 114
Policy Improvement 116
An Example 119
Comparison with Discrete-Time Case 120
CHAPTER 9 Conclusion 123
APPENDIX: The Relationship of Transient to Recurrent Behavior 127
REFERENCES 133
INDEX 135
Introduction

The systems engineer or operations researcher is often faced with

devising models for operational systems. The systems usually contain
both probabilistic and decision-making features, so that we should
expect the resultant model to be quite complex and analytically intrac-
table. This has indeed been the case for the majority of models that
have been proposed. The exposition of dynamic programming by
Richard Bellman! gave hope to those engaged in the analysis of complex
systems, but this hope was diminished by the realization that more
problems could be formulated by this technique than could besolved.
Schemes that seemed quite reasonable often ran into computational
difficulties that were not easily circumvented.
The intent of this work is to provide an analytic structure for a
decision-making system that is at the same time both general enough
to be descriptive and yet computationally feasible. It is based on the
Markov process as a system model, and uses an iterative technique
similar to dynamic programmingas its optimization method.
We begin with a discussion of discrete-time Markov processes in
Chapter 1 and then add generalizations of the model as we progress.
These generalizations include the addition of economic rewards in
Chapter 2 and the introduction of the decision process in Chapter3.
The policy-iteration method for the solution of decision processes
with simple probabilistic structures is discussed in Chapter 4 and then
examples are presented in Chapter 5. Chapter 6 introduces the case
of more complicated probabilistic structures, while Chapter 7 presents
the extension of the model to the case where the discounting of future
1
2 INTRODUCTION

rewards is important. Chapter 8 generalizes all the preceding chapters

to continuous-time rather than discrete-time Markov processes. Finally,
Chapter g contains a few concluding remarks.
It is unfortunate that the nature of the work prevents discussion of
the linear programming formulation of the policy-optimization scheme,
but this very interesting viewpoint will have to be postponed to another
time. Readers who are familiar with linear programming will in any
event be able to see familiar structures in the linear forms with which
we deal.
Markov Processes

A Markovprocess is a mathematical model that is useful in the study

of complex systems. The basic concepts of the Markov process are
those of “‘state’’ of a system and state “‘transition.’’ We say that a
system occupies a state when it is completely described by the values
of variables that define the state. A system makes state transitions
when its describing variables change from the values specified for one
state to those specified for another.
A graphic example of a Markov process is presented by a frog in a
lily pond. As time goes by, the frog jumpsfrom onelily pad to another
according to his whim of the moment. The state of the system is the
number of the pad currently occupied by the frog; the state transition
is of course his leap. If the numberoflily padsis finite, then we have a
finite-state process. All our future remarks will be confined to such a
process.
If we focus our attention on the state transitions of the system and
merely index the transitions in time, then we may profitably think
of the system as a discrete-time process. If the time between transi-
tions is a random variable that is of interest, then we may consider the
system to be a continuous-time process. Further discussion of this
latter case will occur in Chapter8.
To study the discrete-time process, we must specify the probabilistic
nature of the state transition. It is convenient to assume that the
time between transitions is a constant. Suppose that there are N
states in the system numbered from 1 to N. If the system is a simple
Markov process, then the probability of a transition to state 7 during
3
4 MARKOV PROCESSES

the next timeinterval, given that the system now occupiesstate 2, is a

function only of 2 and 7and not of any history of the system beforeits
arrivalinz. In other words, we may specify a set of conditional proba-
bilities #:; that a system which now occupies state 7 will occupy state
y after its next transition. Since the system must be in somestate
after its next transition,
N

> py =1
j=1
where the probability that the system will remain in 7, pi, has been
included. Since the fi; are probabilities,
O< fy <1

The Toymaker Example—State Probabilities

A very simple example of a discrete-time Markov processof the type
we have defined can be thought of as the toymaker’s process. The
toymakeris involved in the novelty toy business. He maybein either
of two states. Heisin the first state if the toy he is currently producing
has found great favor with the public. Heis in the secondstateif his
toy is out of favor. Let us suppose that when heis in state 1 thereis
50 per cent chance of his remaining in state 1 at the end of the following
week and, consequently, a 50 per cent chance of an unfortunate tran-
sition to state 2. Whenheis in state 2, he experiments with new toys,
and he mayreturn to state 1 after a week with probability 2 or remain
unprofitable in state 2 with probability 3. Thus fii = 4, pie =}
pei = %, fog = 2. In matrix form we have

P = [py] = F25 :
A corresponding transition diagram of the system showing the states
and transition probabilities in graphical form is

4
2
A 3
2 5
2
5

The transition matrix P is thus a complete description of the Markov

process. The rows of this matrix sum to 1, and it is composed of non-
negative elements that are not greater than 1; such a matrix is called a
 THE TOYMAKER EXAMPLE—STATE PROBABILITIES 3

stochastic matrix. We make use of this matrix to answerall questions

about the process. We may wish to know,for example, the probability
that the toymakerwill be in state 1 after » weeks if we know heis in
state 1 at the beginning of the m-week period. To answerthis and other
questions, we define a state probability 7;:(), the probability that the
system will occupy state 7 after m transitions if its state at n = 0 Is
known. It follows that

>ml (1.1)

) = >(n\py n= 0,1,2,-> (1.2)

If we define a row vector of state probabilities x(m) with components
m(”), then
n(n + 1) = x(n)P n = 0,1, 2,--- (1.3)
Since by recursion
m(1) = (0)P
m(2) = 2(1)P = x(0)P?
7(3) = 1(2)P = 7(0)P2
in general,
(nm) = 7(0)P” n = 0,1, 2,--- (1.4)
Thus it is possible to find the probability that the system occupies
each of its states after m moves, x(m), by postmultiplying the initial-
state probability vector 2(0) by the mth powerof the transition matrix
P.
Let us illustrate these relations by applying them to the toymaking
process. If the toymaker starts with a successful toy, then 71(0) = 1
and 72(0) = 0, so that x(0) = [1 0]. Therefore, from Eq. 1.3,

m(l) = mR =(1 oF F
1

and
m1) =[2 3]
After one week, the toymakeris equally likely to be successful or un-
successful. After two weeks,

m(2) = n(1)P = [3 3] [F | —

and
m(2) =[z0 20
so that the toymakeris slightly more likely to be unsuccessful.
6 MARKOV PROCESSES

After three weeks, m(3) = 2(2)P = [#55 330], and the probability
of occupying each state is little changed from the values after two
weeks. Note that since
p3 — fe
g9 111
4
lil 139
250 2950

m(3) could have been obtained directly from 2(3) = 2(0)P3.

An interesting tendency appears if we calculate m;(m) as a function of
m aS Shown in Table 1.1.

Table 1.1. SUCCESSIVE STATE PROBABILITIES OF TOYMAKER STARTING WITH

A SUCCESSFUL Toy
n= 0 1 2 3 4 5
y(n) 1 0.5 0.45 0.445 0.4445 0.44445
t9(n) 0 0.5 0.55 0.555 0.5555 0.55555

It appears as if mi(m) is approaching $ and z2(m) is approaching 3

as nm becomesvery large. If the toymaker starts with an unsuccessful
toy, so that 721(0) = 0, x2(0) = 1, then the table for z;(m) becomes
Table 1.2.

Table 1.2. SUCCESSIVE STATE PROBABILITIES OF TOYMAKER STARTING

WITHOUT A SUCCESSFUL TOY
n= 0 1 2 3 4 5
4(n) 0 0.4 0.44 0.444 0.4444 0.44444
t9(n) 1 0.6 0.56 0.556 0.5556 0.55556
For this case, mi(”) again appears to approach § for large n, while
m2(n) approaches 3. The state-occupancy probabilities thus appear to
be independent of the starting state of the system if the number of
state transitions is large. Many Markovprocesses exhibit this property.
Weshall designate as a completely ergodic process any Markov process
whoselimiting state probability distribution is independentof starting
conditions. We shall investigate in a later discussion those Markov
processes whose state-occupancy probabilities for large numbers of
transitions are dependent upon thestarting state of the system.
For completely ergodic Markov processes, we may define a quantity
7; aS the probability that the system occupies the zth state after a large
number of moves. The row vector* x with components 7; is thus the
limit as approachesinfinity of m(m); it is called the vector of limiting
* x(n) and 7 are the only row vectors that we shall consider in our work; other
vectors will be column vectors.
 TITHE z-TRANSFORMATION 7

or absolute state probabilities. It follows from Eq. 1.3 that the vector
m™ must obey the equation
m= rP (1.5)
and, of course, the sum of the components of must be 1.

> mm = | (1.6)

We may use Eqs. 1.5 and 1.6 to find the limiting state probabilities
for any process. For the toymaker example, Eq. 1.5 yields
2

3
Tt2 = 41 + Bie

whereas Eq. 1.6 becomes 71 + m2 = 1.

The three equations for the two unknowns7and m2 have the unique
solution ™1 = $, mz = 3. These are, of course, the same values for
the limiting state probabilities that we inferred from ourtablesof 7;(7).
In many applications the limiting state probabilities are the only
quantities of interest. It may be sufficient to know, for example, that
our toymakeris fortunate enough to have a successful toy $ of the time
and is unfortunate 3 of the time. The difficulty involved in finding
the limiting state probabilities is precisely that of solving a set of N
linear simultaneous equations. We must remember, however, that
the quantities 7; are a sufficient description of the process only if enough
transitions have occurred for the memory of starting position to be
lost. In the following section, we shall gain more insight into the
behavior of the process during the transient period when the state
probabilities are approaching their limiting values.

The z-Transformation

For the study of transient behavior and for theoretical convenience,

it is useful to study the Markov process from the point of view of the
generating function or, as we shall call it, the z-transform. Consider
a time function f(m) that takes on arbitrary values /(0), f(1), f(2), and
so on, at nonnegative, discrete, integrally spaced points of time and
that is zero for negative time. Sucha time function is shown in Fig.1.1.
For time functions that do not increase in magnitude with m faster
than a geometric sequence, it is possible to define a z-transform /(z)
such that

fe) = > flan

0
(1.7)
8 MARKOV PROCESSES

¢ f(1)

@ f(0)
f(2)

f(3)

0 1 2 3 n
Fig. 1.1. An arbitrary discrete-time function.

The relationship between /f(m) and its transform f(z) is unique; each
time function has only one transform, and the inverse transformation
of the transform will produce once more the original time function.
The z-transformation is useful in Markov processes because the prob-
ability transients in Markov processes are geometric sequences. The
z-transform providesus with a closed-form expressionfor such sequences.
Let us find the z-transforms of the typical time functions that we
shall soon encounter. Consider first the step function
1 n = 0,1, 2,3, ---
f(n) =
0 n<0Q0
The z-transform is

— 1
f(z) — Dfne — LT+z24+ 224
2 B84...
234 or f(z) —
T=3

For the geometric sequence f/(m) = a”, n > 0,

_ ce _ ce a 1

f(z) = 2S(na = 2,(a2) or f(z) = iow

Note that if

£2) = >. aren

n=0

then

a f(z) = S nangn-1
dz MX
and

S nanan = 2" f(z) = 24 i) ee

KX az dz\1 — az (1 — az)?
Thus we have obtained as a derived result that, if the time function we
are dealing with is f(m) = na”, its z-transform is f(z) = az/(1 — az)?.
 2-TRANSFORM ANALYSIS OF MARKOV PROCESSES 9

From these and other easily derived results, we may compile the table
of z-transforms shown as Table 1.3. In particular, note that, if a time
function f(m) with transform f(z) is shifted to the right one unit so as
to become /(z + 1), then the transform of the shifted function 1s

>fm + er = >flmemt = Pe) — FO)

The reader should become familiar with the results of Table 1.3
because they will be used extensively in examples andproofs.

Table 1.3. z-TRANSFORM PAIRS

Time Function for > 0 z-Transform

f(n) f(z
film) + fe(n) f(z) + fa(z)
hf (n) (k is a constant) kf (z)
fin — 1) zf(z)
f(n + 1) z- Lele) — f(0)]
an 1 — az
1 (unit step) 1
1-2
nan “
* (1 — az)?
n (unit ramp) i ae

anf (n) f(xz)

%-Transform Analysis of Markov Processes

Weshall now use the z-transform to analyze Markov processes. It
is possible to take the z-transform of vectors and matrices by taking
the z-transform of each component of the array. If the transform of
Eq. 1.3 is taken in this sense, and if the vector z-transform of the vector
m(n) is given the symbol II(z), then we obtain
z-1[II(z) — 2(0)] = II(z)P (1.8)
Through rearrangement we have
II(z) — 2II(z)P = x(0)
II(z)(I — zP) = x(0)
and finally
II(z) = 2(0)(I — zP)-1 (1.9)
In this expression I is the identity matrix. The transform of the
state probability vector is thus equal to the initial-state-probability
10 MARKOV PROCESSES

vector postmultiplied by the inverse of the matrix I — zP; the inverse

of I — zP will always exist. Note that the solution to all transient
problemsis contained in the matrix (I — zP)-1. To obtain the complete
solution to any transient problem,all we must dois to weight the rows
of (I — zP)—! by the initial state probabilities, sum, and then take the
inverse transform of each element in the result.
Let us investigate the toymaker’s problem by z-transformation.
For this case
141
p=(75 OS3]
so that
_ fl — dz —z
a= oe
and
1 — 22 dz
a , (1 — z)(1— oz) (1 — 2)(1 — Yoz)
— zP)1=
22 1 — kz
(1 — 2)(1— oz) (1 — 2)(1 — Yoz)
Each element of (I — zP)—! is a function of z with a factorable de-
nominator (1 — z)(1 — 76z). By partial-fraction expansion? we can
express each element as the sum of two terms: one with denominator
1 — z and one with denominator 1 — yz. The (I — zP)-! matrix
now becomes
$3 _
a a
_ zp)-1 =
(r— ®) 49 +
_49 59 49
l1—z 1-7, 1—z 1- 2

a-pai- tft },_1

“tals gs] *i—wel-4s i4
Let the matrix H() be the inverse transform of (I — zP)—! on an
element-by-element basis. Then from Table 1.3, we see that

win) = [Fa] + oe]

9 9

and finally by taking the inverse transform of Eq. 1.9

(nm) = 1(0)H(x) (1.10)
 2-TRANSFORM ANALYSIS OF MARKOV PROCESSES 11

By comparison with Eq. 1.4 we see that H(m) = P”, and that we
have found a convenient way to calculate the mth powerof the tran-
sition-probability matrix in closed form. The state-probability vector
at time ” can thus be found by postmultiplying the initial-state-prob-
ability vector by the response matrix H(m). The zjth element of the
matrix H(n) represents the probability that the system will occupy
state 7 at time 7, given that it occupied state z at time = 0. If the
toymaker starts in the successful state 1, then x(0) =[1 0] and
n(n) =[$ 3] + (Fo)"[3 —$] or wi(m) = $ + $(z0)”, m2(m) = § — 3 (Fo).
Note that the expressions for 71(m) and me(m) are exact analytic
representations for the state probabilities found in Table 1.1 by matrix
multiplication. Note further that as m becomes very large 71(m) tends
to $ and ze(m) tends to 3; they approachthelimiting state probabilities
of the process.
If the toymakerstarts in state 2, then x(0) = [0 1], x(n) =[$ 3
+ (¥o)"[-—$ $], so that mi(m) = § — $(zo)” and me(m) = 3 + $(z6)”.
We have now obtained analytic forms for the data in Table 1.2. Once
more wesee that for large m the state probabilities becomethe limiting
state probabilities of the process.
It is possible to make some general statements about the form that
H(n) maytake. First it will always have among its component matrices
at least one that is a stochastic matrix and that arises from a term of
(I — zP)-1 of the form 1/(1 — z). This statement is equivalent to
saying that the determinant of I — zP vanishes for z = 1 or that a
stochastic matrix always has at least one characteristic value equalto 1.
If the process is completely ergodic, then there will be exactly one
stochastic matrix in H(z). Furthermore, the rows of this matrix will
be identical and will each be the limiting-state-probability vector of the
process. Wecall this portion of H(m) the steady-state portion and
give it the symbolS since it is not a function of 1.
The remainder of the terms of H(z) represent the transient behavior
of the process. These terms are matrices multiplied by coefficients of
the form «”, na", m2a", and soon. Naturally, |«| must not be greater
than 1, for if any a were greater than 1, that component of probability
would grow without bound, a situation that is clearly impossible.
The transient matrices represent the decreasing geometric sequences of
probability components that are typical of Markov processes. The
transient component of H(m) may be given the symbol T(m) sinceit is
a function of m. Since for completely ergodic processes |«| < 1 forall
a, the transient component T(m) vanishes as becomes very large.
The matrices that compose T(z) are also of interest because they sum
to zero across each row. The transient components must sum to zero
12 MARKOV PROCESSES

since they may be considered as perturbations applied to the limiting

state probabilities. Matrices that sum to zero acrossall rowsare called
differential matrices. Finally, for a completely ergodic process,
H(n) = S + T(n) (1.11)
whereS is a Stochastic matrix all of whose rowsare equal to the limiting
state-probability vector and where T(m) is the sum of a numberof
differential matrices with geometric coefficients that tend to zero as n
becomesvery large.

Transient, Multichain, and Periodic Behavior

To gain further insight into the Markov process, let us use the
z-transform approachto analyze processesthat exhibit typical behavior
patterns. In the toymaker’s problem, both states had a finite proba-
bility of occupancy after a large numberof transitions. It is possible
even in a completely ergodic process for some of the states to have a
limiting state probability of zero. Such states are called transient
states because we are certain that they will not be occupied after a
long time. A two-state problem with a transient state is described by
p_ (i 3
=|o il
with transition diagram

i
4

If the system is in state 1, it has probability + of making a transi-

tion to state 2. However, if a transition to 2 occurs, then the system
will remain in 2 for all future time. State 1 is a transient state;
state 2 is a trapping state (a state 2 for which py = 1).
By applying the z-transform analysis, we find

a -2) =| 1 — 32
0
‘ —iz
1-2
"|
and
1-—2z Lz
a By (1 — z)(1— gz) (1 — 2)(1 — 32)
— gP)-i =

0 1 — 32
@-)i-% 7-70-®
 TRANSIENT, MULTICHAIN, AND PERIODIC BEHAVIOR 13

1 fo 1 1 fl -1
(I
_
2B)"
—1 _
7 lo | TT slo 0
ee

Thus

am) = (5 + @\y
If the system is started in state 1 so that x(0) = [1 0], then z1i(m) =
(3), me(m) = 1 — (#)". If the system is started in state 2 with
x(0) = [0 1], then naturally m1(m) = 0, me(m) = 1. In either case
we see that the limiting state probability of state 1 is zero, so our
assertion that it is a transient state is correct. Of course the limiting
state probabilities could have been determined from Eqs. 1.5 and 1.6
in the mannerdescribed earlier.
A transient state need not lead the system into a trappingstate.
The system may leave a transient state and enter a set of states that
are connected by possible transitions in such a way that the system
makes jumps within this set of states indefinitely but never jumps
outside the set. Such a set of states is called a recurrent chain of the
Markov process; every Markov process must have at least one recurrent
chain. A Markov process that has only one recurrent chain must be
completely ergodic because no matter where the processis started it
will end up making jumps among the membersof the recurrent chain.
However, if a process has two or more recurrent chains, then the
completely ergodic property no longer holds, for if the system is started
in a State of one chain then it will continue to make transitions within
that chain but never to a state of another chain. In this sense, each
recurrent chain is a generalized trapping state; onceit is entered, it can
never be left. We may now think of a transient state as a state that
the system occupies before it becomes committed to oneof the recurrent
chains.
The possibility of many recurrent chainsforces us to revise our think-
ing concerning S, the steady-state component of H(m). Since the
limiting state probability distribution is now dependent on how the
system is started, the rowsof the stochastic matrix S are no longer equal.
Rather, the 7th row of S represents the limiting state probability distri-
bution that would exist if the system were started in the zth state. The
ith row of the T(m) matrix is as before the set of transient components
of the state probability if 2 1s the starting state.
Let us investigate a very simple three-state process with two recurrent
chains described by

p= |o
1 0
j
oH et ©

13 13
14 MARKOV PROCESSES

with the transition diagram

i
3

State 1 constitutes one recurrent chain; state 2 the other. Both are
trapping states, but the general behavior would be unchanged if each
were a collection of connected states. State 3 is a transient state that
may lead the system to either of the recurrent chains. To find H(n)
for this process, we first find
1—2z 0 0
(I — zP) = 0 l-2z 0
—iz —tkz 1-—ikz
and
r (1 — z)(1 — dz 7
Lees ° °
(I — 2P)-! = 0 t = on — s 0
_ —_ I

(1 — z)dz (1 — z)iz (1 — z)2

(1 — z)®(1 —32z) (1 — 2)%(1 — gz) (1 — 2)®(1 — 32) J
Thus
1 1 0 0 1 0 0 0
(I — zP)-1 = 0 1 Of + ; 0 0 0
rafts =a -3
and
i 0 0 0 0 0
H(n) = f 1 J + an 0 0 j
t $0 -} -31
= S + T(n)
If the system is started in state 1, mi(m) = 1, xo(m) = z3(n) = 0.
If the system is started in state 2, mi(m) = ma(n) = 0, x
p=
~~

—
=-,
=

|
oo
 TRANSIENT, MULTICHAIN, AND PERIODIC BEHAVIOR 15

the system is started in state 3, m1(m) = mo(m) = 3[1 — (4)”], x(n) =

(3)”.
We may summarize by saying that if the system is started in state 1
or state 2 it will remain in its starting state indefinitely. If it is started
in state 3, it will be after many movesin state 1 with probability 4 and
in state 2 with probability 4. These results may be seen directly
from the rows of S which are, after all, the limiting state probability
distributions for each starting condition.
The multichain Markovprocessis thus treated with ease by z-trans-
formation methods. There is one other case that requires discussion,
however, before we mayfeel at all confident of our knowledge. Thatis
the case of periodic chains. A periodic chain is a recurrent chain
with the property that if the system occupies somestate at the present
time it will be certain to occupy that samestate after f, 2p, 3p, 44,---
transitions, where # is an integer describing the periodicity of the system.
The simplest periodic system is the two-state system of period 2 with
transition matrix
0 1
P= lio
and transition diagram

aC
1

If the system is started in state 1, it will be once morein state 1 after

even numbersof transitions and in state 2 after odd numbersof transi-
tions. There is no need for analysis to understand this type of be-
havior, but let us investigate the results obtained by the transformation
method. We have

(I — 2P) = | 1
1 z
(1 — z)(1 + 2) (1 — z)(1 + 2)
(I — zP)-1 =

and
16 MARKOV PROCESSES

The response matrix H(z) is thus

1
1
H(n) = k + (— 14]

bolt poles
2
12

This H(z) does represent the solution to the problem because, for
example, if the system is started in state 1, mi(m) = 4[1 + (—1)”] and
to(n) = 4{1 — (—1)"]. These expressions produce the sameresults that
we Saw intuitively. However, whatis to be the interpretation placed on
Sand T(m) inthis problem? The matrix T(m) contains componentsthat
do not die away for larger n, but rather continueto oscillate indefinitely.
On the other hand, T(z) can still be considered as a perturbation to the
set of limiting state probabilities defined by S. The best interpretation
of the limiting state probabilities of S is that they represent the proba-
bility that the system will be found in each of its states at a time
chosen at random in the future. For periodic processes, the original
concept of limiting state probabilities is not relevant since we know
the state of the system at all future times. However, in manypractical
cases, the random-time interpretation introduced above is meaningful
and useful. Whenever we consider the limiting state probabilities of a
periodic Markov process, weshall use them in this sense. Incidentally,
if Eqs. 1.5 and 1.6 are used to find the limiting state probabilities, they
yield x1 = xe = 4, in agreement with our understanding.
Wehavenowinvestigated the behavior of Markovprocesses using the
mechanism of the z-transform. This particular approach is useful
because it circumvents the difficulties that arise because of multiple
characteristic values of stochastic matrices. Many otherwise elegant
discussions of Markov processes based on matrix theory are markedly
complicated bythis difficulty. The structure of the transform method
can be even more appreciated if use is made of the work that has been
done on signal-flow-graph models of Markov processes, but this is
beyond our present scope; references 3 and 4 maybeuseful.
The following chapter will begin the analysis of Markov processes
that have economic rewards associated with state transitions.
Markov Processes with Rewards

Suppose that an N-state Markov process earns 7;; dollars when it

makes a transition from state 7 to state 7. We call 7; the “‘reward”’
associated with the transition from ztoj. The set of rewards for the
process may be described by a reward matrix R with elements 74;.
The rewards need not be in dollars, they could be voltage levels, units
of production, or any other physical quantity relevant to the problem.
In most of our work, however, we shall find that economic units such as
dollars will be the pertinent interpretation.
The Markov process now generates a sequence of rewards as it
makes transitions from state to state. The reward is thus a random
variable with a probability distribution governed by the probabilistic
relations of the Markov process. Recalling our frog pond, we can
picture a game where the player receives an amount of money 7;
if the frog jumps from pad z to pad 7. As some of the ~; might
be negative, the player on occasion would have to contribute to the
pot.

Solution by Recurrence Relation

One question we might ask concerning this game is: What will be
the player’s expected winningsin the next » jumpsif the frog is now in
state z (sitting on the lily pad numbered 2)? To answer this question,
let us define v;(m) as the expected total earnings in the next transitions
if the system is now in state 7.
17
18 MARKOV PROCESSES WITH REWARDS

Some reflection on this definition allows us to write the recurrence

relation
N
vi(n) = > pulrg + vx(n — 1)] ¢ = 1,2,---,N nm =1,2,3,--- (2.1)
j=1

If the system makesa transition from 7 to 7, it will earn the amount 7,

plus the amount it expects to earn if it starts in state 7 with one move
fewer remaining. As shown in Eq.2.1, these earnings from a transition
to 7 must be weighted by the probability of such a transition, fi;, to
obtain the total expected earnings.
Notice that Eq. 2.1 may be written in the form
N N
vi(n) = > dur + > pyvj(n — 1)
j=1 j=1
1=1,2,---,N nm =1,2,3,--- (2.2)
so that if a quantity q; is defined by
N

ga => pyrg 1=1,2,---,N (2.3)

j=1

Eq. 2.1 takes the form

N
vi(n) = ge + > pyvim —1) 1 =1,2,---,-N n=1,2,3,--- (24)
j=1

The quantity g; may be interpreted as the reward to be expected in

the next transition out of state z; it will be called the expected immediate
reward for statez. In terms of the frog jumping game, g; is the amount
that the player expects to receive from the next jumpof the frogif it
is now on lily pad. Rewriting Eq. 2.1 as Eq. 2.4 shows us that it is
not necessary to specify both a P matrix and an R matrix in order to
determine the expected earnings of the system. All that is neededis a
P matrix and a q column vector with N components g;. The reduction
in data storage is significant when large problemsare to be solved on a
digital computer. In vector form, Eq. 2.4 may be written as
vin) = q + Pv(n — 1) n = 1,2, 3,--- (2.5)
where v(m) is a column vector with N components v;(m), called the
total-value vector.

The Toymaker Example

To investigate the problem of expected earningsin greater detail, let
us add a reward structure to the toymaker’s problem. Suppose that
 THE TOYMAKER EXAMPLE 19

when the toymakerhas a successful toy (the system is in state 1) and

again has a successful toy the following week (the system makes a
transition from state 1 to state 1) he earns a reward of 9 units for that
week (perhaps $900). Thus 7111s equal to 9. If the week has resulted
in a transition from unsuccessful to unsuccessful (state 2 to state 2),
then the toymakerloses 7 units or 722 = —7. Finally, if the week has
produced a change from unsuccessful to successful or from successful
to unsuccessful, the earnings are 3 units, so that r21 = 712 = 3. The
reward matrix R is thus
9 3
R=|3 7
Recalling that
0.5 0.5
P= lo 06
we can find q from Eq. 2.3:

LS
Inspection of the q vector showsthat if the toymaker has a successful
toy he expects to make 6 units in the following week; if he has no
successful toy, the expected loss for the next week is 3 units.
Suppose that the toymaker knowsthat heis going to go out of busi-
ness after » weeks. He is interested in determining the amount of
money he may expect to make in that time, depending on whetheror
not he now has a successful toy. The recurrence relations Eq. 2.4
or Eq. 2.5 may be directly applied to this problem, but a set of
boundary values v;(0) must be specified. These quantities represent
the expected return the toymaker will receive on the day he ceases
operation. If the businessis sold to anotherparty, v1(0), would be the
purchase price if the firm had a successful toy on the selling date, and
v2(0) would be the purchase price if the business were not so situated
onthat day. Arbitrarily, for computational convenience, the boundary
values v;(0) will be set equal to zero in our example.
We may now use Eq. 2.4 to prepare Table 2.1 that shows v(m) for
each state and for several values of n.

Table 2.1. TotTsaL EXPECTED REWARD FOR TOYMAKER AS A FUNCTION OF

STATE AND NUMBER OF WEEKS REMAINING
n= 0 1 2 3 4 5
v4(n) 0 6 7.5 8.55 9.555 10.5555
(n) 0 -3 2.4 — 1.44 — 0.444 0.5556
20 MARKOV PROCESSES WITH REWARDS

Thus, if the toymakeris four weeksfrom his shutdown time, he expects

to make 9.555 units in the remaining time if he now has a successful
toy andto lose 0.444 unit if he does not have one. Note that vi(m) —
ve(m) seems to be approaching 10 as m becomes large, whereas both
vi(m) — vi(n — 1) and ve(m) — ve(m — 1) seem to approach the value
1 for large ». In other words, when m is large, having a successful
| | | | | a”

lle Points for a|

Vy (n) a
10;-
oo a
Pa
a“
9 woo\asymptote of v, (n) |
aL ue \ slope = 1 _
a” —

7L a 7
we

eb
‘e
* |
= 5
> |

gSs |.
_
<4 10 units
£
= 3)
|
Go
2b yl
£ 7
us 1
vo 7
ao

of ! ! ——
: Asymptoteof v. (n) oo
—iE slope = 1 V7 |
-2 NU
2 a |
—3L
2 s a7 Points for 7
Lo Uo (n)
-4 U- ” 7
—5 | | | |
0 1 2 3 4 8 °
n (weeks remaining)

Fig. 2.1. Toymaker’s problem;total expected reward in each state as a function

of weeks remaining.

toy seems to be worth about 10 units more than having an unsuccessful

one, as farasfuture returnisconcerned. Also, for large”, an additional
week’s operation brings about 1 unit of profit on the average. The
behavior of v;(”) for large ” is even more clear when the data of Table
2.1 are plotted as Fig. 2.1. The distance between the asymptotes to
the value expressionsis 10 units, whereas the slope of each asymptoteis
 z-TRANSFORM ANALYSIS 21

1 unit. Weshall be very much interested in the asymptotic behavior

of total-earnings functions.

%-Transform Analysis of the Markov Process with Rewards

Let us analyze the Markov process with rewards by means of the

z-transformation. The z-transform of the total-value vector v(m) will
ce

be called v(z) where v(z) = > v(m)z*. Equation 2.5 may be written
n=0
as
vin + 1) = q + Pv(n) n = 0,1, 2,--- (2.6)

If we take the z-transformation of this equation, we obtain

_ 1
2z-l[v(z) — v(0)] = To7it Pv(z)

v(z) — v(0) = — q + 2Pv(z)

(I — 2P)v(z) = —— q + v(0)
or

v2) = 3 - -(I — 2P)-1q + (I — 2P)-1v(0) (2.7)

Finding the transform v(z) requires the inverse of the matrix (I — zP),
which also appeared in the solution for the state probabilities. This is
not surprising since the presence of rewards does not affect the proba-
bilistic structure of the process.
For the toymaker’s problem, v(Q) is identically zero, so that Eq. 2.7
reduces to

v(2) = 3 “ (I — 2P)-1q (2.8)

For the toymakerprocess, the inverse matrix (I — zP)—1 was previously

found to be
22 MARKOV PROCESSES WITH REWARDS

zZ &£ 3s 10 _ 10 > 5

comlt * (ratios 4
_ 9 9 + 9 + 9 9 9

Let the matrix F(m) be the inverse transform of [z/(1 — z

—
-_—_~

~~”
LH

a)
pws
|
N
|
Then

The total-value vector v(m) is then F(n)q by inverse transformation of

Eq. 2.8, and, since q = 5;

In other words,

vi(n) = m + *9[1 — (¥o)*] ve(n) = n — 4>(1 — (¥6)"] (2.9)

Wehave thus found a closed-form expression for the total expected
earnings starting in eachstate.
Equations 2.9 could be used to construct Table 2.1 or to draw Fig.2.1.
Wesee that, as » becomes very large, vi(m) takes the form n + 52,
whereas v2(m) takes the form » — 42. The asymptotic relations
is
(lo

V3() =nN+

vo(n) =n —
Cio
|p

are the equations of the asymptotes shownin Fig. 2.1. Note that, for
large n, both vi(m) and ve(m) have slope 1 and vi(m) — ve(n) = 10, as
we Saw previously. For large , the slope of v1() or ve(m) is the average
reward per transition, in this case 1. If the toymaker were many,
many weeks from shutdown, he would expect to make 1 unit of return
per week. Wecall the average reward per transition the “gain’’; in
this case the gain is 1 unit.

Asymptotic Behavior
What can be said in general about the total expected earnings of a
 ASYMPTOTIC BEHAVIOR 23

process of long duration? To answer this question, let us return to

Eq.2.7:
z
v(z) = i (I — zP)-1q + (I — zP)—1v(0) (2.7)
— 2

It was shown in Chapter 1 that the inverse transform of (I — zP)-!

assumed the form § + T(z). In this expression, S is a stochastic
matrix whose 7th row is the vector of limiting state probabilities if the
system is started in the zth state, and T(x) is a set of differential matrices
with geometrically decreasing coefficients. Weshall write this relation
in the form

(I — 2B)! = _—_S
— 2
+ F(z) (2.10)
where JF (z) is the z-transform of T(z). If we substitute Eq. 2.10 into
Eq. 2.7, we obtain
z 1
v(z) = (1 — z)? Sq + =
1 F(2)q + 1—z
Sv(0) + F(z)v(0) (2.11)
By inspection of this equation for v(z), we can identify the components
of v(x). The term [z/(1 — z)2] Sq represents a ramp of magnitude Sq.
Partial-fraction expansion showsthat the term [z/(1 — z)] 7(z)q repre-
sents a step of magnitude 7 (1)q plus geometric terms that tend to
zero as m becomesvery large. The quantity [1/(1 — z)] Sv(O) 1s a step
of magnitude Sv(0), whereas J (z)v(0) represents geometric components
that vanish when x is large. The asymptotic form that v(m) assumes
for large is thus
v(m) = nSq + JF(1)q + Sv(0) (2.12)
If a column vector g with componentsg; is defined by g = Sq, then
v(n) = ng + JF(1)q + Sv(0) (2.13)
The quantity g; is equal to the sum of the immediate rewards q;
weighted by the limiting state probabilities that result if the system is
started in the zth state, or
N

gt = > SigQj
j=l

It is also the average return per transition of the system if it is started

in the :th state and allowed to make manytransitions; we may call g¢
the gain of thezthstate. Equivalently, it is the slope of the asymptote
of v(m). Since all member states of the same recurrent chain have
identical rows in the § matrix, such states all have the same gain.
24 MARKOV PROCESSES WITH REWARDS

Tf there is only one recurrent chain in the system so thatit is completely

ergodic, then all rows of S are the same and equal to the limiting state
probability distribution for the process, z. It follows that in this case
all states have the same gain,say g, and that
N

g => mg (2.14)
+=1

The column vector J (1)q + Sv(0) represents the intercepts at n = 0

of the asymptotes of v(m). These intercepts are jointly determined by
the transient behavior of the process 7 (1)q and by the boundaryeffect
Sv(0). We shall denote by v; the asymptotic intercepts of v;(”), so
that for large n
vi(n) = nge + Vi 1=1,2,.--,N (2.15)

The column vector with components v; may be designated by v so that

v = F(1)q + Sv(0). Equations 2.15 then become

v(m) =ng+v for large n (2.16)

If the system is completely ergodic, then, of course, all g; = g, and

we maycall g the gain of the process rather than the gain of a state, so
that Eqs. 2.15 become

vi(n) = ng + v4 1=1,2,---,N for large n (2.17)

By wayof illustration for the toymaker’s problem,

a-i=[fils [2 Hl
1-213 3 1 — yozL-$ 4

= +-S8+ Fy)
so that
3 3 $1 81
s<[ ag] 7-Lae “al
Since

By assumption, v(0) = 0; then

v=7()a=[_|
 ASYMPTOTIC BEHAVIOR 25

Therefore, from Eqs. 2.15,

vin) = n + 2 ven) =n — 4 for large n
as we found before.
We have now discussed the analysis of Markov processes with
rewards. Special attention has been paid to the asymptotic behavior
of the total expected reward function, for reasons that will become
clear in later chapters.
The Solution of the
Sequential Decision Process
by Value Iteration

The discussion of Markov processes with rewards has been the means
toanend. This end is the analysis of decisions in sequential processes
that are Markovian in nature. This chapter will describe the type of
process underconsideration and will show a methodof solution based on
recurrence relations.

Introduction of Alternatives

The toymaker’s problem that we have been discussing may be de-

scribed as follows. If the toymaker is in state 1 (successful toy), he
makes transitions to state 1 and state 2 (unsuccessful toy) according
to a probability distribution [f1;] = [0.5 0.5] and earns rewards
according to the reward distribution [71;] = [9 3]. If the toymaker
is in state 2, the pertinent probability and reward distributions are
[poz] = [0.4 0.6] and [ve;] = [3 —7]. This process has been analyzed
in detail; we know how to calculate the expected earnings for any
numberof transitions before the toymakergoes out of business.
Suppose now that the toymaker has other courses of action open to
him that will change the probabilities and rewards governing the process.
For example, when the toymaker has a successful toy, he may use
advertising to decrease the chance that the toy will fall from favor.
However, because of the advertising cost, the profits to be expected
per week will generally be lower. To be specific, suppose that the
probability distribution for transitions from state 1 will be
[p13] = [0.8 0.2] when advertising is employed, and that the
26
 INTRODUCTION OF ALTERNATIVES 27

corresponding reward distribution will be [v1;] = [4 4]. The toymaker

now has twoalternatives when heis in state 1: He may use no advertis-
ing or he may advertise. We shall call these alternatives 1 and 2,
respectively. Each alternative has its associated reward and prob-
ability distributionsfor transitions out of state 1. We shall use a super-
script & to indicate the alternatives in a state. Thus, for alternative
1 in state 1, [61,1] = [0.5 0.5], [7134] = [9 3]; and for alternative 2 in
state 1, [f1;2] = [0.8 0.2], [71;7] = [4 41.
There mayalso be alternativesin state 2 of the system (the company
has an unsuccessful toy). Increased research expenditures may in-
crease the probability of obtaining a successful toy, but they will also
increase the cost of being in state 2. Under the original alternative
in state 2, which we maycall alternative 1 and interpret as a limited
research alternative, the transition probability distribution was
[pay] = [0.4 0.6], and the reward distribution was [7e;] = [3 —7].
Underthe research alternative, alternative 2, the probability and reward
distribution might be [fo;] = [0.7 0.3] and [ve;] = [1 -—19]. Thus,
for alternative 1 in state 2,

[poj4] = [0.4 0.6] [ret] = [3 —-7]

and for alternative 2 in state 2,

[pay7] = [0.7 0.3] [req7] = [1 —19]

The concept of alternative for an N-state system is presented
graphically in Fig. 3.1. In this diagram, two alternatives have been

Present state Pt Succeeding state

of system of system

t=] J=1

i=20O J=2

i=3 O J=3
I I

| |
i=NO Oj=N
Fig. 3.1. Diagram of states and alternatives.

allowed in the first state. If we pick alternative 1 (k = 1), then the

transition from state 1 to state 1 will be governed by the probability
28 THE VALUE-ITERATION METHOD

pii!, the transition from state 1 to state 2 will be governed by 412},

from 1 to 3 by #13!, and so on. The rewards associated with these
transitions are 711!, 7121, 7131, and so on. If the second alternative in
state 1 is chosen (R = 2), then pir’, pi2?, p13",° sy pin? and 711%, 7122,

7137,---, vin*, and so on, would be the pertinent probabilities and

rewards, respectively. In Fig. 3.1 we see that, if alternative 1 in state
1 is selected, we maketransitions according to thesolid lines; if alterna-
tive 2 is chosen, transitions are made according to the dashed lines.
The numberof alternatives in any state mustbe finite, but the number
of alternatives in each state may be different from the numbers in
other states.

The Toymaker’s Problem Solved by Value Iteration

The alternatives for the toymaker are presented in Table 3.1. The
quantity g:* is the expected reward from a single transition from state
N
1 under alternative k. Thus, gi* = > Dig*rag*.
j=1

Table 3.1. THE TOYMAKER’S SEQUENTIAL DECISION PROBLEM

Expected
Transition Immediate
State Alternative Probabilities Rewards Reward
a k pik pie* rk r49k qak
1 (Successful toy) 1 (No advertis- 0.5 0.5 9 3 6
ing)
2 (Advertising) 0.8 0.2 4 4 4

2 (Unsuccessful 1 (No research) 0.4 0.6 3 -7 —3

toy) 2 (Research) 0.7 0.3 1 -19 —5

Suppose that the toymaker has weeks remaining before his business
will close down. Weshall call x the numberof stages remaining in the
process. The toymaker would like to know as a function of » and his
present state what alternative he should use for the next transition
(week) in order to maximize the total earnings of his business over the
n-week period.
Weshall define d;(m) as the numberof the alternative in the 7th state
that will be used at stage n. We call d;(m) the “‘decision”’ in state z at
the mth stage. When d;(m) has been specified for all 7 and all n, a
‘policy’? has been determined. The optimal policy is the one that
maximizes total expected return for each 2 and n.
To analyze this problem, let us redefine v;(m) as the total expected
 TOYMAKER’S PROBLEM SOLVED BY VALUE ITERATION 29

return in m stages starting from state 2 1f an optimal policy is followed.

It follows that for any 1
N

vi(n + 1) = max > pij*[rij* + v;(n)] n=0,1,2,--- (3.1)

Rk j=1

Suppose that we have decided which alternatives to follow at stages n,

nm — 1,---, 1 in such a way that we have maximized v,(m) for 7 = 1, 2,
--+,.N. We are at stage » + 1 and are seeking the alternative we
should follow in the zth state in order to make vi(n +1) as large as
possible; this is dj(m + 1). If we used alternative & in the 7th state,
then our expected return for + 1 stages would be

2 Dej*[reg* + v;(n)] (3.2)

by the argument of Chapter 2. Weare seeking the alternative in the zth
state that will maximize Expression 3.2. For this alternative, v;(m + 1)
will be equal to Expression 3.2; thus we have derived Eq. 3.1,* which we
may call the value iteration equation. Equation 3.1 may be written
in terms of the expected immediate rewards from each alternative in
the form

vi(n + 1) = max jae + > puto) (3.3)

The use of the recursive relation (Eq. 3.3) will tell the toymaker
which alternative to use in each state at each stage and will also provide
him with his expected future earnings at each stage of the process.
To apply this relation, we must specify v;(0) the boundary condition
for the process. Weshall assign the value 0 to both v:(0) and v2(0),
as we did in Chapter 2. Now Eq. 3.3 will be used to solve the toy-
maker’s problem as presented in Table 3.1. The results are shown in
Table 3.2.

Table 3.2. TOYMAKER’S PROBLEM SOLVED BY VALUE ITERATION

n= 0 1 2 3 4

v1(7) 0 6 8.2 10.22 12.222

vo(n) 0 —3 —1.7 0.23 2.223

1(7) — 1 2 2 2
do(n) _— 1 2 2 2
The calculation will be illustrated by finding the alternatives and
* Equation 3.1 is the application of the “Principle of Optimality”’ of dynamic
programming to the Markovian decision process; this and other applications are
discussed by Bellman.!
30 THE VALUE-ITERATION METHOD

rewards at the first stage. Since v(0) = 0, vi(1) = maxqi*. The

k
alternative to be used in state 1 at thefirst stage is that with thelargest
expected immediate reward. Since gi! = 6 and gi? = 4, the first
alternative in state 1 is the better one to use at the first stage, and
vi(1) = 6. Similarly, ve(1) = max ge*, and, since, ge! = —3, and
k
g22 = —5, the first alternative in state 2 is the better alternative and
ve(1) = —3. Having now calculated v,(1) for all states, we may
again use Eq. 3.3 to calculate v;(2) and to determine the alternatives
to be used at the second stage. The process may be continued for as
many as we careto calculate.
Suppose that the toymaker has three weeks remaining and that heis
in state 1. Then we see from Table 3.2 that he expects to make 10.22
units of reward in this period of time, v1(3) = 10.22, and that he should
advertise during the coming week, di(3) = 1. We may similarly
interpret any other situation in which the toymaker may find himself.
Note that for = 2, 3, and 4, the second alternativein each stateis
to be preferred. This means that the toymaker is better advised to
advertise and to carry on researchin spite of the costs of these activities.
The changes produced in the transition probabilities more than make
up for the additional cost. It has been shown! that the iteration
process (Eq. 3.3) will converge on a best alternative for each state as n
becomes very large. For this problem the convergence seems to have
taken place at » = 2, and the secondalternative in each state has been
chosen. However, in many problemsit is difficult to tell when con-
vergence has been obtained.

Evaluation of the Value-Iteration Approach

The method that has just been described for the solution of the
sequential process may be called the value-iteration method because the
v(m) or ‘‘values”’ are determined iteratively. This method has some
important limitations. It must be clear to the reader that not many
enterprises or processes operate with the specter of termination so
imminent. For the most part, systems operate on an indefinite basis
with no clearly defined end point. It does not seem efficient to have
to iterate v;(m) for m = 1, 2, 3, and so forth, until we have a sufficiently
large m that termination is very remote. We would much rather have
a method that directed itself to the problem of analyzing processesof
indefinite duration, processes that will make manytransitions before
termination.
Such a technique has been developed; it will be presented in the next
chapter. Recall that, even if we were patient enough to solve the
 EVALUATION OF THE VALUE-ITERATION APPROACH 3]

long-duration process by value iteration, the convergence on the best

alternative in each state is asymptotic and difficult to measure analyti-
cally. The method to be presented circumventsthis difficulty.
Even though the value-iteration method is not particularly suited
to long-duration processes, it is relevant to those systems that face
termination in a relatively short time. However, it is important to
recognize that often the process need not have many stages before a
long-duration analysis becomes meaningful.
The Policy-Iteration Method
for the Solution of
Sequential Decision Processes

Consider a completely ergodic N-state Markov process described by

a transition-probability matrix P and a reward matrix R. Suppose
that the process is allowed to make transitions for a very, very long
time and that weare interested in the earnings of the process. The total
expected earnings depend upon the total numberof transitions that the
system undergoes, so that this quantity grows without limit as the
numberof transitions increases. A more useful quantity is the average
earnings of the process per unit time. It was shown in Chapter 2
that this quantity is meaningful if the process is allowed to make many
transitions; it was called the gain of the process.
Since the system is completely ergodic, the limiting state proba-
bilities x; are independent of the starting state, and the gain g of the
system 1s
N

> mgs
g = +=1 (2.14)
where q; is the expected immediate return in state z defined by Eq. 2.3.
Every completely ergodic Markov process with rewards will have a
gain given by Eq. 2.14. If we have several such processes and we
should lke to know which would be most profitable on a long-term
basis, we could find the gain of each and thenselect the one with highest
gain.
The sequential decision process of Chapter 3 requires consideration
of many possible processes because the alternatives in each state may
be selected independenily. By way of illustration, consider the
32
 THE POLICY-ITERATION METHOD 33

three-dimensional array of Fig. 4.1, which presents in graphical form

the states and alternatives.

k Alternatives
J Succeeding
1-1/ 51,1 lel state
Pra" Piehe Pige hs
i Present state
bp
Poy 72

PodVr
Ted

Fig. 4.1. A possible five-state problem.

The array as drawn illustrates a five-state problem that has four

alternatives in the first state, three in the second, two in the third, one
in the fourth, and five in the fifth. Entered on the face of the array
are the parameters for the first alternative in each state, the second
row in depth of the array contains the parameters for the second
alternative in each state, and so forth. An X indicates that we have
chosen a particular alternative in a state with a probability and reward
distribution that will govern the behavior of the system at any time
that it enters that state. The alternative thus selected is called the
“decision”’ for that state; it is no longer a function of m. Theset of
X’s or the set of decisions for all states is called a “‘policy.’’ Selection
of a policy thus determines the Markov process with rewards that will
describe the operations of the system. The policy indicated in the
diagram requires that the probability and reward matrices for the system
be composedof thefirst alternative in state 4, the second alternativein
states 2 and 3, and the third alternative in states land 5. It 1s possible
to describe the polity by a decision vector d whose elements represent
the number of the alternative selected in each state. In this case
WrReNN Ww
a
ll

An optimal policy is defined as a policy that maximizes the gain,

or average return per transition.* In the five-state problem dia-
grammed in Fig. 4.1, there are 4 x 3 x 2 x 1 x 5 = 120 different
* Weshall assume for the momentthatall policies produce completely ergodic
Markov processes. This assumption will be relaxed in Chapter6.
34 THE POLICY-ITERATION METHOD

policies. It is conceivable that we could find the gain for each

of these policies in orderto find thepolicy with the largest gain. How-
ever feasible this may be for 120 policies, it becomes unfeasible for very
large problems. For example, a problem with 50 states and 50 alter-
natives in each state contains 505°( ~ 1085) policies.
The policy-iteration method that will be described will find the optimal
policy in a small numberof iterations. It is composed of two parts, the
value-determination operation and the policy-improvement routine.
Weshall first discuss the value-determination operation.

The Value-Determination Operation

Suppose that we are operating the system under a given policy so that
we havespecified a given Markovprocess with rewards. If this process
were to be allowed to operate for ” stages or transitions, we could define
v;(m) as the total expected reward that the system will earn in movesif
it starts from state 7 under the given policy.
The quantity v;(7) must obey the recurrence relation (Eq. 2.4)
derived in Chapter 2:
N
vi(n) = ge + > pyvji(n —1) 1=1,2,---,N n=1,2,3,--+ (24)
j=l
There is no need for a superscript & to appear in this equation because
the establishment of a policy has defined the probability and reward
matrices that describe the system.
It was shown in Chapter 2 that for completely ergodic Markov proc-
esses vi(”) had the asymptotic form
vi(n) = ng + U4 1=1,2,---,N for large n (2.17)
In this chapter we are concerned only with systems that have a very,
very large number of stages. We are then justified in using Eq. 2.17
in Eq. 2.4. We obtain the equations
N
ng +4 = 4 + 2pall —-lgt+v]) i=1,2,---,N
j=1

nmtu=qt ((n — l)g Spa + Sow

N
Since > bij = 1, these equations become
j=1
N

g+u=Gt> py, i=1,2,---,N (4.1)

j=l
 VALUE-DETERMINATION OPERATION 35

Wehave now obtained a set of N linear simultaneous equations that

relate the quantities v; and g to the probability and reward structure
of the process. However, a count of unknownsreveals N v; and 1 g
to be determined, a total of N + 1 unknowns. The nature of this
difficulty may be understood if we examinethe result of adding a constant
a to all v; in Eqs. 4.1. These equations become
N
etut+a=qit > piv; + a)
j=1
or
N

gtu=q t+ > piry

j=1
The original equations have been obtained once more, so that the
absolute value of the v; cannot be determined by the equations. How-
ever, if we set one of the v; equal to zero, perhaps vy, then only N un-
knowns are present, and the Eqs. 4.1 may be solved for g and the
remaining v;. Notice that the v; so obtained will not be those defined
by Eq. 2.17 but will differ from them by a constant amount. Never-
theless, because the true values of the v; contain a constant term
N
> 7404(0)
t=1

as shown in Eq. 2.13, they have no real significance in processes that

continue for a very large numberof transitions. The v; produced by
the solution of Eqs. 4.1 with vy = 0 will be sufficient for our purposes;
they will be called the relative values of the policy.
The relative values may be given a physical interpretation. Consider
the first two states, land 2. For any large n, Eq. 2.17 yields

Vi(n) = ng + V1 Vo(n) = ng + Ve

The difference v1(m) — ve(m) = v1 — ve for any large m; it is equal

to the increase in the long-run expected earnings of the system caused
by starting in state 1 rather than state 2. Since the difference v1 — ve
is independentof any absolutelevel, the relative values may be used to
find the difference. In other words, the difference in the relative values
of the two states v1 — ve 1s equal to the amount that a rational man
would be just willing to pay in order to start his transitions from
state 1 rather than state 2 if he is going to operate the system for
many, many transitions. We shall exploit this interpretation of the
relative values in the examples of Chapter5.
36 THE POLICY-ITERATION METHOD

If Eqs. 4.1 are multiplied by 7, the limiting state probability of the

ith state, and then summed over 7, we obtain
N N

g£ > Tm + > THU; = >Tegi + Ss Ss TePijv;

+=1 t=1 jg=17=1

The basic equations (Eqs. 1.5 and 1.6) show that this expression is
equivalent to Eq. 2.14:
N

> mgs
g = 1=1 (2.14)
A relevant question at this pointis this: If we are seeking only the gain
of the given policy, why did we not use Eq. 2.14 rather than Eq. 4.1?
As a matterof fact, why are we botheringto find such thingsas relative
values at all? The answer is first, that although Eq. 2.14 does find
the gain of the process it does not inform us about howto find a better
policy. We shall see that the relative values hold the key to finding
better and better policies and ultimately the best policy.
A second part of the answer is that the amount of computational
effort required to solve Eqs. 4.1 for the gain and relative values is about
the same as that required to find the limiting state probabilities using
Eqs. 1.5 and 1.6, because both computations require the solution of NV
linear simultaneous equations. From the point of view of finding the
gain, Eqs. 2.14 and 4.1 are a standoff; however, Eqs. 4.1 are to be pre-
ferred because they yield the relative values that will be shown to be
necessary for policy improvement.
From the point of view of computation,it is interesting to note that
we have considerable freedom in scaling our rewards because of the
linearity of Eqs. 4.1. If the rewards 7; of a process with gain g and
relative values v; are modified by a linear transformation to yield new
rewards 7; in the sense %;’ = arij + 6, then since
N

ge = >, bury
j=1

the new expected immediate rewards q;’ will be gs’ = agi + 6,so that the
gi are subjected to the same transformation. Equations 4.1 become
N

gEtu=
“° + Dba a=1,2,---,N

OT

(ag + 6) + (avi) = qi + 2, Pis(a2;)

and 7
N

gt! = ge + > pyr;

j=l
 POLICY-IMPROVEMENT ROUTINE 37

The gain g’ of the process with transformed rewardsis thus ag + 3,

whereas the values v;’ of this process will equal av;. The effect of
changes in the units of measurement and in the absolute level of the
reward system upon the gain and relative valuesis easily calculated.
Thus we could normalize all rewards to be between 0 and 1, solve the
entire sequential decision process, and then use the inverse of our
original transformation to return the gain and relative values to their
original levels.
Wehave now shown that for a given policy we can find the gain and
relative values of that policy by solving the N linear simultaneous
equations (Eqs. 4.1) with vy = 0. Weshali now show howtherelative
values may be usedto find a policy that has higher gain than theoriginal
policy.

The Policy-Improvement Routine

In Chapter 3 we found that if we had an optimal policy up to stage n
we could find the best alternative in the 7th state at stage m + 1 by
maximizing

qi®& + > piskvj(n) (4.2)

over all alternatives in the 7th state. For large n, we could substitute
Eg. 2.17 to obtain
N

gk + D puk(ng + vj) (4.3)

J

as the test quantity to be maximized in each state. Since

N

> put = 1
g=1

the contribution of mg and any additive constant in the v; becomes a

test-quantity component that is independent of &. Thus, when we are
making our decision in state 7, we can maximize
N

gt + > pesko; (4.4)

j=1

with respect to the alternatives in the7zth state. Furthermore, we can

use the relative values (as given by Eqs. 4.1) for the policy that was
used up to stage m.
The policy-improvement routine may be summarizedas follows: For
each state 7, find the alternative & that maximizes the test quantity
N

gk + > pity;
j=
38 THE POLICY-ITERATION METHOD

using the relative values determined under the old policy. This
alternative k now becomes d;, the decision in the ith state. A new
policy has been determined when this procedure has been performed
for every state.
Wehave now, by somewhatheuristic means, described a method for
finding a policy that is an improvement over our original policy. We
shall soon prove that the new policy will have a higher gain than the
old policy. First, however, we shall show how the value-determination
operation and the policy-improvement routine are combined in an
iteration cycle whose goalis the discovery of the policy that has highest
gain amongall possible policies.

The Iteration Cycle

The basic iteration cycle may be diagrammed as shownin Figure 4.2.

Value- Determination Operation

Use pi and q; for a given policy to solve
N
P* Et+u=Qat
A pyyy t= 1,2,---,N

for all relative values v; and g by setting vy to zero.

a

Policy-Improvement Routine
For each state 7, find the alternative k’ that maximizes
N
|___ gi + > pij*v; <¢—|
j=1
using the relative values v; of the previous policy. Then k’
becomes the new decision in the 7th state, g;*’ becomes q;, and
pi®’ becomes py.

Fig. 4.2. The iteration cycle.

The upper box, the value-determination operation, yields the g and

corresponding to a given choice of q; and f;;._ The lower box yields
the #:; and q; that increase the gain for a given set of vy; In other words,
the value-determination operation yields values as a function of policy,
 THE TOYMAKER’S PROBLEM 39

whereasthe policy-improvementroutine yields the policy as a function

of the values.
We may enter the iteration cycle in either box. If the value-
determination operation is chosen as the entrance point, an initial
policy must be selected. If the cycle is to start in the policy-improve-
ment routine, then a starting set of values is necessary. If there is no
a priors reason for selecting a particularinitial policy or for choosing a
certain starting set of values, then it is often convenient to start the
process in the policy-improvement routine with all v; = 0. In this
case, the policy-improvement routinewill select a policy as follows:
Foreach 2, it will find the alternative k’ that maximizes g;* and then
set di = k’.
This starting procedure will consequently cause the policy-improve-
ment routine to select as an initial policy the one that maximizes the
expected immediate reward in each state. The iteration will then
proceed to the value-determination operation with this policy, and the
iteration cycle will begin. The selection of an initial policy that maxi-
mizes expected immediate reward is quite satisfactory in the majority
of cases.
At this point it would be wise to say a few words about how to stop
the iteration cycle once it has done its job. The rule is quite simple:
The optimal policy has been reached (g is maximized) when the
policies on two successive iterations are identical. In order to prevent
the policy-improvement routine from quibbling over equally good alter-
natives in a particular state, it is only necessary to require that the
old d; be left unchangedif the test quantity for that d; is as large as
that of any other alternative in the new policy determination.
In summary, the policy-iteration method just described has the
following properties:

1. The solution of the sequential decision process is reducedto solving

sets of linear simultaneous equations and subsequent comparisons.
2. Each succeeding policy found in the iteration cycle has a higher
gain than the previous one.
3. The iteration cycle will terminate on the policy that has largest
gain attainable within the realm of the problem; it will usually find this
policy in a small numberof iterations.

Before proving properties 2 and 3, let us see the policy-iteration

method in action by applying it to the toymaker’s problem.

The Toymaker’s Problem

The data for the toymaker’s problem were presented in Table 3.1.
40 THE POLICY-ITERATION METHOD

There are two states and two alternatives in each state, so that there
are four possible policies for the toymaker, each with associated proba-
bilities and rewards. He would like to know whichof thesefourpolicies
he should follow into the indefinite future to make his average earnings
per week as large as possible.
Let us suppose that we have no a priort knowledge about which policy
is best. Then if we set v1 = vg = 0 andenter the policy-improvement
routine, it will select as an initial policy the one that maximizes expected
immediate reward in each state. For the toymaker, this policy con-
sists of selection of alternative 1 in both states 1 and 2. For this
policy
1 0.5 0.5 6
e= | r= lod "A 7* |_|
Weare now ready to begin the value-determination operation that
will evaluate our initial policy. From Eqs. 4.1,
gtv= 6 + 0.571 + 0.5ve £ + v2 = —3 + 0.4v1 + 0.6v2

Setting ve = 0 and solving these equations, we obtain

(Recall that by use of a different method the gain of 1 was obtained

earlier for this policy.) We are now ready to enter the policy-improve-
ment routine as shown in Table 4.1.

Table 4.1. TOYMAKER POLICY-IMPROVEMENT ROUTINE

State Alternative Test Quantity
N
i k gi + j=1
> Pasko;
1 1 6 + 0.5(10) + 0.5(0) = 11
2 4+ 0.8(10) + 0.2(0) = 12<

2 1 —3 + 0.4(10) + 0.6(0) = 1
2 —5 + 0.7(10) + 0.3(0) = 2<

The policy-improvement routine reveals that the second alternative

in each state produces a higher value of the test quantity
N

gi* + > puto;

j=1

than does thefirst alternative. Thus the policy composed of the second
alternative in each state will have a higher gain than ouroriginal policy.
 THE TOYMAKER’S PROBLEM 4]

However, we must continue our procedure because we are not yet sure
that the new policy is the best we can find. Forthis policy,

e=[) Pfr os} a= [5

Equations 4.1 for this case become
gt = 44 0.801 + 0.2v2
gtve = —5 + 0.701 + 0.302
With ve = 0, the results of the value-determination operation are
g=2 v1 = 10 ve = 0

The gain of the policy d = A is thus twice that of the original

policy. We must now enter the policy-improvement routine again,
but, since the relative values are coincidentally the same as those for
the previousiteration, the calculations in Table 4.1 are merely repeated.
The policy d = |. is found once more, and, since we have found the
2
same policy twice in succession, we have found the optimal policy.
The toymaker should follow the second alternative in each state. Ifhe
does, he will earn 2 units per week on the average, and this will be a
higher average earning rate than that offered by any other policy. The
reader should verify, for example, that both policy d = |, and policy

d = | have inferior gains.

For the optimal policy, v1 = 10, ve = 0, so that v1 — ve = 10.

This means that, even when the toymaker is following the optimal
policy by using advertising and research, he is willing to pay up to
10 units to an outside inventor for a successful toy at any time that
he does not have one. Therelative values of the optimal policy may
be used in this way to aid the toymaker in making “one-of-a-kind”
decisions about whether to buy rights to a successful toy when business
is bad.
The optimal policy for the toymaker was found by valueiteration in
Chapter 3. The similarities and differences of the two methods should
now be clear. Note how the policy-iteration method stopped of its
own accord whenit achieved policy convergence; there is no comparable
behavior in the value-iteration method. The policy-iteration method
has a simplicity of form andinterpretation that makes it very desirable
from a computational point of view. However, we must always bear
42 THE POLICY-ITERATION METHOD

in mind that it may be applied only to continuing processes or to those

whose termination is remote.

A Proof of the Properties of the Policy-Iteration Method

Suppose that we have evaluated a policy A for the operation of the
system and that the policy-improvement routine has produced a policy
B that is different from A. Then if we use superscripts A and B to
indicate the quantities relevant to policies A and B, we seek to prove
that g? > gA.
It follows from the definition of the policy-improvement routine
that, since B was chosen over A,
N N
qiB + > piyBoj4 > GA + > pyAvjA 1 =1,2,---,N (4.5)
j=1 j=1

Let
N N

ye = QB + > pyBujA — gid — >, PisAvy4 (4.6)

j=1 j=1
so that y; 2 0. The quantity y; is the improvementin the test quan-
tity that the policy-improvement routine was able to achieve in the
ith state. For policies A and B individually, we have from Eqs.4.1
N
gB + uF = gi® + > pigBv,® 7=1,2,---,N (4.7)
j= 1
N

gat vA = qd + > pytvjA 1 =1,2,---,N (4.8)

j=1
If Eq. 4.8 is subtracted from Eq. 4.7, then the result is
N N

eB — gd + vB — 44 = GiB — qd + > pizBvj® — > piyAvj4 (4.9)

j=1 j=1

If Eq. 4.6 is solved for gi? — q:4 and this result is substituted into
Eq. 4.9, then we have
N N

gB — g4 + 4B — vid = ye — D> PigBoj4 + D> pasAvs4

j=l j=1
N N

+ > piyBvjB — > piyAvsA

j=1 j=1

Or

ge — eA + ve — vd = ye + D> pyP(4® — v4) (4.10)

N

j=1
 A PROOF OF THE POLICY-ITERATION METHOD 43

Let g4 = g® — gA and vA = v,8 — v;4. Then Eq. 4.10 becomes

N
er tod =yet > pb 1=1,2,---,N (4.11)
j=l
Equations 4.11 are identical in form to Eqs. 4.1 except that theyare
written in terms of differences rather than in terms of absolute quanti-
ties. Just as the solution for g obtained from Eqs. 4.1 is
N

g = i=1
D> mg
so the solution for g4 in Eqs. 4.11 is
N
gi= > TBy; (4.12)
i=l
where 78 is the limiting state probability of state z under policy B.
Since all 2,2 > 0 and all y; > 0, therefore, g4 > 0. In particular,
g® will be greater than g4 if an improvementin the test quantity can
be made in any state that will be recurrent under policy B. We see
from Eq. 4.12 that the increases in gain caused by improvements in
each recurrent state of the new policy are additive. Even if we
performed our policy improvement on only one state and left other
decisions unchanged, the gain of the system would increase if this
state is recurrent under the new policy.
Weshall now showthatit is impossible for a better policy to exist and
not be found at some timeby the policy-improvement routine. Assume
that, for two policies A and B, g? > g4, but the policy-improvement
routine has converged on policy A. Then in all states, y; < 0, where
yi 1s defined by Eq. 4.6. Since 7? > 0 for all 7, Eq. 4.12 holds that
g2 —gA < 0. But g? > g4 by assumption, so that a contradiction
has been reached. It is thus impossible for a superior policy to remain
undiscovered.
The following chapter will present further examples of the policy-
iteration method that show how it may be applied to a variety of
problems.
Use of the Policy-Iteration Method
in Problems of Taxicab Operation,
Baseball, and Automobile Replacement

An Example—Taxicab Operation
Consider the problem of a taxicab driver whose territory encompasses
three towns, A, B, and C. If he is in town A, he has three alterna-
tives:

1. He can cruise in the hope of picking up a passenger by being

hailed.
2. He can drive to the nearest cab stand and wait in line.
3. He can pull over and wait for a radio call.

If he is in town C, he has the same three alternatives, but if he is in

town B,the last alternative is not present becausethereis no radio cab
service in that town. Fora given town and given alternative, there is a
probability that the next trip will go to each of the towns A, B, and C
and a corresponding reward in monetary units associated with each
such trip. This reward represents the income from thetrip after all
necessary expenses have been deducted. For example, in the case of
alternatives 1 and 2, the cost of cruising and of driving to the nearest
stand must be included in calculating the rewards. The probabilities
of transition and the rewards depend upon the alternative because
different customer population will be encountered under each alter-
native.
If we identify being in towns A, B, and C withstates 1, 2, and 3,
respectively, then we have Table 5.1.
44
 TAXICAB OPERATION 45
Table 5.1. DATA FOR TAXICAB PROBLEM
State Alternative Probability Reward Expected
Immediate
Reward
N
i k bist righ gk = > pagkragk
j=1
7=1 2 3 7=1 #2 3

1 1 re ¢ 4 r10 4 87 8
2 is 2 ve 8 2 4 2.75
3 | ££ $ 3] | 4 6 44 4.25

2 1 r+ O 3 14 O 18 16
2 is ¢& de 8 16 8 15

3 1 4+ 86406 3 r10 2 87 7
2 4 2 4 6 4 2 4
3 t ve wt | 4 0 8] 4.5
The reward is measured in some arbitrary monetary unit; the num-
bers in Table 5.1 are chosen more for ease of calculation than for any
other reason.
In order to start the decision-making process, suppose that we make
V1, Vz, and vg = O, so that the policy improvement will chooseinitially
the policy that maximizes expected immediate reward. By examining
the q;*, we see that this policy consists of choosing thefirst alternative
in each state. In other words, the policy vector d whose zth elementis
the decision in the 7th state is

d= |1
1

or the policy is always cruise.

The transition probabilities and expected immediate rewardscorre-
sponding to this policy are

2} 8
P=|i 0 3 q = |16
t 2 3 7
Nowthe value-determination operation is entered, and we solve the
equations
N

g+u=qat > py 1=1,2,---,N

Ji=
46 EXAMPLES OF THE METHOD

In this case we have

g++. = 8 + 401 + juve + jv
£ + ve = 16 + fv1 + Ove + dug
&+3 = 7 + ZU1 + ve + FU
Setting v3 = 0 arbitrarily and solving these equations, we obtain
Vi = 1.33 v2 = 7.47 v3 = 0 g = 9.2

Undera policy of always cruising, the driver will make 9.2 units per
trip on the average.
Returning to the policy-improvement routine, we calculate the
quantities
N

git + > pisto;

j=1

for all 7 and &, as shown in Table 5.2.

Table 5.2. First PoLicy IMPROVEMENT FOR TAXICAB PROBLEM

State Alternative Test Quantity
N
i k gk + > Pak;
j=1

1 1 10.53<
2 8.43
3 5.52

2 1 16.67
2 21.62<—

3 1 9.20
2 9.77<—
3 5.97

Wesee that for: = 1 the quantity in the right-hand column is maxi-

-f
mized when &k = 1. For 2 = or 3, it is maximized when & = 2.
In other words, our new policy is

This means that if the driver is in town A he should cruise; if he is

in town B or C, he should drive to the nearest stand.
Wehave now

owls
iL
A hoje

Hele OO[N] ile

|

4
1
a]

1
l

1
8
 TAXICAB OPERATION 47

Returning to the value-determination operation, we solve the equations

g+= 8 + $01 + Gve + fv3
gt+ve= 15 + yevi + fre + Yevs
gtvgs = 4+ §v1 + fv2 + $3
Again with v3 = 0, we obtain

vi = —3.88 ve = 12.85 v3 = 0 g = 13.15

Note that g has increased from 9.2 to 13.15 as desired, so that the
cab earns 13.15 units per trip on the average. A second policy-
improvement routine is shown in Table 5.3.

Table 5.3. SECOND POLICY IMPROVEMENT FOR TAXICAB PROBLEM

State Alternative Test Quantity
N
4 R gk + > pajko;
j=1
1 1 9.27
2 12.14<—
3 4.89

2 1 14.06
2 26.00<—

3 1 9.24
2 13.10<—
3 2.39

f
The new policy is thus

The driver should proceed to the nearest stand, regardless of the town
in which he finds himself.
With this policy
1
= 2.75
a
leo OlN] iBico

16
— |. q = {15
O0|pat o/-

P= 16
I

i
8
4

Entering the value-determination operation, we have

gt vi 2.75 + ~evi + 300 + 75U3
& + ve 15 + 6V1 + £V2 + 6U3
g+tuvu= 4 + $01 + $v2 + gv
48 EXAMPLES OF THE METHOD

With vg = 0, the solution to these equationsis

v1 = —1.18 vg = 12.66 v3 = 0 g = 13.34
Note that there has been a small but definite increase in g from 13.15
to 13.34; however, we as yet have no evidence that the optimal policy
has been found. The next policy improvement is shown in Table 5.4.

Table 5.4. THtrD PoLicy IMPROVEMENT FOR TAXICAB PROBLEM

State Alternative Test Quantity
N
a R gk + > pigko,
j=l
1 1 10.58
2 12.17<—
3 5.54

2 1 15.41
2 24.42<—

3 1 9.87
2 13.34<—
3 4.41
The new policy is
2
d= {2
2
but this is equal to the previous policy, so that the process has con-
verged, and g has attained its maximum, namely, 13.34. The cab
driver should drive to the nearest stand in any city. Following this
policy will yield a return of 13.34 units per trip on the average, almost
half as much again as the policy of always cruising found by maxi-
mizing expected immediate reward. The calculations are summarized
in Table 5.5.
Table 5.5. SUMMARY OF TAXICAB PROBLEM SOLUTION
V1 0 1.33 — 3.88 —1.18
v9 0 7.47 12.85 12.66
U3 0 0 0 0

g — 9.20 13.15 13.34

WOON AOS AOS
dy 1 1 2 2
do 1 2 2 2 STOP
dg 1 2 2 2
P indicates that this step takes place in the policy-improvementroutine.
v indicates that this step takes place in the value-determination operation.
 A BASEBALL PROBLEM 49

Notice that the optimal policy of always driving to a stand is the

worst policy in terms of immediate reward. This is roughly equivalent
to saying that if a cab driver is to conduct his affairs in the best way
he must consider not only the fare from a trip but also the destination
of the trip with respect to the expectation of further trips. Any
experienced cab driver will verify the wisdom of such reasoning. It
often happens in the sequential decision process that the birds in the
bush are worth more than the one in the hand.
The policy-improvement routine of Table 5.3 provides us with an

f
opportunity to check Eq. 4.12. The policy changed as a result of this
routine from a policy A for which

-f
to a policy B described by

The quantities y; defined by Eq. 4.6 may be obtained from Table 5.3.
They are the differences between the test quantities for each policy.
We find y1 = 12.14 — 9.27 = 2.87, whereas yz = y3 = 0 because the
decisions in states 2 and 3 are the samefor both policies A and B.
Application of Eqs. 1.5 and 1.6 to the transition-probability matrix
for policy B yields the limiting state probabilities:
t1 = 0.0672 te = 0.8571 3 = 0.0757
From Eq. 4.12 we then have that
g4 = (0.0672)(2.87) = 0.19
The change of policy from A to B should thus have produced an in-
crease in gain of 0.19 unit. Since g4 = 13.15 and g®? = 13.34, our
prediction is correct.

A Baseball Problem

It is interesting to explore computational methods of solving the

discrete sequential decision problem. The policy-improvement routine
is a simple computational problem comparedto the value-determination
operation. In order to determine the gain and the values,it is necessary
to solve a set of simultaneous equations that may be quite large.
A computer program for solving the problem that we have been
discussing has been developed as an instrument of research. This
30 EXAMPLES OF THE METHOD

program performs the value-determination operation by solving a set

of simultaneous equations using the Gauss-Jordan reduction. Prob-
lems possessing up to 50 states and with up to 50 alternatives in each
state may be solved.

Table 5.6. BASEBALL PROBLEM DATA

1. Managertells player at bat to try for a hit.

Player Player on Player on
Probability Batter on First Second Goes Third Goes
Outcome of Outcome Goes to Goes to to to

Single 0.15 1 2 3 H
Double 0.07 2 3 H H
Triple 0.05 3 H H H
Homerun 0.03 H H H H
Base on balls 0.10 1 2 3 (if forced) H (if forced)
Strike out 0.30 Out 1 2 3
Fly out 0.10 Out 1 2 H (if less than
2 outs)
Ground out 0.10 Out 2 3 H (if less than
2 outs)
Double play 0.10 Out The player nearest first is out.

The interpretation of these outcomes is not described in detail. For instance,

if there are no men on base, then hitting into a double play is counted simply as
making an out.

2. Manuger tells player at bat to bunt.

Outcome Probability Effect

Single 0.05 Runners advance one base.

Sacrifice 0.60 Batter out; runners advance one base.
Fielder’s choice 0.20 Batter safe; runner nearest to making run is
out, other runners stay put unless forced.
Strike or foul out 0.10 Batter out; runners do not advance.
Double play 0.05 Batter and player nearest first are out.

3. Managertells player on first to steal second.

4. Manager tells player on secondto steal third.

In either case, the attempt is successful with probability 0.4, the player’s position
is unchanged with probability 0.2, and the player is out with probability 0.4.

5. Manager tells player on third to steal home.

The outcomes are the same as those above, but the corresponding probabilities
are 0.2, 0.1, and 0.7.
Baseball fans please note: No claim is madefor the validity of either assumptions
or data.
 A BASEBALL PROBLEM ol

When this program was used to solve the taxicab problem, it of

course yielded the same solutions we obtained earlier, but with more
significant figures. The power of the technique can be appreciated
only in a more complex problem possessing several states. As an
illustration of such a problem, let us analyze the game of baseball
using suitable simplifying assumptions to make the problem manageable.
Consider the half of an inning of a baseball game when one team is
at bat. This team is unusual becauseall its players are identical in
athletic ability and their play is unaffected by the tensions of the game.
The manager makesall decisions regarding the strategy of the team,
and his alternatives are limited in number. He maytell the batter
to hit or bunt, tell a man on first to steal second, a man on second to
steal third, or a man on third to steal home. For each situation during
the inning andfor each alternative, there will be a probability of reaching
each othersituation that could exist and an associated reward expressed
in runs. Let us specify the probabilities of transition under each
alternative as shown in Table 5.6.
The state of the system depends upon the numberof outs and upon
the situation on the bases. We may designate the state of the system
by a four-digit number d3d2d3d4, where d is the number of outs—O,1, 2,
or 3—andthe digits dedsd4 are 1 or 0 corresponding to whether there
is or is not a player on bases 3, 2, and 1, respectively. Thus thestate
designation 2110 would identify the situation “‘2 outs; players on second
and third,’’ where 1111 would mean “1 out; bases loaded.’ The
states are also given a decimal number equal to 1 + 8d, + (decimal
numbercorresponding to binary number djd3d4). Thestate 0000 would
be state 1, and the state 3000 would be state 25; 2110 corresponds
to 23, 1111 to 16. There are eight base situations possible for each of
the three out situations 0, 1, 2. There is also the three-out case 3——-,
where the situation on base is irrelevant and we mayarbitrarily call
3—~—-, the state 3000. Therefore, we have a 25-state problem.
The numberof alternatives in each state is not the same. State
1000 or 9 has no men on base, so that noneof the stealing alternatives
are applicable, and only the hit or bunt options are present. State
0101 or 6 has four alternatives: hit, bunt, steal second, or steal home.
State 3000 or 25 has only 1 alternative, and that alternative causes it
to return to itself with probability 1 and reward 0. State 25 is a trap-
ping or recurrentstate; it is the only state that the system may occupy
as the numberof transitions becomesinfinite.
To fix ideas still more clearly, let us list explicitly in Table 5.7 the
transition probabilities #;;* and rewards 7;;* for a typical state, say 0011
or 4. In state 4(2 = 4), three alternatives apply: hit, bunt, steal
third. Only nonzero #;,;* are listed. The highest expected immediate
52 EXAMPLES OF THE METHOD

reward in this state would be obtained by following alternative 1,

Hit.
Table 5.7. PROBABILITIES AND REWARDS FOR STATE 4 OF BASEBALL
PROBLEM (0011)
First alternative: Hit, k = 1.
Next State q pa; 14;

=
0000 1 0.03 3
0100 5 0.05 2
0110 7 0.07 1
0111 8 0.25 0 gai = 0.26
1011 12 0.40 0
1110 15 0.10 0
2010 19 0.10 0

Second alternative: Bunt, k = 2.

Next State q paj? 145°

0111 8 0.05 0
1011 12 0.30 0 2— 90
1110 15 0.60 0 qa" =
2010 19 0.05 0

Third alternative: Steal third, k = 3.

Next State q pa;? 745°

0011 4 0.20 0 3 0
0101 6 0.40 0 ia =
1001 10 0.40 0

Table 5.8, entitled ‘‘Summary of Baseball Problem Input,’’ shows

for each state 7 the state description, the alternatives open to the man-
ager in that state, and q:*, the expected immediate reward(in runs) from
following alternative k in state 7. The final column showsthe policy
that would be obtained by maximizing expected immediate reward in
each state. This policy is to bunt in states 5, 6, 13, and 14, andto hit
in all others. States 5, 6, 13, and 14 may be described as those states
with a player on third, none on second, and with less than two outs.
The foregoing data were used as an input to the computer program
described earlier. Since the program chooses an initial policy by
maximizing expected immediate reward, the initial policy was the one
just mentioned. The machine had to solve the equations only twice to
reach a solution. Its results are summarized in Table 5.9.
The optimal policy is to hit in every state. The v; may be interpreted
as the expected numberof runs that will be made if the inning is now
in state 7 and it is played until three outs are incurred. Since a team
 A BASEBALL PROBLEM 53
Table 5.8. SUMMARY OF BASEBALL PROBLEM INPUT
Number
of Alter- Initial
Alternative Alternative Alternative Alternative natives Policy
State Description 1 2 3 4 in State dy if ug
Bases k=1 k=2 k = 3 k=4 1 Set = 0
t Outs 3 2 1 gq qi qe qt
1 0 0 O O- 0.03 Hit — — — 1 1
2 0 0 O 1. 0.11 Hit O Bunt 0 Steal 2 — 3 1
3 0 0 1 #O- 0.18 Hit QO Bunt 0 Steal 3 — 3 1
4 0 0 1 #1 0.26 Hit O Bunt 0 Steal 3 — 3 1
5 0 1 O O- 0.53 Hit 0.65 Bunt 0.20 Steal H — 3 2
6 0 1 O 1 0.61 Hit 0.65 Bunt 0 Steal2 0 Steal H 4 2
7 0 1 1 OO 0.68 Hit 0.65 Bunt 0.20 Steal H — 3 1
8 0 1 1 #1 0.86 Hit 0.65 Bunt 0.20 Steal H — 3 1
9 1 0 O O- 0.03 Hit — — — 1 1
10 1 0 O 1. 0.11 Hit O Bunt 0 Steal 2 — 3 1
11 1 0 1 O- 0.18 Hit O Bunt 0 Steal 3 — 3 1
12 1 0 1 #1 0.26 Hit O Bunt 0 Steal 3 — 3 1
13 1 1 O O- 0.53 Hit 0.65 Bunt 0.20 Steal H — 3 2
14 1 1 O 1 0.61 Hit 0.65 Bunt 0 Steal2 0.20 Steal H 4 2
15 1 1 1 #O- 0.68 Hit 0.65 Bunt 0.20 Steal H — 3 1
16 1 1 1 #1 £0.86 Hit 0.65 Bunt 0.20 Steal H — 3 1
17 2 0 O O- 0.03 Hit — — — 1 1
18 2 0 O 1. O11 Hit O Bunt 0 Steal 2 — 3 1
19 2 0 1 #O- 0.18 Hit O Bunt 0 Steal 3 — 3 1
20 2 0 1 1 0.26 Hit O Bunt 0O Steal 3 — 3 1
21 2 1 OO O- 0.33 Hit 0.05 Bunt 0.20 Steal H — 3 1
22 2 1 O 1 0.41 Hit 0.05 Bunt 0 Steal2 0.20 Steal H 4 1
23 2 1 1 O 0.48 Hit 0.05 Bunt 0.20 Steal H — 3 1
24 2 1 1 #1 0.66 Hit 0.05 Bunt 0.20 Steal H — 3 1
25 3 — — — 0O Trapped — — — 1 1

starts each inning in state 1, or ‘‘no outs, no men on,’’ then v1 may be
interpreted as the expected numberof runs per inning under the given
policy. The initial policy yields 0.75 for v1, whereas the optimal
policy yields 0.81. In other words, the team will earn about 0.06
more runs per inning on the average if its uses the optimal policy
rather than the policy that maximizes expected immediate reward.
Note that under both policies the gain was zero as expected, since
after an infinite number of movesthe system will be in state 25 and will
always make reward 0. Note also that, in spite of the fact that the
gain could not be increased, the policy-improvement routine yielded
values for the optimal policy that are all greater than or equal to those
for the initial policy. The appendix showsthat the policy-improvement
routine will maximize valuesif it is impossible to increase gain.
The values v; can be used in comparing the usefulness of states. For
example, under either policy the manager would rather be in a position
with two men out and bases loaded than be starting a new inning
(compare Ve4 with v1). However, he would rather start a new inning
than have two men out and men on second and third (compare ve3
with v3). Many other interesting comparisons can be made. Under
the optimal policy, having no men out and a player on first is just about
as valuable a position as having one man out and players on first and
j4 EXAMPLES OF THE METHOD

second (compare v2 with vie). It is interesting to see how the preceding

comparisons compare with our intuitive notions of the relative values
of baseball positions.

Table 5.9. SUMMARY OF BASEBALL PROBLEM SOLUTION

Iteration 1 Iteration 2
g=0 g=0
State Description Decision Value v; State Description Decision Value v;

1 0000 Hit 0.75 1 0000 Hit 0.81

2 0001 Hit 1.08 2 0001 Hit 1.25
3 0010 Hit 1.18 3 0010 Hit 1.35
4 0011 Hit 1.82 4 0011 Hit 1.89
5 0100 Bunt 1.18 5 0100 Hit 1.56
6 0101 Bunt 1.56 6 0101 Hit 2.07
7 0110 Hit 2.00 7 0110 Hit 2.17
8 0111 Hit 2.67 8 0111 Hit 2.74
9 1000 Hit 0.43 9 1000 Hit 0.46
10 1001 Hit 0.75 10 1001 Hit 0.77
11 1010 Hit 0.79 11 1010 Hit 0.86
12 1011 Hit 1.21 12 1011 Hit 1.23
13 1100 Bunt 0.88 13 1100 Hit 1.11
14 1101 Bunt 1.10 14 1101 Hit 1.44
15 1110 Hit 1.46 15 1110 Hit 1.53
16 1111 Hit 1.93 16 1111 Hit 1.95
17 2000 Hit 0.17 17 2000 Hit 0.17
18 2001 Hit 0.34 18 2001 Hit 0.34
19 2010 Hit 0.40 19 2010 Hit 0.40
20 2011 Hit 0.59 20 2011 Hit 0.59
21 2100 Hit 0.51 21 2100 Hit 0.51
22 2101 Hit 0.68 22 2101 Hit 0.68
23 2110 Hit 0.74 23 2110 Hit 0.74
24 2111 Hit 0.99 24 2111 Hit 0.99
25 3000 Hit 0 25 3000 Hit 0

The Replacement Problem

The examples of the policy-iteration method presented up to this
point have been somewhat far removed from the realm of practical
problems. It would be extremely interesting to see the method applied
to a problem that is of major importance to industry. As an example
of such a practical application, the replacement problem was chosen.
This is the problem of when to replace a piece of capital equipment
that deteriorates with time. The question to be answered is this:
If we now own a machine of a certain age, should we keep it or should
we tradeit in; further, if we trade it in, how old a machine should we
buy?
In order to fix ideas, let us consider the problem of automobile
 THE REPLACEMENT PROBLEM ID

replacement over a time interval of ten years. We agree to review

our current situation every three months and to make a decision on
keeping our present car or trading it in at that time. Thestate of the
system, 7, is described by the age of the car in three-month periods; 7
may run from 1 to 40. In order to keep the numberofstates finite,
a car of age 40 remains a car of age 40 forever (it is considered to be
essentially worn out). The alternatives available in each state are
these: Thefirst alternative, & = 1, is to keep the present car for another
quarter. The other alternatives, & > 1, are to buy a car of age k — 2,
where k — 2 may be as large as 39. We have then 40 states with 41
alternatives in each state, with the result that there are 414° possible
policies.
The data supplied are the following:

C;, the cost of buying a car of age z

T;, the trade-in value of a car of age z
E;, the expected cost of operating a car of age z until it reaches age
a+ 1
pi, the probability that a car of age z will survive to be agez + 1
without incurring a prohibitively expensive repair

The probability defined here is necessary to limit the number of

states. Acar of any age that has a hopeless breakdown is immediately
sent to state 40. Naturally, pao = 0.
The basic equations governing the system whenit is in state 7 are
the following: If & = 1 (keep present car),

gtu = —Ey + pivier + (1 — pa)vao

If k > 1 (trade for car of age k — 2),

getu = Ti — Cre — Ex-o + pu-ave-1 + (1 — pr-2)va0

It is simple to phrase these equations in termsof our earlier notation.
For instance,

qi® = —FE; for k=1 gi* = T; _— Cr-2 — Exo fork > 1

pig =tti
piy® =<1— pi 7 = 40 fork = 1
0 other 7

pez GW = R-|1
pig® = 41 — pee 7 = 40 fork >1
0 other 7
56 EXAMPLES OF THE METHOD

The actual data used in the problem are listed in Table 5.10 and
graphed in Figure 5.1. The discontinuities in the cost and trade-in
functions were introduced in order to characterize typical model-year
effects.

Table 5.10. AUTOMOBILE REPLACEMENT DATA

Agein Cost Trade- Operating Survival Agein Cost Trade- Operating Survival
Periods in Expense Proba- Periods in Expense Proba-
Value bility Value bility
4 C; T; E; Pi a C; rT; E; Pi

0 $2000 $1600 $50 1.000

1 1840 1460 53 0.999 21 $345 $240 $115 0-925
2 1680 1340 56 0.998 22 330 239225 118 0.919
3 1560 1230 59 0.997 23 315 210 121 0.910
4 1300 1050 62 0.996 24 300 200 125 0.900
5 1220 980 65 0.994 25 290 190 129 0.890
6 1150 8910 68 0.991 26 280 180 133 0.880
7 1080 840 71 0.988 27 265 170 137 0.865
8 900 710 75 0.985 28 250 160 141 0.850
9 840 650 78 0.983 29 240 150 145 0.820
10 780 600 81 0.980 30 230 86145 150 0.790
11 730 §©550 84 0.975 31 220 #8140 155 0.760
12 600 480 87 0.970 32 210 135 160 0.730
13 560 430 90 0.965 33 200 130 167 0.660
14 520 390 93 0.960 34 190 §=120 175 0.590
15 480 360 96 0.955 35 180 115 182 0.510
16 440 330 100 0.950 36 170 =110 190 0.430
17 420 310 103 0.945 37 160 105 205 0.300
18 400 290 106 0.940 38 150 95 220 0.200
19 380 270 109 0.935 39 140 87 235 0.100
20 360 255 112 0.930 40 130 80 250 0

2000 ry ry C—O dg tT Trib yp rb bp bit pr br |’ 1.00

OO Survival -— 0.90
1600
NS .
SO 4 Probability | 9.80

1200 |- A
Probability
Dollars

Oo

Oo
on

800

400

Years

16 20 24 28 32 36 40
Oo

fp

CO

nN

Periods z

Fig. 5.1. Automobile replacement data.

 THE REPLACEMENT PROBLEM a7

The automobile replacement problem was solved by the policy-

iteration method in seven iterations. The sequence of policies, gains,
and values is shown in Table 5.11. The optimal policy given by itera-
tion 7 is this: If you have a car that is more than 4 year old butless
than 64 years old, keep it. If you have a car of any other age, trade
it in on a 3-year-old car. This seems to correspond quite well
with our intuitive notions concerning the economics of automobile
ownership. Note that if we at present have a car that is 3 or 6 months
old we should trade it for a 3-year-old car, but that if our car’s
age is between 6 months and 64 years, we should keep it. These rules
enable us to enter the 3 to 64 cycle; once the cycle is entered, the car
we own will always be between 3 and 64 years old.* It is satisfying
to note that the program at any iteration requires that, if we are going
to trade, we must trade for a car whose age is independent of our
present car’sage. This is just the result that the logic of the situation
would dictate.
If we follow our optimal policy, we shall keep a car until it is 64 years
old and then buy a 3-year-old car. Suppose, however, that when
our car is 4 years old, a friend offers to swap his 1-year-old car for
ours foran amount X. Should we take up his offer? In order to answer
this question, we must look at the values.
In each of the iterations, the value of state 40 was set equal to zero
for computational purposes. Table 5.11 also showsthe values underthe
best policy when the value of state 40 is set equal to $80, the trade-in
value of a car of that age. When this is done, each v; represents the
value of a car of age 7 to a person whois following the optimal policy.
In order to answer the question just posed, we must compare the value
of a l-vear-old car, v4 = $1152, with the value of a 4-year-old car,
Vig = $422. If his asking price X is less than v4 — vig = $730, we
should make the trade; otherwise, we should not. If is, of course, not
necessary to change vao from zero in order to answer this problem;
however, making v49 = $80 does give the values an absolute physical
interpretation as well as a relative one.
If the optimal policy is followed, the yearly cost of transportation is
about $604 (4 x $150.95). If the policy of maximizing immediate
reward shown in iteration 1 were followed, the yearly cost would
be $1000. Thus, following a policy that maximizes future reward

* Of course, chaos for the automobile industry would result if everyone followed
this policy. Where would the 3-year-old cars come from? Economic forces
would increase the price of such cars to a point where the 3 to 64 policy is
no longer optimal. The preceding analysis must assume that there are enough
people in the market buying cars for psychological reasons that so-called
‘“‘rational’’ buyers are a negligible influence.
 Table 5.11. AUTOMOBILE REPLACEMENT RESULTS 58

Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 Iteration 7

Gain: — $250.00 Gain: — $193.89 Gain: — $162.44 Gain: — $157.07 Gain: — $151.05 Gain: — $150.99 Gain: — $150.95
State Decision Value Decision Value Decision Value Decision Value Decision Value Decision Value Decision Value Adjusted Value

36 $1374 20 $1380 12 $1380 12 $1380 $1380 $1460

36 1254 20 1260 12 1260 12 1260 1260 1340
36 1144 20 1150 12 1150 12 1150 1161 1241
36 964 20 970 K 1003 1072 1152
36 894 20 900 K 917 987 1067
36 824 906 986
36 754 831 911
36 624 760 840

MHAMAENONR OD
36 564 695 775
36 514 632 712
36 464 574 654
36 394 520 600
36 344 470 550
36 304 424 504
36 274 381 461
36 244 342 422
36 224 306 386
273 353
243 323
215 295
189 269
166 246
144 224
126 206
111 191
100 180
90 170
80 160
EXAMPLES OF THE METHOD

70 150
65 145
60 140
55 135
50 130
40 120
35 115
30 110
25 105
15 95
7 87
0 80
A numberin the decision column meanstrade for a car of that age in periods; a K means keep the presentcar. Values and gains are expressed in
dollars. The adjusted value is computed by adding $80, the value of a scrap car, to each of the Iteration 7 values.
 THE REPLACEMENT PROBLEM 39

rather than immediate reward has resulted in a saving of almost $400

per year. The decrease of period cost with iteration is shown in Fig.
5.2. The gain approaches the optimal value roughly exponentially.
Notice that the gains for the last three iterations are so close that for
all practical purposes the corresponding policies may be considered

300

250}- =
Cost per period (dollars)

200|- -_

150}— =

100}- =

50;- as

0 | | | | |

=
0 1 2 3 4 5 6 7 8
Iteration number

Fig. 5.2. Quarterly cost of automobile operation as a function of iteration.

to be equivalent. The fact that a 3-year-old car is the best buy is

discovered as early as iteration 4. The model-year discontinuity
occurring at 3 years is no doubt responsible for this particular
selection.
The replacement problem described in this section is typical of a
large class of industrial replacement problems. Placing these problems
in the frameworkof the policy-iteration method requires only a thorough
understanding of their peculiarities and some foresight in selecting a
suitable formulation.
The Policy-Iteration Method
for Multiple-Chain Processes

The developments of Chapter 4 assumed thatall the possible policies

for the system were completely ergodic. Complete ergodicity meant
that each policy defined a Markovprocess with only one recurrent chain,
and thus with a unique gain. Our problem was simply to find the
policy that had highest gain; the method of Chapter 4 accomplished
this purpose. This iteration techniqueis satisfactory for most problems
because we can usually define a problem in such a way as to meet the
requirement that it have only completely ergodic policies. This was
the case for the examples of Chapter 5.
However, it is not difficult to think of processes that have multiple
chains. In Chapter 1 we discussed a three-state process with transi-
tion-probability matrix
10 0
P=/0 1 0
23 14
3 3

that had two recurrent chains. Suppose that the process had an
1
expected immediate reward vector q = 2 expressed in dollars. The
3
matrix of limiting-state probability vectors was found in Chapter 1
to be
1 0 QO
S=1|10 1 0O

60
 VALUE-DETERMINATION OPERATION 61

1
The gain vector g = Sq = | 2 | and we interpret g as follows: If the
1.5
process were started in state 1, it would earn $1.00 per transition. A
start in state 2 would earn $2.00 per transition. Finally, since the
system is equally likely to enter state 1 or state 2 after many transitions
if it is started in state 3, such a starting position is expected to earn
$1.50 per transition on the average. The averaging involvedis per-
formed over several independent trials starting in state 3, because in
any given trial either $1.00 or $2.00 per transition will be ultimately
earned.
The gain of the system thus depends upon the state in which it is
started. A start in state 7 produces a gain g;, so that we maythinkof
the gain as being a function of the state as well as of the process. Our
new task is to find the policy for the system that will maximize the
gain of all states of the system. We are fortunate that the policy-
iteration method of Chapter 4 can be extended to the case of multiple-
gain processes. Weshall now proceed to this extension.

The Value-Determination Operation

Equations 2.15 show the asymptotic form that the total expected
reward of the system assumes when the system is started in state 2
and allowed to make a large numberof transitions:
vin) =nitu i=1,2,---,N (2.15)
Each state has its own g;, but, as discussed in Chapter2, all states that
are members of the same recurrent chain have the same gain. If we
agree to study the unending process, Eqs. 2.15 may be used with the
basic recurrence relation for total expected earnings,
N
vi(n + 1) = qi + > parm) 1 =1,2,---,N (6.1)
j=1
to yield
N

(n + l)gi + ve = gi + D. Pislngs + v)
j=1

Or
N N

mgit git= Git n> pugs + >, pir; (6.2)

j=1 j=1
If Eq. 6.2 is to be satisfied for any large n, it follows that
N

> pugy
gi= jg=1 t= 1,2,---,N (6.3)
62 MULTIPLE-CHAIN PROCESSES

and
N
gi + ve = Gi + > pan; a=1,2,---,N (6.4)
j=1
We now have the two sets of N linear simultaneous equations (Eqs.
6.3 and 6.4) that we mayuse to solve for the Ng; and Nv;. However,
Eqs. 6.3 may not be solved uniquely for the v;. The matrix [I — P]
has a singular determinant, so that the solution for the g; obtained from
Eqs. 6.3 will contain arbitrary constants. The number of arbitrary
constants is equal to the number of recurrent chains in the process.
Equations 6.3 essentially relate the gains of each state to the gains
of each recurrent chain. For example, in an L-chain process there will
be L independent gains. The gains of the states that are transient
will be related by Eqs. 6.3 to the L independent gains and so will be
determined when the independent gains are determined.
The N equations (Eqs. 6.4) must now be used to determine the L
independent gains and also the Nv;. We thus have ZL too many un-
knowns. However, suppose that we extend our former procedure by
setting equal to zero the v; for one state in each recurrent chain, so
that a total of Lv; will be equated to zero. Weshall generally choose
the highest numbered state in each chain to be the one whose 1, Is
set equal to zero. Wefind that Eqs. 6.4 may now besolved for the L
independent gains and for the remaining (N — L)v,.
The v; determined by the solution of Eqs. 6.4 maystill be called
relative values if we remember that they are relative within a chain.
The difficulty of solving Eqs. 6.3 and 6.4 is about the same as that of
finding the limiting-state-probability matrix S for a multiple-chain
process. Weshall see that the relative values v; are as useful as the
true limiting v; defined by Eqs. 2.15, as far as the search for the optimal
policy is concerned.
To illustrate these remarks, let us find the gain andrelative values of
the two-chain process discussed at the beginning of this section.
Equations 6.3. yield

g1 = £1 £2 = £2 23 = 321 + 382 + 983

Thus there are two independent gains g1 and ge. The gain of state 3
is expressed in terms of gi and ge by g3 = 4¢1 + $ge. Tf we could find
gi and ge, we should know the gain of every state. In general, we shall
call le the gain of chain 1, 2g the gain of 2, and so on, and then express
the gain of each state in terms of lg, 2g,---. This notation cannot be
used until the states are identified with respect to chain membership.
For this problem, gi = 1g, go = 2g, and g3 = $lg + 42g.
 POLICY-IMPROVEMENT ROUTINE 63

Equations 6.4 yield

fitm=14+1 £2 +g = 24+ ve
£3 + vg = 3 + 3U1 + 3U2 + $U3
If we now express g3 in termsof g1 and ge and then set equal to zero
the relative value of one state in each recurrent chain so that
V1 = ve = O, we obtain

gi=1 ge=2 321 + 382 + vg = 3 + fvs

The solution of this set of equations is g1 = 1, ge = 2, v3 = 2.25, so
that
gi = 1 g2 = 2 £3 = 1.5
v1 = 0 vg = 0 vg = 2.25

are the gains and relative values for each state of the process. The
gains are of course the sameas those obtainedearlier.

The Policy-Improvement Routine

Weshall now show howthe gains and therelative values of a policy
may be used to find the optimal policy for the system. Following
the argument of Chapter 4, if we now have a policy that we have been
following up to stage m, we may find a better decision for the zth state
at stage m + 1 by maximizing

ait + > pujto,(n) (4.2)

with respect to all alternatives in state 7. For large m, in Expression
4.2 we may substitute the relation in Eqs. 2.15 to obtain
N

gi® + > pis*(ngy + 23)

j=1

Or

N N

n> pistes + qi® + > pisko; (6.5)

<1 j=1
as the test quantity to be maximized. When ~ is large, Expression
6.5 is of course maximized by the alternative that maximizes
N

> diskg
j=1
64 MULTIPLE-CHAIN PROCESSES

Policy Evaluation
Use p;; and gq; for a given policy to solve the double set of
equations

w= She FHLBN
N

j=1

N
wt =U + > Py? 7=1,2,---,N
j=l
for all v; and g;, by setting the value of one v; in each recurrent
chain to zero.

Policy Improvement

For each state 2, determine the alternative & that maximizes

>, Pike;
j=l
using the gains of the previous policy, and make it the new
decision in the zth state.
If
N

> pijkgy
j=1
is the same for all alternatives, or if several alternatives are
equally good according to this test, the decision must be made
on the basis of relative values rather than gains. Therefore,
if the gain test fails, break the tie by determining the alter-
native k that maximizes
N

gk + > pigho;
j=l
using the relative values of the previous policy, and by making
it the new decision in the 7th state.
Regardless of whether the policy-improvementtest is based
on gains or values, if the old decision in the zth state yields as
high a value of the test quantity as any other alternative,
leave the old decision unchanged. This rule assures conver-
gence in the case of equivalent policies.
When this procedure has been repeated for all states, a
new policy has been determined and new [f,;] and [g¢;] ma-
trices have been obtained. If the new policy is the same as
the previous one, the iteration process has converged, and the
best policy has been found; otherwise, enter the upper box.

Fig. 6.1. General iteration cycle for discrete sequential decision processes.
 MULTICHAIN EXAMPLE 65

the gain test quantity, using the gains of the old policy. However,
whenall alternatives have the same value of
N

> dikes
j=1
or when a group of alternatives have the same maximum value of the
gain test quantity, the tie is broken by choosing the alternative that
maximizes the value test quantity,
N

git + > dijko;

j=
by using the relative values of the old policy. The relative values may
be used for the value test because, as we shall see, the test is not affected
by a constant added to the v; of all states in a recurrent chain.
The general iteration cycle is shown in Fig. 6.1. Note that it reduces
to our iteration cycle of Fig. 4.2 for completely ergodic processes. An
example with more than one chain will now be discussed, followed by
the relevant proofs of optimality.

A Multichain Example
Let us find the optimal policy for the three-state system whose
transition probabilities and rewards are shown in Table 6.1. The
transition probabilities are all 1 or 0, first for ease of calculation and
second to show that no difficulties are introduced by such a structure.
This system has the possibility of multiple-chain policies.

Table 6.1. A MULTICHAIN EXAMPLE

State Alternative Probabilities Expected Immediate
Reward
a k pik piok pisk qik
1 1 1 GO 0 1
2 0 1 0 2
3 0 0 1 3

2 1 1 0 0 6
2 0 1 0 4
3 0 0 1 5

3 0
- © ©

~] © 06
oo =
WN =

—
66 MULTIPLE-CHAIN PROCESSES

Let us begin with the policy that maximizes expected immediate

reward. This policy is composed of the third alternative in the first
state, the first alternative in the second state, and the second alternative
in the third state. For this policy
3 001 3
d=}1 P=|1 0 0 q = |6
2 01 0 9
Weare now readyto enter the policy-evaluation part of the iteration
cycle. Equations 6.3 yield

€1 = §3 §2 = §1 §3 = §2
These results show that there is only one recurrent chain and that
all three states are members of it. If we call its gain g, then
£1 = g2 = g3 = g; the relative valuevg is arbitrarily set equal to zero.
If we use these results in writing Eqs. 6.4, the following equations are
obtained:

gtu= 3 gtve=64+ 4 g= 9+
Their solution is g = 6, v1 = ve = —3, so that

£1 = 6 gz = 6 £3 = 6
and
v1 = —3 vg = —3 v3 = 0

Weare now ready to seek a policy improvement as shown in Table

6.2.

Table 6.2. First PoLticy IMPROVEMENT FOR MULTICHAIN EXAMPLE

State Alternative Gain Test Quantity Value Test Quantity
N N
i k >, Puke; git + > pike,
j=l j=l

1 1 6 1+ (-—3) = -2
2 6 2+ (-—3) = -1
3 6 °34+ (0) = 3<

2 1 6 6+ (-3)= 3
2 6 4+(-3)= 1
3 6 5+ (0)= 5<

3 1 6 8+(—-3)= 5
2 6 9+(-3)= 6
3 6 7+ (0) = T<
 MULTICHAIN EXAMPLE 67

Since the gain test produced ties in all cases, the value test was
necessary. The new policy is
3 0 0 1 3

3 0 0 1 7
This policy must now be evaluated. Equations 6.3 yield
1 = &3 §2 = &3 &3 = &3
We maylet g1 = ge = gs = @, Set vg = 0, and use Eqs. 6.4 to obtain
gtu= 3 gtuve=5 g=7

The solution is g = 7, v1 = —4, ve = —2, and so

gi=7 g2=7 gs =7
and
m= -4 v= -2 %=0
The policy-improvementroutine is shown in Table 6.3.

Table 6.3. SECOND PoLicy IMPROVEMENT FOR MULTICHAIN EXAMPLE

State Alternative Gain Test Quantity Value Test Quantity
N N
i k >, Pis*ey gt + > Pyke
j=1 j=1
1 1 7 —3
2 7 0
3 7 3<-

2 1 7 2
2 7 2
3 7 5<

3 1 7 4
2 7 7
3 7 7<

Since once more the gain test was indeterminate,it was necessary to
rely on the relative-value comparison. In state 3, alternatives 2 and
3 are tied in the value test. However, because alternative 3 was our
old decision, it will remain as our new decision. Wehave thus obtained
the same policy twice in succession; it must therefore be the optimal
policy. The optimal policy has a gain of 7 in all states. The policy
3
d = S , which was possible because of the equality of the value test
2
in state 3, is also optimal.
68 MULTIPLE-CHAIN PROCESSES

Although this system had the capacity for multichain behavior, such
behavior did not appear if we chose as our starting point the policy
that maximized expected immediate reward. Nevertheless, other
choices of starting policy will create this behavior.
Let us assume the followinginitial policy:
3 001 3
=f P=|0 1 0 a= [4
1 100 8
To evaluate this policy, we first apply Eqs. 6.3 and obtain

§1 = §3 2 = §2 §3 = §1
There are two recurrent chains. Chain 1 is composedof states 1 and
3, chain 2 of state 2 alone. Therefore, g1 = g3 = 1g, g2 = 2g, and we
may set ve = v3 = 0. Equations 6.4 then yield
lo + v, = 3 29 = 4 le =84+ v4

The solution of these equations is lg = 41, 9¢ = 4, v1 = —3, and so

gi =e g2 = 4 gs = "4
and
vi = —8 vg = 0 v3 = 0

Table 6.4 shows the policy-improvement routine.

Table 6.4. PorLicy IMPROVEMENT BY A CHANGE IN CHAIN STRUCTURE

State Alternative Gain Test Quantity Value Test Quantity
N N
i k >, Piske; qk + > pigtv;
j=l j=l

1 1 43 —¥
2 4 2
3 73 3<-

2 1 12 z
2 4 4
3 “e 5<
3 1 14 an
2 4 9
3 73 i<—

The policy improvement in this case was performed by means of

both gains and values. The gain test selected two alternatives in each
state, and the value test then decided between them. Thepolicy that
 PROPERTIES OF THE ITERATION CYCLE 69

has been producedis the optimal policy that was found earlier, and so
there is no need to continue the procedure because we would only
repeat ourearlier work.
In the preceding example we began with a two-chain policy and ended
with the optimal one-chain policy. The reader should start with such
1 1
policies as d = 2 and d = ; to see how the optimal policy with
3 1
gain 7 for all states may be reached by various routes. Note that in
no case is it necessary to use the true limiting values v;; the relative
values are adequate for policy-improvement purposes.

Properties of the Iteration Cycle

Weshall now show that the iteration cycle of Fig. 6.1 will lead to
the policy that has a higher gain in each state than any other policy.
Suppose that a policy A has been evaluated so that its gains and values
are known. The policy-improvement routine will use these gains and
values to produce a new policy B. Weneed to determine the relation-
ship between policies A and B.
If in state 7 the decision was made on the basis of gains, we know
that
N N

> Pibgit > > pudgy

j=1 j=
where superscripts A and B are used to denote the quantities pertaining
to each policy. In particular, we may define
N N

be = > disBoy4 — > payAgy4 (6.6)

j=1 j=1
The quantity dt; is greater than zero if the decision in the zth state is
based on gain and is equal to zero if it is based on values. If {; is equal
to zero, so that a value decision is made, we know that
N N

GB + > pisPr74 > gd + D puri

j=1 j=1
If we let
N N

yi =? + > PizPvj4 — it — > pis4v54 (6.7)

j=1 j=1
then y; > 0. If both ¥: and y: = 0, then the policies A and B are
equivalent as far as the test quantities in statez are concerned. Insuch
a case we would arbitrarily use the decision in statez pertaining to
policy A.
70 MULTIPLE-CHAIN PROCESSES

The policy-evaluation equations may now be written for both policies

A and B according to Eqs. 6.3 and 6.4. For policy A we have
N

git = > pistgiA

j=1
i= 1,2,---,N (6.8)
N
git + vid = gid + > piz4v; 7=1,2,---,N (6.9)
j=l

For policy B the correspondingrelations are

N
iF = > pizFeg? t= 1, 2,° vt, N (6.10)
j=l
N
eB + vB = ge + > pyBvjB 1=1,2,---,N (6.11)
j=1

Subtraction of Eq. 6.8 from Eq. 6.10 yields

N N

BiB — giA = > pij®ey® — > pudgiA

j=l j=1

If Eq. 6.6 is used to eliminate

N

>, Pidgi4
j=l

and welet gi4 = gi:8 — gid, then

N
gd =dit > pubA 1 =1,2,---,N (6.12)
j=l
Similarly, if Eq. 6.9 is subtracted from Eq. 6.11, we obtain
N N

geP — git + 1B — eA = GiB — ged + D pajBoj® — D pizAvj4

i= ist
Equation 6.7 may be used to eliminate g;? — gi4. Then if we let
vA = vz2 — v;4, we have
N
gAt+uAs=vet > pyFA i= 1,2,---,N (6.13)
j=1

Wehave now found that the changes in gains and values must satisfy
the two sets of equations (Eqs. 6.12 and 6.13). Equations 6.13 are
identical to Eqs. 6.4 except that they are written in terms of differences
in gain and value rather than the absolute quantities, and y:; appears
instead of gi. However, Eqs. 6.12 differ from Eqs. 6.3 because of the
term ;; otherwise, if b; were zero, Eqs. 6.12 would bear the same
relation to Eqs. 6.3 that Eqs. 6.13 bear to Eqs. 6.4. Let us investigate
further the nature of Eqs. 6.12.
 PROPERTIES OF THE ITERATION CYCLE 71

The policy B described by parameters #,;? and g;2 may of course have
many independent chains. If there are L recurrent chainsin the proc-
ess, then we are able to identify L groups of states with the property
that if the system is started in any state within a groupit will always
make transitions within that group. In addition there will bean L + Ist
group of transient states with the property that if the system is started
in any state of this group it will ultimately make a transition into one
of the Z recurrent chains. By a renumbering of states, it is possible
to write the matrix P# in the form

: 11p 0 0 0

ee oo
efooo)
are re
“aap| ap aptibap
The square submatrices 11p sap .., LLp are the transition matrices
for the chains 1, 2,---, £ after the renumbering; each is itself a stochas-
tic matrix. Submatrices of the form ’sP are composed of zero elements
ifv¢~sandrv4~Ll4+1. The submatrix 2+1,2+1P is the matrix of
transition probabilities among transient states. Some of the elements
of the submatrices 4+1,sP for s = 1, 2,---, L must be positive.
If the same renumbering scheme is used on the vectors g4, v4, , y,
and 7, we obtain a set of vectors composed of L + 1 subvectors; these
vectors are
gd lyA Iw ly
*g° “vA op ay

gv=| : ve=] : p=] : Y=]:

LgA LwA Ly Ly

L+1gA L+lyA Lt+ig Ltly

r= [17 : 2 : ...: Le: L+1z]

The vector x is the state-probability vector for the L-chain process.

Each subvector x is the limiting-state-probability vector if the system
72 MULTIPLE-CHAIN PROCESSES

is started in a state of the vth chain; "x = *x’’P, and the sum of the
components of each "x for 7 = 1,2,---,£is 1. The subvector 4t1x
has all components zero because all states in the group L + 1 are
transient.
Equations 6.12 and 6.13 in vector form are
gi =o + P8g4 (6.14)
git yi=y + PByA (6.15)
If the partitioned forms are used in Eq. 6.14, we obtain
rgh = mp + 7Prgd y=1,2,---,L (6.16)
and
L+1
L+lgA = L+lyy + > L+1,sP sgA (6.17)
s=1

Partitioning transforms Eq. 6.15 into

rgd + 7ryA = ™% + rrp ryA Y= 1, 2,° oy L (6.18)

and
L+1
LtlgA 4 L+lyA = Ltly 4 > L+1,sP syA (6.19)
s=1
Suppose that Eq. 6.16 is premultiplied by "x so that
Tac rgA = Tx rb + Tx7rp rgA

Since
To = Tre 7TP

it follows that
Txt) = 0 (6.20)
Becauseall states in the 7th chain are recurrent, "x containsall positive
elements. We know from ourearlier discussion that all |; are greater
than or equal to zero. From Eq. 6.20 we see that, in any of the 7
groups 7 = 1, 2,---, L, b; must be zero. It follows that in each re-
current chain of the policy B the decision in each state must be based
on value rather than gain.
Equations 6.16 thus become
rg — rrp rgd (6.21)

Weknow that the solution of these equationsis that all g;4 = "g4, so
that all states in the 7th group experience the same increase in gain as
the policy is changed from A to B. If this result is used in Eq. 6.18,
wefind that
tgh = Mary (6.22)
 PROPERTIES OF THE ITERATION CYCLE 73

Thus the increase in gain for each state in the 7th group is equal to
the vector of limiting state probabilities for the 7th group times the
vector of increases in the value test quantity for that group. Since,
for each group < L,; = 0, then"y; > 0. Equation 6.22 showsthat
an increase in gain for each recurrent state of policy B will occur un-
less policies A and B are equivalent.
Wehave yet to determine whetheror not the gain of the transient
states of policy B is increased. Equation 6.17 showsthat
L
(L+1] — L+1,L+1p)Lt+igA = Lt+ly + > L+1,sP sgA (6.23)
s=1

where “+11 is an identity matrix of the same size as the numberof

states in the transient group L + 1. Thechangein gain of the transient
states is thus given by
L
L+lgA — (471] — aa Ca + > L+1,sp | (6.24)
s=1

In the appendix it is shown that (£+1I — 14+1,2+1P)—1 exists and has

no negative elements. We know that all d; are greater than or equal
to zero, that some elements of the matrices 4+[Link] for s = 1,2,---, L
are positive and that none are negative, and that the changes in gain
for the Z recurrent groups cannot be negative. It follows that the
change in gain for all the transient states of group L + 1 cannot be
negative and will be positive if either or both of two conditions occur.
First, the gain of a transient state will increase if its probabilistic be-
havior is changed so that it is more likely to run into chains of higher
gain. Second, the gain of the transient state will increase if the gains
of the chains into which the transient state runs are increased.
Thus we have shown that under the iteration cycle of Fig. 6.1 the
gain of no state can decrease, and that the gain of some state must
increase unless equivalent policies exist. We have now to show that
the iteration cycle will find the policy that has highest gain in all states.
Suppose that policy B has higher gain in somestate than policy A,
but that the iteration cycle has converged on policy A. It follows that
all d; < 0, and that, if ¥; = 0, then y; < 0. Equation 6.22 shows that
all "g4 are nonpositive, so that no recurrentstate of policy B can have
a higher gain than the same state under policy A. Since Eq. 6.24
shows that all 4+t1g;4 are nonpositive, no transient state of policy B
can have a higher gain than the same state under policy A. Conse-
quently, no state can have a higher gain under policy B than it has
under policy A andstill have the iteration cycle converge on policy A.
We have thus shown that the iteration cycle increases the gain of
74 MULTIPLE-CHAIN PROCESSES

all states until it converges on the policy that has highest gain in all
states, the optimal policy.
The preceding discussion maybeillustrated by means of the multi-
chain example of Table 6.1. Recall the case when the policy
3 001 3
=f a 1 0 =|
1 10 0 8

fi] ok
changed to the policy

Oo ©
by means of the policy-improvement routine of Table 6.4. The first
policy we havecalled policy A, the second, policy B. From Table 6.4
wesee that

0 0
p= j y= {1
0 3
If the identity of states 3 and 1 is interchanged, we have

1/00 0 z “8”
P2—1/1:0 0O pb = i Y= { = be
1'0 0 0 0 8
Thus L = 1, there is one recurrent chain, and 11P = [1]. We notice
that in the new state 1 (the old state 3) the decision was based on values
rather than gains. The limiting-state-probability vector for s = 1,
1g, is [1]. Hence from Eq. 6.22
IgA =
boles

Since

22p _ 0 0
P F 0
we see from Eq. 6.24 that

ve = ys res = [i] + [3]= [3]

2 1

so that
 PROPERTIES OF THE ITERATION CYCLE 75

If now the renumbering of states 1 and 3 is reversed, the vector g4 is

unchanged. Hence wefind that, in going from policy A to policy B,
states 1 and 3 should have their gain increased by 3, while state 2
should have its gain increased by 3. Reference to the policy-evaluation
equations solved earlier for policies A and B showsthat this was indeed
the case.
Wehave seen that the multichain sequential decision process may be
solved by a method extremely analogous to that for single-chain
processes. However, in most practical problems knowledge of the
process enables us to use the simpler single-chain approach.
The Sequential Decision Process
with Discounting

In many economic systems the cost of money is very important.

We mightcriticize the automobile replacement problem of Chapter 5,
for example, because a dollar of expenditure in the future was given as
much weight as a dollar spent at the present time. This chapter will
overcome such criticisms by extending ouranalysis of sequential decision
processes to the case in which discountingof future returns is important.
Consider a Markov process with rewards described by a transition-
probability matrix P and a reward matrix R. Let the quantity B be
defined as the value at the beginning of a transition interval of a unit
sum received at the end of the interval. It follows that the discount
factor 8 must be the reciprocal of 1 plus the interest rate that is appli-
cable to the time interval required for a transition. For a nonzero
interest rate, 0 < 6 < 1.
Let us suppose that 7;; in such processesis received at the beginning
of the transition from 7 toj7. Then, if v;(”) is defined as the present
value of the total expected reward for a system in state 7 with » transi-
tions remaining before termination, we obtain

vi(n) = 2,bulls + Bun -—1)}) += 1,2,---,N

m= 1,2,3,--- (7.1)
by analogy with Eqs. 2.1. Once again we may usethe set of expected
immediate rewards
N

gi = > Putis
j=l
76
 DISCOUNTING 77

to obtain for the basic recurrencerelation

N
v;(”) = gi t+ B> pivi(n — 1) 1=1,2,---,N
j=1
nm = 1,2,3,--- (7.2)
Equations 7.2 may also be used to analyze processes where rewards
are received at the end of a transition rather than at the beginning.
All that is required is that we interpret g; as the expected present values
of the rewards received in the next transition out of state 7. In this
way we may use Eqs. 7.2 to analyze situations where rewards are
distributed in some arbitrary fashion over the transition interval.
Furthermore, Eqs. 7.2 may be used to analyze processes where
discounting is not present but wherethere is uncertainty concerning the
duration of the process. To seethis, let 8 be defined as the probability
that the process will continue to earn rewards after the next transition.
Then 1 — £6 is the probability that the process will stop at its present
stage. If the process receives no reward from stopping, then the Eqs.
7.1 and 7.2 still describe the process. It will thus not be necessary
in the following to distinguish between processes with discounting and
processes with indefinite duration.
Let v(m) be the vector of total expected rewards and q be the vector
of expected immediate rewards. Equations 7.2 may be written as
vim + 1) = q + BPv(n) (7.3)
If the vector v(z) is defined as the z-transform of the vector v(m), then
by the techniques of Chapter 1, we may take the z-transform of Eq. 7.3
to obtain the matrix equation

-lv(2) — v(0)] = ——
1-2 4 + BPv(2)
Then
v(z) — v(0) = 7 4 + BzPv()

(I — BzP)v(z) = ;— 4 + v(0)
and finally
v(z) = ~~ (I — BzP)“q + (I — BeP)-1v(0) (7.4)
Wehave thus found the z-transform of v(m). It is now possible to
find a closed-form expression for v(m) in any problem,so that it is not
necessary to rely on the recurrence relation (Eq. 7.3).
78 DISCOUNTING

Let us illustrate these results by applying them to the toymaker’s

problem of Table 3.1. Suppose that the toymaker is following the
policy
1 ft oy 6
a= [1] Aa @=|l
Heis not advertising and not conducting research. Suppose also that
for each weekthere is a probability of 4 that he will go completely out
of business before the next week starts. If he goes out of business, he
still receives his immediate rewards for the present week but receives
no other reward. The problem as stated fits our framework with
8 = 4. Weshall assume that v(0) = 0; therefore, if he does survive
for all m stages his business will have no value at that time.
For this problem, Eq. 7.4 becomes
z
v(z) = -— ; (I — BzP)~'q
Or

v(z) = #(z)q
where we consider #(z) to be the z-transform of a response function
H(z). Finally, v(z) = H(n)q.
We mustfirst find

3(2) = -— (1 - BP)
Since B = f,
1 _fi-z — 42
a-em =P a
and
1 — 2 dz
(1 — 32)(1 — goz) (1 — 32)(1 — 2)
(I — 4zP)-1 =
£2 —te
(1 — 32)(1 — goz) (1 — 32)(1 — 262)
Thus
2(1 — x62) 42"
(1 — z)(1 — 32)(1 — goz) (1 — 2)(1 — $2)(1 — go2)
H(z) =
be? “(1 — 2)
(1 — z)(1 — 32)(1 — gez) (1 — 2)(1 — $2)(1 — go)
 VALUE ITERATION 79

By partial-fraction expansion
1 (3 4), 1-8 -ae
0-5 ultimele al _8_
19 9
1
321 —
— =v
9
1 100 100
1 171
a=
20
80 i71
i71
se |
and
28 $10 __ 8 _ 10
_ |19 9 1\n 9 9
H(z) — iN 3 + (3) "3 “a
ig 1 9 9

+(f6)"| so _so.
__ 100 100
_1_\n 171 171
7 171

Since v(z) = H(n)q, the problem of finding v(m) has been solved for an
arbitrary q. Forq = |

138 _2 __ 100
ven) = |_| +| 73] + ore Ge
If the toymakeris in state 1 and has m possible stages remaining,
the present value of his expected rewards from the m stagesis v(m)
= 488 — 2(4)" — 4% (s6)". The corresponding quantity if he is in
state 2 is ve(m) = —f§ — 2(4)™ + 88(s5)". Note that v1(0) = vo(0)
= 0, as required. For v(0) = 0, Eqs. 7.2 show that v1(1) = 6 and
vo(1) = —3; these results are also confirmed by our solution. The
z-transform methodis thus a straightforward way to find the present
value of the future rewards of a process at any stage.
We note that as becomes very large vi(m) approaches 33% and
vo(m) approaches —7. For a process with discounting, the expected
future reward does not grow with as it did in the no-discounting case.
Indeed, the present value of future returns approaches a constant
value as ~ becomes very large. We shall have more to say of this
behavior.

The Sequential Decision Process with Discounting Solved by Value

Iteration
Just as we could use the value-iteration method to solve the sequential
decision process when discounting was not important, we may now use
it when discounting is important. We desire to find at each stage n
the alternative we should choose in each state to makev;(), the present
value of future rewards, as large as possible. By analogy with the
recurrence equation (Eq. 3.3) of the no-discounting case, we obtain
80 DISCOUNTING

for the case where discounting is important the equation

vin +1) = max ce + 6 >puter (7.5)

In this equation v;(7) is defined as the present value of the rewards

from the remaining stages if the system is now in state 7 and if the
optimal selection of alternatives has been performed at each stage
through stage . For each state, the alternative & that maximizes

qk + B >. Pig*v;(n)

is used as the decision for the zth state at stage m + 1, or di(m + 1).
Since the v;(m) are known for stage u, all the quantities needed to
make the test at stage » + 1 are at hand. Once v(0) is specified, the
procedure can be carried through to any stage desired.
Let us work the toymaker example described by Table 3.1. We shall
assume that B = 0.9, so that either the toymaker has an interest rate
on his operation of 11.1 per cent per week or thereis a probability 0.1
that he will go out of business in each week. The interest rate is
absurdly high, but it illustrates how such a problem is handled. If
transitions were made oncea year, such an interest rate might be more
realistic.
The solution of this problem with use of Eq. 7.5 is shown in Table
7.1. Once more we assume that v1(0) = v2(0) = 0.

Table 7.1. SOLUTION OF TOYMAKER’S PROBLEM WITH DISCOUNTING

USING VALUE ITERATION
n= 0 1 2 3 4
v1(n) 0 6 7.78 9.1362 10.461658
- v9(n) 0 3 —2.03 — 0.6467 0.581197
dy(n) — 1 2 2 2
do(n) — 1 2 2 2

As weshall soon prove, the total expected rewards v;() will increase
with ~ and approach the values vi(m) = 22.2 and ve(n) = 12.3 as n
becomes very large. The policy of the toymaker should be to use the
second alternative in each state if > 1. Since we have seen how the
v(m) approach asymptotic values for large , we might ask if there is
any way we can by-pass the recurrencerelation and develop a technique
that will yield directly the optimal policy for the system of very long
duration. The answer is that we do have such a procedure and that
it is completely analogous to the policy-iteration technique used for
 VALUE-DETERMINATION OPERATION 81

processes without discounting. Since the concept of gain has no

meaning when rewards are discounted, the optimal policy is the one
that produces the highest present value in all states. We shall now
describe the new formsthat the value-determination operation and the
policy-improvement routine assume. Weshall see that the sequential
decision process with discounting is as easy to solve as the completely
ergodic process without discounting. We need no longer be concerned
with the chain structure of the Markov process.

The Value-Determination Operation

Suppose that the system is operating under a given policy so that a
given Markov process with rewards has been specified. Then the
z-transform of v(m), the vector of present values of expected reward in
n stages, 1s given by Eq. 7.4 as
Zz
v(z) = (I — BzP)-1q + (I — BzP)—1v(0) (7.4)
1—2z
It was shown in Chapter 1 that (I — zP)—1 could be written in the form
[1/(1 — z)]S + 7 (z), where Sis the matrix of limiting state probabilities
‘and 7 (z) is the transformed matrix of componentsthat fall to zero as n
becomeslarge. It follows that (I — 6zP)—1 can be written in the form
1
(I — peP)-1 = - — Bz
S + F(z) (7.6)
and that 7 (8z) now refers to components that fall to zero even faster
as n grows large. Then Eq. 7.4 becomes

o@) = 775 gS + 7(6)|a + |g S+ 7089|¥O) (7.7)

z

Let us investigate the behavior of Eq. 7.7 for large n. The coefficient
of v(0) represents terms that decay to zero, so that this term disappears.
The coefficient of q represents a step component that will remain
plus transient components that will vanish. By partial-fraction
expansion the step component has magnitude [1/(1 — B)]S + 7(8).
Thus for large n, v(z) becomes {[1/(1 — z)][1/(1 — B)]S + 7(8)}q.
For large n, v(m) takes the form {[1/(1 — B)]S + 7(8)}q. However,
{[1/(1 — B)]S + 7 (B)} is equal to (I — BP)—1, by Eq. 7.6. Therefore,
for large n, v(m) approachesa limit, designated v, that is defined by
v = (I — BP) "q (7.8)
The vector v may be called the vector of present values, because each
of its elements v; is the present value of an infinite number of future
expected rewards discounted by the discount factor8.
8&2 DISCOUNTING

Wemayalso derive Eq. 7.8 directly from Eq. 7.3:

vin + 1) = q + BPv(n) (7.3)
If we write v(1), v(2), v(3),--- in explicit form, we find
v(1) = q + BPv(0)
v(2) = q + BPq + B?P?v(0)
(3) = q + BPq + B?P?q + BPFv(0)
<

The general form of these equationsis

v(n) = S (ePy|a + erPrv(0

Since 0 < 6 < 1,

lim v(m) = > (@P)’q

n—> oO j=0

Because P is a stochastic matrix, all of its eigenvalues are less

than or equal to 1 in magnitude. The matrix BP therefore has eigen-
values that are strictly less than 1 in magnitude because 0 < 6 < 1.
We may thus write > (@8P)i = (I — BP)-! and obtain lim v(z) = v =
j7=0 M—> CO

(I — BP)—q, or Eq.7.8.
The present value of future rewards in each stateis finite and equal
to the inverse of the (I — BP) matrix postmultiplied by the q vector.
Note for future reference that, since P is a matrix with nonnegative
elements, (I — ®BP)-1 = > (8P)3 must have nonnegative elements and,
j=0
moreover, must have numbersatleast as great as 1 on the main diagonal.
This result is understandable from physical considerations because a q
with nonnegative elements must produce a v with nonnegative elements.
Since no rewardsare negative, no present value can be negative.
Weare now in a position to describe the value determination itself.
Because weare interested in the sequential decision process for large n,
we may substitute the present values v; = lim v;(m) for the quantities
v(m) in Eq. 7.2 to obtain the equations
N

w= Gi tB> py t= 1,2,---,N (7.9)

j=l
For a given set of transition probabilities 4;; and expected immediate
rewards g:, we may use Eqs. 7.9 to solve for the present values of the
 POLICY-IMPROVEMENT ROUTINE 8&3

process. Weare interested in the present values not only because they
are the quantities that we seek to maximize in the system but also
because they are the key to finding the optimal policy, as weshall see
when we discuss the policy-improvement routine. —
Let us find the present values for 8 = 4 of the toymaker’s policy
defined by
P = 2 2 _ 6
“Tal t= [3
Equations 7.9 yield
v1 = 6 + 4u1 + jue Ve = —3 + $1 + Pove
The solution is v1 = 433, ve = —?¢%. These are the limiting values
for vi(m) and ve(m) found earlier.
Weshall now see how to use the present values for policy improve-
ment.

The Policy-[mprovement Routine

The optimal policy is the one that has highest present values in all
states. If we had a policy that was optimal up to stage n, according
to Eq 7.5 we should maximize

qi® + BD, pistos(n)

with respect to all alternatives & in the zth state. Since we are now deal-
ing only with processes that have a large number of stages, we may
substitute the present value v; for vj(m) in this expression. We must
now maximize
N

git + BD pista;
i=
with respect to all alternatives in the zth state.
Suppose that the present values for an arbitrary policy have been
determined. Then a better policy, one with higher present values in
every state, can be found by the following procedure, which wecall
the policy-improvement routine.
For each 2, find the alternative & that maximizes
N

gi* + BD pisko;
j=1
using the v; determined for the original policy. This & now becomes
the new decision in the zth state. A new policy has been determined
when this procedure has been performed for everystate.
The policy-improvement routine can then be combined with the
8&4 DISCOUNTING

value-determination operation in the iteration cycle shown in Fig. 7.1.

Value-Determination Operation
Use pi and q; for given policy to solve the set of equations
N
t= Ga +B > pir; a=1,2,---,N P|
j=l
for all present values vj.

Policy-Improvement Routine
For each state i, find the alternative k’ that maximizes
N

|| gk + =
> pagho; iq

using the present values v; from the previous policy. Then

k’ becomes the new decision in the ith state, q;*’ becomes qj,
and p;;*’ becomes p4.

Fig. 7.1. Iteration cycle for discrete decision processes with discounting.

The iteration cycle may be entered ineither box. An initial policy may
be selected and the iteration begun with the value-determination opera-
tion, or an initial set of present values may be chosen andtheiteration
started in the policy-improvementroutine. Ifthereisnoa priori basis for
choosing a close-to-optimal policy, then it is often convenientto start the
process in the policy-improvement routine withall v; set equal to zero.
The initial policy selected will then be the one that maximizes expected
immediate reward, a very satisfactory starting point in mostcases.
The iteration cycle will be able to make policy improvements until
the policies on two successive iterations are identical. At this point it
has found the optimal policy, and the problem is completed. It will
be shown after the example of the next section that the policy-improve-
ment routine must increase or leave unchanged the present values of
every state and that it cannot converge on a nonoptimal policy.

An Example
Let us solve the toymaker’s problem that was solved by value
iteration earlier in this chapter. The data were given in Table 3.1,
 AN EXAMPLE 85

and as before B = 0.9. We seek the policy that the toymaker should
follow if his rewards are discounted and he is going to continue his
business indefinitely. The optimalpolicy is the one that maximizesthe
present value of all his future rewards.
Let us choose as the initial policy the one that maximizes his
expected immediate reward. This is the policy formed by the first
alternative in each state, so that
1 0.5 0.5 6
os H P= lo Oe a* |_|
Equations 7.7 of the value-determination operation yield
vi = 6 + 0.9(0.5u1 + 0.5v2) vg = —3 + 0.9(0.401 + 0.6v2)
The solution is v; = 15.5, vg = 5.6. The policy-improvementroutine
is now used as shown in Table7.2.

Table 7.2. First Poticy IMPROVEMENT FOR TOYMAKER’S PROBLEM

WITH DISCOUNTING
State Alternative Value Test Quantity
N
1 k qik + > byko;
j=1
1 1 6 + 0.9[0.5(15.5) + 0.5(5.6)] = 15.5
2 4 + 0.9[0.8(15.5) + 0.2(5.6)] = 16.2<—

2 1 —3 + 0.9[0.4(15.5) + 0.6(5.6)] = 5.6

2 —5 + 0.9[0.7(15.5) + 0.3(5.6)] = 6.3<

The second alternative in each state provides a better policy, so that now

a= |] P= lor os] t= [|
The value-determination operation for this policy provides the
equations
v7, = 44 0.9(0.8v1 + 0).2v2) va = —5 + 0.9(0.73 + 0.3v2)

From these equations we find v; = 22.2, ve = 12.3.

Notice that there has been a significant increase in present values in
both states. The policy-improvement routine must be used once more
as we see in Table 7.3.
The policy-improvementroutine has found the samepolicy that it did
in the previous iteration, so that this policy must be optimal. The
second alternative in each state should be used if the present valuesof
both states are to be maximized. The toymaker should advertise and
do research even if faced by the 11.1 per cent interest rate per week.
86 DISCOUNTING
Table 7.3. SECOND PoLicy IMPROVEMENT FOR TOYMAKER’S PROBLEM
WITH DISCOUNTING
State Alternative Value Test Quantity
N
i k gi + BD pighy;
j=l

1 1 21.5
2 22.2<-

2 1 11.6
2 12.3<—

The present values of the two states under the optimal policy are 22.2
and 12.3, respectively; these present values must be higher than those
of any other policy. The reader should check the policies d = ,

and d = |: to make sure that this is the case.

We have seen that if the discount factor is 0.9 the optimal no-
discounting policy found in Chapter4 is still optimal for the toymaker.
Weshall say more about how the discount factor affects the optimal
policy after we prove the properties of the iteration cycle.

Proof of the Properties of the Iteration Cycle

Consider a policy A and its successor policy B produced by the
policy-improvement routine. Since 6 was generated from A, it follows
that
N N

gi® + BD pisBoj4 > ged + BD piydvy4 (7.10)

j=l j=1
in every statez. We also knowforthepolicies taken individually that
N

vid = gid + BD pistu;4 (7.11)

j=l
N

vB = qi® + BD pisFu,% (7.12)

j=l
Let
N N

vi = GF + BD dijPoj4 — GA — BD dasA0s4
j=1 j=1

Thus y; is the improvementin the test quantity that the policy-improve-

ment routine was able to achieve in the 7th state; from the preceding
 SENSITIVITY OF OPTIMAL POLICY TO DISCOUNT FACTOR 87

definition, y; > 0. If we subtract Eq. 7.11 from Eq. 7.12, we obtain

N N

vB — vi = GiB — gid + BD piy®vj — BD Pis4vsA

j=l j=l
N N N

Yi — BD PsPoj4 + BD pitnj4 + BD piPox?

j=l j=1 q=1 N

— BD
j=l
patos
If v;4 = v;® — v;,4, the increase in present value in the zth state, then
N

vid = yi + BD dizPoj4
j=1
This set of equations has the same form asouroriginal present-value
equations (Eq. 7.9), but it is written in terms of the zucrease in present
values. We know that the solution in vector form is
v4 = (I — BP8}-1y (7.14)
where y is the vector with components y;. It was shown earlier that
[I — BP#]-1 has nonnegative elements and has values of at least 1 on the
main diagonal. Hence, if any y; > 0, at least one v;4 must be greater
than zero, and no v;4 can be less than zero. Therefore, the policy-
improvement routine must increase the present values of at least one
state and cannot decrease the present values of anystate.
Is it possible for the routine to converge on policy A when policy B
produces a higher present value in some state? No, because if the
policy-improvement routine converges on A, then all y; < 0, and hence,
all v4 < 0. It follows that when the policy-improvement routine has
converged on a policy no other policy can have higher present values.

The Sensitivity of the Optimal Policy to the Discount Factor

The taxicab problem discussed in Chapter 5 was solved for discount
factors 8 ranging from 0 to 0.95 with intervals of 0.05. In this example,
1—8 might be considered to be the probability that the driver’s cab
will break down before his next trip. The optimal policy and present
values for each situation are shown in Table 7.4. Wesee that, although
the present values change as @ increases, the optimal policy changes
only as we pass certain critical values of 8. More detailed calculation
reveals that these critical values of 8 are approximately 0.13, 0.53, and
0.77. The solution for the optimal policy for different values of 6
is shown in Fig. 7.2. For 8 between 0 and 0.13, the first alternative in
each state is the optimal policy; the driver should cruise in every town.
88 DISCOUNTING
Table 7.4. OPTIMAL POLICY AND PRESENT VALUES FOR THE TAXICAB
PROBLEM AS A FUNCTION OF THE DiIscouNT FACTOR 6
Discount Factor Optimal Policy Decisions Present Values
B State 1 State2 State3 State1 State2 State3

0 1 1 1 8.00 16.00 7.00

0.05 1 1 1 8.51 16.40 7.50
0.10 1 1 1 9.08 16.86 8.05
0.15 1 2 1 9.71 17.46 8.67
0.20 1 2 1 10.44 18.48 9.38
0.25 1 2 1 11.27 =19.63 10.21
0.30 1 2 1 12.24 20.93 11.16
0.35 1 2 1 13.38 22.43 12.28
0.40 1 2 1 14.72 24.17 13.61
0.45 1 2 1 16.33 26.21 15.21
0.50 1 2 1 18.30 28.64 17.16
0.55 1 2 2 20.79 31.61 19.83
0.60 1 2 2 24.03 35.33 23.46
0.65 1 2 2 28.28 40.10 28.13
0.70 1 2 2 34.06 46.44 34.37
0.75 1 2 2 42.32 55.29 43.11
0.80 2 2 2 55.08 68.56 56.27
0.85 2 2 2 77.25 90.81 78.43
0.90 2 2 2 121.65 135.31 122.84
0.95 2 2 2 255.02 268.76 256.20

Region Region Region Region

I II III IV
Optimal Optimal Optimal Optimal
Policy Policy Policy Policy

1 1 1 2
oy 6= [2 =|) e= [2
1 1 2 2

0 0.13 0.77 1.0

Fig. 7.2. Optimal policy as a function of discount factor for taxicab problem.

For 6 > 0.77, the second alternative in each state is the optimal
policy; the driver should always proceed to the nearest stand. In
Region I, the policy that maximizes expected immediate reward is
optimal; in Region IV, the no-discounting policy is best. An inter-
mediate policy should be followed in Regions II andIII.
The behavior first described enables us to draw several conclusions
 THE AUTOMOBILE PROBLEM WITH DISCOUNTING 8&9

about the place of processes with discounting in the analysis of sequen-

tial decision processes. First, even if the no-discounting process
described earlier is the preferred model of the system, the present
analysis will tell us how large the discounting element of the problem
must be before the no-discounting solution is no longer applicable.
Second, one criticism of a model that includes discounting is the
frequent difficulty of determining what the appropriate discount rate
should be. Figure 7.2 shows us that if the uncertainty about the
discount rate spans only one of our regions, the same policy will be
optimal, and the exact discount rate will affect only the present values.
Third, because it becomesincreasingly difficult to solve the process
using discounting when @ is near 1, in such a situation we are better
advised to solve the problem for the optimal policy without discounting.

The Automobile Problem with Discounting

The automobile replacement problem discussed in Chapter 5 was
solved using a discount factor 8B = 0.97. This discount factor corre-
sponds to an annual interest rate of approximately 12 per cent,a fairly
realistic cost of money for the average car purchaser. Kecall that the
optimal no-discounting policy was found in seven iterations and that
it was to buy a 3-year-old car and keep it until it was 64 years old.
The optimal policy with discounting was found in nineiterations; it is
to buy a 3-year-old car and trade it when it is 62 years old. The
optimal no-discounting and discounting policies are very similar—
if the 3 to 64 policy is evaluated with a discount factor B = 0.97, its
present values differ negligibly from those of the 3 to 62 policy. This
result emphasizes the point made above that the no-discounting policy
is often adequate for relatively low interest rates.
The present values of the optimal policy with discounting are of
interest ; they are presented in Table 7.5, along with the decision in
each state. Note that if we have a car less than 1 year old we should
trade it for a 3-year-old car. The present values are negative be-
cause they represent a discounted stream of future costs. The present
value of a l-year-old car is — $4332, while the present value of a
4-year-old car is — $4946. These figures tell us that if we have a
4-year-old car we should depart from our optimal 3 to 62 policy if
we can trade it for a 1-year-old car and pay less than (— $4332)
— (— $4946) = $614. In the no-discounting case the corresponding
quantity was $730, so that we were somewhat morewilling to make such
a trade when the cost of money was not important.
An interesting business opportunity is presented by Table 7.5. It
appears that for a cash deposit of about $5000 some entrepreneur
90 DISCOUNTING

Table 7.5. OPTIMAL POLICY AND PRESENT VALUES OF AUTOMOBILE

REPLACEMENT PROBLEM FOR DiscounT Factor 8 = 0.97
State: Age of Car in
Quarterly Periods Decision Present Value

Trade for 12-period car — $3925

Trade for 12-period car — $4045
Trade for 12-period car — $4155
Keep present car — $4332
Keep present car — $4398
Keep present car — $4462
Keep present car — $4523
Keep present car — $4581
Keep present car — $4635
Keep present car — $4688
Keep present car — $4738
Keep present car — $4785
Keep present car — $4829
Keep present car — $4870
Keep present car — $4909
Keep present car — $4946
Keep present car — $4979
Keep present car — $5011
Keep present car — $5041
Keep present car — $5069
Keep present car — $5096
Keep present car — $5121
Keep present car — $5145
Keep present car — $5167
Keep present car — $5186
Keep present car — $5202
Trade for 12-period car — $5215
Trade for 12-period car — $5225
Trade for 12-period car — $5235
Trade for 12-period car — $5240
Trade for 12-period car — $5245
Trade for 12-period car — $5250
Trade for 12-period car — $5255
Trade for 12-period car — $5265
Trade for 12-period car — $5270
Trade for 12-period car — $5275
Trade for 12-period car — $5280
Trade for 12-period car — $5290
Trade for 12-period car — $5298
Trade for 12-period car — $5305

should be willing to supply us with the use of a car between 3 and 63

years old forever. In order to make the deal more appealing to him,
we might make the deposit $6000 and allow him some profit. How
unusual it would be to pay for a lifetime of car ownership in advance
 SUMMARY 91

rather than by an unending stream of time payments and gasoline

bills.

Summary
The solution of sequential decision processes is of the same order of
difficulty whether or not discounting is introduced. In eithercaseit is
necessary to solve repeatedly a set of linear simultaneous equations.
Each solution is followed by a set of comparisons to discover an 1m-
proved policy; convergence on the optimal policy is assured. Dis-
counting is useful when the cost of money is important or when there is
uncertainty concerning the duration of the process.
The Continuous-lime
Decision Process

In the previous chapters we have been discussing Markov processes

that make state transitions at discrete, uniformly spaced intervals of
time. In this chapter we shall extend our previous work to the case
in which the process may make transitions at random timeintervals.

The Continuous-Time Markov Process

The first problem we face is how to describe an N-state process whose

time between transitions is random. Reflection shows that the sig-
nificant parameters of the process must be transition rates rather than
transition probabilities. Let us call a; the transition rate of a process
from state z to state7, forz #7. The quantity a; 1s defined as follows:
In a short time interval d, a process that 1s now in state z will make a
transition to state 7 with probability a;; dt (1 #7). The probability of
two or more state transitions is of the order of (dt)? or higher and is
assumedto be zeroif dt is taken sufficiently small. The correspondence
between this definition and the assumptions of the Poisson process
should be clear. We shall consider only those processes for which the
transition rates aj; are constants, an assumption equivalent in the dis-
crete-time case to the assumption that the transition probabilities do
not change with time. We may now describe the continuous-time
Markov process by a transition-rate matrix A with components 4a;;;
the diagonal elements have not yet been defined.
The probability that the system occupies state z at a time ¢ after the
start of the process is the state probability x,(¢) by analogy with 7x;(7).
92
 CONTINUOUS-TIME MARKOV PROCESS 93

We mayrelate the state probabilities at time ¢ to those a short time

dt later by the equations

ni(é + dt) = 7;(t) 1 — > ays it + Dnil)aydt 7 =1,2,---,N (8.1)

t#j t#ij
There are two mutually exclusive ways in which the system can
occupy the state 7 at ¢ + di. First, it could have been in state 7 at time
¢ and made no transitions during the interval dt. These events have
probability z;(¢) and 1 — > a;;, at, respectively, because we have said
tJ
that the probability of multiple transitions 1s of order higher than dz
and is negligible, and because the probability of making no transition
in dt is 1 minus the probability of making a transition in dt to some
state 2 #7. The second way the system could be in state 7 at ¢ + dt
is to have been at state 2 4 7 at time ¢ and to have madea transition
from 2 to state 7 during the time di. These events have probabilities
mi(t) and ay dt, respectively. The probabilities must be multiplied
and added over all z that are not equal to 7 because the system could
have entered 7 from any other state z. Thus we see how Eq. 8.1 was
obtained.
Let us define the diagonal elements of the A matrix by

ayy = — >, ay (8.2)

t#j
If Eq. 8.2 is used in Eq. 8.1, we have
75 (¢ + dt) = 7; (2)[1 + Ajj at| + > t4(t) ai; at
tH#j
Or
N
y(t + dt) — r;(t = 27(t)aaj dt

Upon dividing both sides of this equation by dt and taking the limit
as dt > 0, we have
N
£ il) = > (2) ai; = 1, 2,° vy N (8.3)
t=1

Equations 8.3 are a set of N linear constant-coefficient differential

equations that relate the state probabilities to the transition-rate
matrix A. The initial conditions 7;(0) for 7 = 1, 2,---,N must be
specified if a solution is to be obtained.
Wesee that the transition-rate matrix A for continuous-time proc-
esses plays the same central role that the transition-probability matrix
P played for discrete-time processes. However, we now havea set of
94 THE CONTINUOUS-TIME DECISION PROCESS

differential equations (Eqs. 8.3) rather than a set of difference equations

(Eqs. 1.2). In matrix form we may write Eqs. 8.3 as
ad
qn) = (Z)A (8.4)

where 7(¢) is the vector of state probabilities at time ¢. The matrix

A is of itself interesting. The off-diagonal elements of A are given by
the transition rates of the process. The diagonal elements of A are
given by Eq. 8.2. Asa result the rows of A sum to zero, or
N
> ay = 0
j=1

As mentioned earlier, a matrix whose rows sum to zero 1s called a

differential matrix. As we shall see, the differential matrix A is a
very close relative of the stochastic matrix P.
In the following section we shall discuss the use of Laplace transforms
in the solution of continuous-time Markov processes described by Eq.
8.4. Weshall find that our knowledge of discrete-time Markov processes
will be most helpful in our new work.

The Solution of Continuous-Time Markov Processes by Laplace Trans-

formation
The Laplace transform of a time function /(¢) which is zero for ¢ < 0
is defined by

f(s) = |“f(estat (8.5)

The Laplace transform exists for any such time function that does
not grow faster than exponentially. Consider, for example, the
function f(t) = e-% fort > Oand/(t) = Ofort < 0. Using Eq. 8.5, we
find

f(s) = [,0eterna = {0* g-(stayt = I

S+a

Table 8.1 shows some typical time functions and their corresponding
Laplace transforms derived using Eq. 8.5.
The properties of Laplace transforms are widely known and are
thoroughly discussed in such references as Gardner and Barnes.2 The
Laplace transform of a time function is unique; there is a one-to-one
correspondence between the time function and its Laplace trans-
formation. These transforms are particularly suited to the analysis
of systems that can be described by linear constant-coefficient differ-
ential equations.
 SOLUTION BY LAPLACE TRANSFORMATION 95
Table 8.1. LAPLACE TRANSFORM PAIRS
Time Function for ¢ > 0 Laplace Transform

F(é) f(s)
filt) + felt) fils) + fas)
bf (t) (k is a constant) kf (s)

Slt) f(s) - £0)

eat !
S+a

1 (unit step) :

“a
teat G+1 ape

t (unit ramp) <

s
e~atf(t) f(s + a)

The continuous-time Markov process is described by Eq. 8.4, so we

should expect Laplace transformations to be useful in the solution of
such a process. Let us designate by II(s) the Laplace transform of
the state-probability vector zm(¢). The Laplace transform of any
matrix of time functions is the matrix of the Laplace transformsof the
individual time functions. If we take the Laplace transform of Eq.8.4,
we obtain

Or
II(s)(sI — A) = x(0)
where I is the identity matrix. Finally, we have
II(s) = x(0)(sI — A)-1 (8.6)
The Laplace transform of the state-probability vector is thus the
initial-state-probability vector postmultiphed by the inverse of the
matrix (sI — A). The matrix (sI — A)-1 is the continuous-process
counterpart of the matrix (I — zP)-1. Weshall find that it has proper-
ties analogous to those of (I — zP)—1 and that it constitutes a complete
solution of the continuous-time Markov process.
By inspection, wesee that the solution of Eq. 8.4 is
m(t) = m(O)eAt (8.7)
where the matrix function e4t is to be interpreted as the exponential
series
¢2 t3
P+ iA + —_
5 31
A2@+4 A384...
96 THE CONTINUOUS-TIME DECISION PROCESS

which will converge to e44. For discrete processes, Eqs. 1.4 yielded
m(n) = 7(0)P” n = 0,1, 2,--- (1.4)
Suppose that we wish to find the matrix A for the continuous-time
process that will have the same state probabilities as the discrete
process described by P at the times ¢ = 0, 1, 2,---, where a unit of
time is defined as the time for one transition of the discrete process.
Then, by comparison of Eqs. 8.7 and 1.4 when ¢ = n, wesee that
eA = P
or
A=InP (8.8)
Kecall the toymaker’s initial policy, for which the transition-proba-
bility matrix was
1 1
p=|; ||5 5.

Suppose that we should like to find the continuous process that will
have the same state probabilities at the end of each week for an
arbitrary starting position. Then we would have to solve Eq. 8.8
to find the matrix A. Methods for accomplishing this exist,* and if we
apply them to the toymaker’s P we find
In 10 ,—5 5
aaa oa
Since the constant factor (In 10)/9 is annoying from thepoint of view of
calculation, we may as well solve a problem that 1s analogous to the
toymaker’s problem but that is not encumbered by the constants
necessary for complete correspondence in the sense just described. We
shall let A be simply

A=|"7
—5
jl5 (8.9)
Since we are abandoning complete correspondence, we may as well
treat ourselves to a change in problem interpretations at the same time.
Weshall call this new problem “the foreman’s dilemma.”’ A machine-
shop foreman has a cantankerous machine that may be either working
(state 1) or not working (state 2). Ifit is working, there is a probability
5 dt that it will break down in a short interval d?; if it is not working,
there is a probability 4d¢ that it will be repaired in dt. We thus
obtain the transition-rate matrix (Eq. 8.9). The assumptions regarding
breakdown andrepair are equivalent to saying that the operating time
between breakdowns is exponentially distributed with mean ¢, while
 SOLUTION BY LAPLACE TRANSFORMATION 97

the time required for repair is exponentially distributed with mean }.

If we take 1 hour as our time unit, we expect a breakdown to occur
after 12 minutes of operation, and we expect a repair to take 15 minutes.
The standard deviation of operating and repair times is also equal to
12 and 15, respectively.
For the foreman’s problem we would like to find, for example, the
probability that the machine will be operating at time ¢ 1f it is operating
when ¢ = 0. To answer such a question, we must apply the analysis
of Eq. 8.6 to the matrix (Eq. 8.9). We find
P
I-az=\l|st 5 —5
st | —4 saa
rs +4 5
it Ay s(s + 9) s(s + 9)
Si — a

4 s+ 5
|s(s + 9) s(s + 9)
Partial-fraction expansion permits
$$ &, -8
ss) 549 st sa 9
(sl — A)-1 =
$ -$ $, 4
st 549 ss 4 9
Or

(t— ayt = 2[f il + 1 $ “4

3 3] s+9l-s §
Let the matrix H(t) be the inverse transform of (sI — A)-!. Then
Eq. 8.6 becomes by meansof inverse transformation
a(t) = 7(0)H(¢) (8.10)
By comparing Eqs. 8.7 and 8.10, we see that H(t) is a closed-form
expression for e4¢,
For the foreman example,
P olen

.9 9

The state-probability vector z(¢) may be obtained by postmultiplying

the initial-state-probability vector z(¢) by the matrix H(¢). If the
machine is operating at ¢ = 0, so that x(0) =[1 0], then x(¢) =
[fs a] + eS —3] or mt) = § + ge", malt) = 3 — ge-%. Both
mi(4) and ro(t) have a constant term plus an exponentially decaying
98 THE CONTINUOUS-TIME DECISION PROCESS

term. The constant term represents the limiting state probability as ¢

becomesvery large. Thus the probability that the machineis operating,
mi(t), falls exponentially from 1 to § as ¢ increases. The time constant
for this exponential decay is 5.
Similarly, if the machine jis not working at ¢ = 0, x(0) = {0 1],
and m(é) = [$ §] + e-™[-$ $],so that m(t) = $ — $e-, mld) —§ +
se-%t. Note that the probability that the machine is workingrises
exponentially from 0 to its steady-state value of § as ¢ becomeslarge.
The limiting state probabilities of the process are ¢ and 3 for states
1 and 2, respectively. They are independent of the state of the system
at z = 0.
The similarity between the discrete-time and continuous-time Markov
processes is now apparent. Both have limiting state probabilities and
transient components of probability. The transients in the discrete
case were geometric; in the continuous case they are exponential. The
matrix (sI — A)~! will always have one term of the form 1/s times a
stochastic matrix §. This is true becauses is a factor of the determinant
of (sI — A); a differential matrix always has one characteristic value
that equals zero. The stochastic matrix S is the matrix of limiting-
state-probability vectors, as it was in the discrete case. The zth row
of S is the limiting-state-probability vector of the processif it is started
in the 7th state. The remarks concerning recurrent chainsstill apply
in the continuous-time process.
The remaining terms of (sI — A)~! represent transient components
of the form e—4t, te-#t, and so on, that vanish for large ¢. The matrices
multiplying these components are themselves differential matrices.
We maycall 7 (s) the transient part of (sI — A)—! and write

(SI — A)-1 = =S + F(s) (8.11)

Or

H(t) = S + T(é) (8.12)

where S$ is the stochastic matrix of limiting state probabilities and
T(¢) contains the transient components of probability. For the fore-
man’s problem
4 5 5 _5
s=[? 3]
9 9
ta =e%[ —9fF G
9
The rows of S are identical because the process is completely ergodic.
It is not necessary to find (sI — A)-1if only the limiting state proba-
bilities are required. Suppose that the process is completely ergodic.
Since the limiting state probabilities are constants, we know that
 CONTINUOUS-TIME MARKOV PROCESS WITH REWARDS 99

dx(t)/dt = 0 for large ¢. If we denote the limiting-state-probability

vector by a, then Eq. 8.4 becomes
0=7A (8.13)
This set of simultaneous equations plus the requirement
N
> = 1 (8.14)
t=)

is sufficient to determine the limiting state probabilities. For the

matrix A (Eq. 8.9) we have from Eq. 8.13
—5n1 + 4nmo = 0 521 — 4nr2 = 0
and from Eq. 8.14
T1 + TM? = 1

The solution of these equations is m = $, mz = 3, in accordance

with our earlier results.

The Continuous-Time Markov Process with Rewards

Just as the notion of continuous time made us think in terms of

transition rates rather than transition probabilities, so we must redefine
the concept of reward. Let us suppose that the system earns a reward
at the rate of 7;; dollars per unit time duringall the timethat it occupies
statez. Suppose further that when the system makesa transition from
state 2 to state 7 (2 # 7) it receives a reward of 7;; dollars. (Note that
vi; and 7:; have different dimensions.) It is not necessary that the
system earn according to both reward rates and transition rewards, but
these definitions give us generality.
Weare interested in the expected earnings of the system if it operates
for a time ¢ with a given initial condition. If welet v;(¢) be the expected
total reward that the system will earn in a time ¢ if it starts in state 2,
then we can relate the total expected reward ina time? + dt, v;(t + dt),
to vi(t) by Eq. 8.15. Here dt represents, as before, a very short time
interval :
vi(t + dt) = | 1 - > aij ai\irss dt + v,(t)| + > aij atlrsy + v;(t) | (8.15)
j#t jHt
Equation 8.15 may be interpreted as follows. During the time
interval dt the system may remain in state 7 or make a transition to
some other state 7. If it remains in state 2 for a time d, it will earn a
reward 7;; dt plus the expected reward that it will earn in the remaining
¢ units of time, v;(¢). The probability that it remains in state 7 for a
time dt is 1 minus the probability that it makes a transition in dt, or
100 TRE CONTINUOUS-TIME DECISION PROCESS

1 — > aij at. On the other hand, the system may make transition
j#t
to some state 7 # 2 during the time interval dt with probability a,j dz.
In this case the system would receive the reward 7;; plus the expected
reward to be madeif it starts in state 7 with time ¢ remaining, v,(t). The
product of probability and reward must then be summed overall
states; # 2 to obtain the total contribution to the expected values.
Using Eq. 8.2, we may write Eq. 8.15 as
vi(t + dt) = (1 + Av dt) res dt + v;(2) | + > aij atlrij + v;(t)]
jHt
or

valt + dt) = Vii dt + v4(t) + aii; (t) dt + > Asiij dt + > AizV;(t) at
j#t jH#t

where terms of higher order than dt have been neglected. Finally, if

we subtract v;(¢) from both sides of the equation and divide by d?, we
have
ui(t
i( + at)
> — u,(t ~
i(2) = 75 + 2, ir + 2, aijzv;(t)

If we take the limit as di — 0, we obtain

a N
di vi(t) = 4 + > Arig + > aizv;(C) = 1, 2, ce, N
j#t j=l

We now have a set of N linear constant-coefficient differential

equations that completely define v;(t) when the v;(0) are known. Let
us define a quantity q; as the “‘earning rate”’ of the system where

qt = tu + > Ais?ij (8.16)

j#t
In the foreman’s problem, for example, the machine might have
earning rates g1 = 6,g2 = —3. These earning rates could be composed
of many different combinations of reward rates and transition rewards.
Thus, if the reward rate in state 1 is $6 per unit time, the reward rate
in state 2 is — $3 per unit time, and there is no reward associated with
transitions, then 711 = 6, 72g = —3, 712 = 721 = 0, and weobtain the
earning rates just mentioned. In a later section we consider the q;
to be obtained partly from transition rewards, but for the momentit
makes no difference.
With useof the definition of earning rate, our equations become
d N
a vil) = a4 + 2,aril 6=1,2,---,N (8.17)
j
 CONTINUOUS-TIME MARKOV PROCESS WITH REWARDS 101

Equations 8.17 are a set of linear, constant-coefficient differential

equations that relate the total reward in time ¢ from a start in state 1
to the quantities g; and aj. If v(¢) is designated as the column vector
with elements v;(¢), the total expected rewards, and if q is designated
as the earning-rate vector with components g;, then Eqs. 8.17 can be
written in matrix form as

Sv) =4 + Avi (8.18)

To obtain a solution to Eq. 8.18, we must of course specify v(0).
Since Eq. 8.18 is a linear constant-coefficient differential equation,
the Laplace transform should provide a useful method of solution.
If the Laplace transform of Eq. 8.18 is taken according to Table 8.1,
we have

sv(s) — v(0) = 4 + Av(s)

or

(sI — A)v(s) = -q + v(0)

and finally
Hm |

v(s) = —(sI — A)—1q + (sI — A)~-1v(0) (8.19)

Thus we find that Eq. 8.19 relates v(s), the Laplace transform of
v(t), to (sI — A)~1, the earning-rate vector q and the termination-
reward vector v(0), respectively. The reward vector v(¢) may be found
by inverse transformation of Eq. 8.19.
Let us apply the result (Eq. 8.19) to the foreman’s problem. The
transition-rate matrix and reward vector are

—5 5 6
Pa ea] 8 [2
A — =

Weshall assume that the machine will be thrown away at ¢ = 0, so that

vi(0) = v2(0) = 0. We found earlier that for this problem

s+4 5
s(s + 9) s(s + 9)
(sI — A)-1 =
4 s+5
s(s + 9) s(s + 9)
102 THE CONTINUOUS-TIME DECISION PROCESS

To use Eq. 8.19, we must find (1/s)(sI — A)-!. This is

StH 5
1 s2(s + 9) s2(s + 9)
“(I — A)! =
4 s+5
s#(s + 9) s2(s + 9)
Using partial-fraction expansion, we obtain

i
S484
9
s2
$i —37
s+ 9
a
3
s2
+ ~ 81
S
+ eT
s+ 9
—(sI — A)-! =
4 _4 4 5 4 _ AL
9 4 781, 31 9 4 8r 81

oH LE Hort AL
S

4 5 3 _5 _—58 3B 6
$3 —8r 0 i —s8irjJJL—3
or

1 5 _5
v(t) = | + + os|
] —%3 3
The total expected reward in time ¢ if the system is started in state 1
is thus
vi(t) =t + § — ge-
and if started in state 2 is
ve(t) = t — § + ge-%
Note that regardless of the starting state the machinewill earn, on the
average, $1 per unit time when ¢ is large because the coefficient of ¢
in both vi(¢) and ve(t) is 1. The average reward per unit time for a
system is called the gain of the system by analogy with the discrete-
time case. As before, the gain will depend uponthestarting state if the
system is not completely ergodic. We also see that for large ?, v1(t)
and v2(t) may be written in the form v,(t) = git + v4; in the abovecase,
v1 = 3, vg = —§. Let us prove that this relation holds for a general
continuous-time Markovprocess.
Equation 8.19 is

v(s) = 2 (oI ~ A)-1q + (sI — A)-1v(0) (8.19)

 CONTINUOUS-TIME MARKOV PROCESS WITH REWARDS 103

We know from Eq. 8.11 that

1
(I — A)" = -S + F(s) (8.11)
whereS is the matrix of limiting state probabilities and 7 (s) consists of
transforms of purely transient components. If Eq. 8.11 is substituted
into Eq. 8.19, we have

v(s) = . |; S + 7/4 + |; S 4 F(8)|¥(0

Or

v(s) = +84 + : T(s)q + : Sv(0) + F(s)v(0) (8.20)

Weshall investigate the behaviorof v(t) for large t by determining the
behavior of each component of Eq. 8.20. The term (1/s?)Sq represents
a ramp of magnitude Sq. The second term (1/s).7 (s)q refers to both
step and exponential transient components. The transient components
vanish for large ¢; the step component has magnitude 7 (0)q. The
term (1/s)Sv(0) represents a step of magnitude Sv(0); the term 7 (s)v(0)
refers to transient components that vanish forlarge 7.
Thus when# is large, v(t) has the form
v(t) = Sq + 7(0)q + Sv(0) (8.21)
If a vector g of state gains g; is defined by
g = Sq (8.22)
and if a vector v with components v; is defined by
v = J(0)q + Sv(0) (8.23)
then Eq. 8.21 becomes
v(t) =tig +v for large ¢ (8.24)
Or
vi(t) = tgs + v0 for large ¢ (8.25)
Wesee that the total expected reward in time¢ for a continuous-time
system started in state 7 has the same form as the corresponding
quantity in the discrete-time case (Eq. 2.15) except that » has been
replaced by ?. For the foreman’s problem,

4
_5
coh» colon

ot — aya = 27?> :| + I |
s+9 4
9 9 9

1
==-S$+ Fs)
S
104 THE CONTINUOUS-TIME DECISION PROCESS

so that

| 7-8

wmlor colon
eC"
N
|
81 81

In addition, q = —3
| From Eq. 8.22, we have g = Sq = |:
1
5
and from Eq.8.23, since v(0) = 0, we have v = J(0)q = ‘|:

©
Therefore by Eq. 8.25, it follows that for large ¢ we may write v1/(t)
and ve(t) in the form
vilt) = ¢ + 3 ve(t) = t — §

These expressions agree with those found previously.

Wehave now completed our analysis of the continuous-time Markov
process with given earning rates in each state. The reader should
compare the results of the foreman’s problem analyzed in this section
with those found for the analogous toymaker’s problem in order to
understand clearly the similarities and differences of discrete and
continuous-time Markov processes. Weshall now turn toa study of the
continuous-time decision problem.

The Continuous-Time Decision Problem

Suppose that our machine shop foreman has to decide upon a main-
tenance and repair policy for the machinery. When the system is in
state 1, or working, the foreman must decide what kind of maintenance
he will use. Let us suppose that if he uses normal maintenance pro-
ceduresthefacility will earn $6 per unit time and will have a probability
5 dt of breaking down in a short time @. Note that this is equivalent
to saying that the length of operating intervals of the machine is
exponentially distributed with mean 3.
The foreman also has the option of a more expensive maintenance
procedure that will reduce earnings to $4 per unit time but will also
reduce the probability of a breakdown in di to 2dt. Under neitherof
these maintenance schemes is there a cost associated with the break-
down per se. If we number the two alternatives in state 1 as 1 and 2,
respectively, then we havefor the first alternative
aio) = 5 ri1} = 6 7121 = 0
and for the second alternative
ajo? = 2 ru? = 4 rie = 0
Finally, we obtain by using Eq. 8.16 that
gii=6 and qi?=
 CONTINUOUS-TIME DECISION PROBLEM 105

Now we must consider what can happen when the machinery is not
working and the system occupies state 2. Let us suppose that the
foreman also has two alternatives in this state. First, he may have the
repair work done by his own men. Forthis alternative the repair will
cost $1 per unit time that the men are working, plus $0.50 fixed charge
per breakdown, and there is a probability 4 dt that the machine will
be repaired in a short time dé (repair time is exponential with mean }).
The parametersof this alternative are thus
ao11 = 4 7991 = —] Y911 = —0.5

and using Eq. 8.16, we have

gzt = —1 + (4)(-0.5) = -3
The second alternative for the supervisor when the machineis not
working is to use an outside repair firm. For this alternative the fixed
charge per breakdown is the same, $0.50. However, these men will
cost $1.50 per unit time, but will increase the probability of a repair in
dt to 7 dt. Thus, for this alternative
ae? = 1992 = —1.5 7912 = —0.5

and
go? = —1.5 + 7(-0.5) = —5
The foreman must decide which alternative to use in each state in
order to maximize his profitsin the long run. The data for the problem
are summarized in Table 8.2.

Table 8.2. THE FOREMAN’S DILEMMA

State Alternative Transition Rate Earning Rate
i k CF aigk qik
1 (Facility 1 (Normal maintenance) —5 5 6
operating) 2 (Expensive maintenance) —2 2 4

2 (Facility 1 (Inside repair) 4 —4 —3

out of order) 2 (Outside repair) 7 —7 —5

The concepts of alternative, decision, and policy carry over from the
discrete situation. Since each of the four possible policies contained
in Table 8.2 represents a completely ergodic process, each has a unique
gain that is independent of the starting state of the system. The
foreman would like to find the policy that has highest gain; this is the
optimalpolicy.
One wayto find the optimal policy is to find the gain for each of the
four policies and see which gain is largest. Although this is feasible
106 THE CONTINUOUS-TIME DECISION PROCESS

for small problems, it is not feasible for problems that have many
states and manyalternativesin eachstate.
Note also that the value-iteration method available for discrete-time
processesis no longer practical in the continuous-time case. It is not
possible to use simple recursive relations that will lead ultimately to the
optimal policy because we are now dealing with differential rather than
difference equations.
A policy-iteration method has been developed for the solution of the
long-duration continuous-time decision problem. It is in all major
respects completely analogous to the procedure used in discrete-time
processes. As before, the heart of the procedure is an iteration cycle
composed of a value-determination operation and a policy-improvement
routine. Weshall now discuss each section in detail.

The Value-Determination Operation

For a given policy the total expected reward of the system in time
tis governed by Eqs. 8.17

© vd(t = Gi +> aizv;(t) 1=1,2,---,N (8.17)

Since we are concerned only with processes whose terminationis remote,

we may use the asymptotic expression (Eq. 8.25) for v;(¢)
vi(t) = igi + UV; for large t (8.25)

and transform Eqs. 8.17 into

N

g= gi + 2, wiltes + v5)
J
Or
N N

g= gi tt> anges t+ dav; i= 1,2,---,-N (8.26)

j=1 j=1

If Eqs. 8.26 are to hold for all large ¢, then we obtain the twosetsof
linear algebraic equations
N
> ag; = 0 i=1,2,---,N (8.27)
4=1
N
B= G+ day 1=1,2,---,N (8.28)
j=
Equations 8.27 and 8.28 are analogous to Eqs. 6.3 and 6.4 for the
discrete-time process. Solution of Eqs. 8.27 expresses the gain of
each state in terms of the gains of the recurrent chains in the process.
 POLICY-IMPROVEMENT ROUTINE 107

The relative value of one state in each chain is set equal to zero, and
Eqs. 8.28 are used to solve for the remaining relative values and the
gains of the recurrent chains.

The Policy-Improvement Routine

Suppose that we have a policy that is optimal when ¢ units of time
remain, and that this policy has expected total rewards v;(¢). If we are
considering what policy to follow if more time than ¢is available, we
see from Eqs. 8.17 that we may maximize ourrate of increase of v;(¢) by
maximizing
N

qi® + > aaskv;(t) (3.29)

j=1
with respect to the alternatives k in state. If? is large, we may use
v(t) = ig; + v; to obtain
N

gk + > ask(tg; + v5)

j=1

Or
N N

gk + j=1
> aajhos + t j=1
> aashg; (8.30)
as the quantity to be maximized in the7zth state. For large ?, Expression
8.30 is maximized by the alternative that maximizes
N

>, a9*g; (8.31)

j=1
the gain test quantity, using the gains of the old policy. However,
when all alternatives produce the same value of Expression 8.31 or
when a group of alternatives produces the same maximum value, then
the tie is broken by the alternative that maximizes
N

> aajko;
gi® + j=1 (8.32)
the value test quantity, using the relative values of the old policy. The
relative values may be used for the value test because a constant differ-
ence will not affect decisions within a chain.
The general iteration cycle is shown in Fig. 8.1. It corresponds
completely with Fig. 6.1 for the discrete-time case and has a completely
analogous proof. The rules for starting and stopping the process are
unchanged.
108 THE CONTINUOUS-TIME DECISION PROCESS

Policy Evaluation
Use aj; and qj for a given policy to solve the double set of
equations
N
>, wes = 0 a 1,2,---,N
37=1
N
B=UuUt > ay 3 1,2,---,N
j=1

for all v; and g;, by setting the value of one v; in each recurrent
chain to zero.

Policy Improvement

For each state z, determine the alternative k that maximizes

N
>, %5*6;
f=1
using the gains g; of the previous policy, and makeit the new
decision in the 7th state.
If
N
>, 4*g;
j=1

is the same for all alternatives, or if several alternatives are

equally good accordingto this test, the decision must be made
on the basis of relative values rather than gains. Therefore,
if the gain test fails, break the tie by determining the alter-
native k that maximizes
N
git + > agko;
j=1
using the relative values of the previous policy, and by making
it the new decision in the 7th state.
Regardless of whether the policy-improvement test is based
on gains or values, if the old decision in the 7th state yields as
high a value of the test quantity as any other alternative,
leave the old decision unchanged. This rule assures conver-
gence in the case of equivalent policies.
When this procedure has been repeated for all states, a
new policy has been determined, and new [a,j] and [g;] ma-
trices have been obtained. If the new policy is the same as
the previous one, the iteration process has converged, and the
best policy has been found; otherwise, enter the upper box.

Fig. 8.1. General iteration cycle for continuous-time decision processes.

 COMPLETELY ERGODIC PROCESSES 109

Completely Ergodic Processes

If, as is usually the case, all possible policies of the problem are
completely ergodic, the computational process may be considerably
simplified. Sinceall states of each Markov process have the same gain
g, the value-determination operation involves only the solution of the
equations
N
B= git > ain; 1=1,2,---,N (8.33)
j=1
with vy set equal to zero. The solution for g and the remaining y;is
then used to find an improved policy. Multiplication of Eqs. 8.33 by
the limiting state probability x; and summation over 7 show that
N
g= 2, Ti

a result previously obtained.

The policy-improvement routine becomes simply: For each state 2,
find the alternative & that maximizes
N
qik¥ + > Aiz*v;
j=1
using the relative values of the previous policy. This alternative
becomesthe new decision in the7zth state. A new policy has been found
when this procedure has been performed for every state.
The iteration cycle for completely ergodic continuous-time systems
is Shown in Fig. 8.2. It is completely analogous to that shown in Fig.
4.2 for discrete-time processes. Note that, if the iteration is started
in the policy-improvement routine with all v; = 0, the initial policy
selected is the one that maximizes the earning rate of each state.
This policy is analogousto the policy of maximizing expected immediate
reward for discrete-time processes.
The proof of the properties of the iteration cycle for the continuous-
time case is very close to the proof for discrete time. We shall illustrate
this remark by theproof of policy improvementfor the iteration cycle of
Fig. 8.2.
Consider two policies, A and B. The policy-improvement routine
has produced policy B as a successor to policy A. Therefore we know
N N
gi + > asjBvj4 > git + > aijAv,4
j=1 j=1
or
N N

Yi = GB + > aazBuj4 — gid > aiz4v;4 (8.34)

j=1 j=1
110 THE CONTINUOUS-TIME DECISION PROCESS

Value- Determination Operation

Use ay; and q; for a given policy to solve the set of equations
N
= 8+ > ayy 1=1,2,---,N |
j=1
for all relative values v; and g by setting vy to zero.

Policy-Improvement Routine
For each state 2, find the alternative k’ that maximizes
N
-= gk + > aagko; <—
j=l
using the relative values v; of the previous policy. Then hk’
becomes the new decision in the ith state, q;*’ becomes q;, and
aie’ becomes aj;.

Fig. 8.2. Iteration cycle for completely ergodic continuous-time decision

processes.

and y; > 0. From the equations of the value-determination operation

we know
N
ge = qi® + > ayzBu;8 (8.35)
j=1

N
gA = git + > aiz4u54 (8.36)
j=1

If Eq. 8.36 is subtracted from Eq. 8.35 and if Eq. 8.34 is used to
eliminate g;2 — q:4, we obtain
N

eB — gh = ye + > ayB(vj? — 0/4)

<4 (8.37)
Let g4 = g® — gAand u;4 = v;8 — v4. Then Eq. 8.37 becomes
N

gr=vet > ab 1=1,2,---,N (8.38)

j=l
Equations 8.38 are the equations of the value-determination operation
written in terms of differences rather than absolute values. We know
 IHE FOREMAN’S DILEMMA 111

the solution is
N

gh = > wiByi (8.39)

j=
where 7;is the limiting state probability of state 7 under policy B.
Since all x;2 > 0, and all y; > 0, therefore g4 > 0. In particular,
g® will be greater than g4 if an improvementin the test quantity
N

git + > aajhv;

j=1

can be madein any state z that is recurrent under policy B.

The proof that the iteration cycle must converge on the optimalpolicy
is the same as that given in Chapter 4 for the discrete case.

The Foreman’s Dilemma

Let us solve the foreman’s problem shown in Table 8.2. Which

maintenance service and which repair service will provide greatest
earnings per unit time? Sinceall policies in the system are completely
ergodic, the simplified procedure of Fig. 8.2 can be used. Let us choose
as our initial policy the one that maximizes the earning rate for each
state. This is the policy consisting of normal maintenance andinside
repair. For this policy
1 —5 5 6
a=[] A= [ a) t= [5]
The value-determination equations (Eqs. 8.33) are
g = 6 — 5u1 + Sve g = —3 + 401 — 4ve
Thesolution of these equations with vg = 0 is
g=1 v71= 1 ve = 0
To find a policy with higher gain, we perform the policy-improvement
routine as shown in Table 8.3.

Table 8.3. PoLicy IMPROVEMENT FOR FOREMAN’S DILEMMA

State Alternative Test Quantity
N
1 k gk + > aggko;
j=1
1 1 6 — 5(1) = 1
2 4 2(1) = 2<

2 1 —3 + 41) =1
112 LHE CONTINUOUS-TIME DECISION PROCESS

The second alternative in each state is selected as a better policy. It

has been found that the policy of using expensive maintenance and
outside repair is more profitable than that of using normal services.

“Botta oly
Weevaluate this policy

using Eqs. 8.33. We have

g = 4 — 2u, + 2v2 g = —5 + 7v1 — 7ve
The solution of these equations with ve = 0 is
g=2 71= 1 ve = 0

Note that the gain is larger than it was before.

We must now enter the policy-improvement routine to see if we can
find a still better policy. However,since the values have coincidentally
not been changed, the policy-improvement routine would yield once
more the policy d = , . Because this policy has been achieved twice
in succession, it must be the optimal policy. Hence, the foreman
should use more expensive maintenance and outside repair; in this way
he will increase his profits from $1 to $2 per hour, on the average.
Note that, since v1 — ve = 1, the foreman should be willing to pay as
much as $1 for an instantaneous repair. The reader may investigate
policies d = B and d = i to assure himself that they do have
lower earnings per hour than the optimal policy.

Computational Considerations
Wehaveseenthat the solution of the continuous-time decision process
involves about the same amount of computation as thesolution of the
corresponding discrete process. As a matter of fact, the two types of
processes are computationally equivalent, so that the same computer
program maybe used for the solution of both. To see this, let us write
the value-determination equations (Eqs. 6.3 and 6.4) for the discrete
process
.
ge = j=l
> bug; i= 1,2,--,N (6.3)
N
gitu=qat > pur; 2 1,2,---,N (6.4)
j=1 j=
 COMPUTATIONAL CONSIDERATIONS 113

These equations may be written as

x(Diy — S4y)gy = O

k= qu + S (piy — 84y)0;
j=l
where 8;; is the Kronecker delta; 54, = lifs =7andOif7 #7. If we
now let ay = pij — Siz, we have
No
>, 4g; = 0
jai
N
= qi t+ > ay;
j=1
These are the value-determination equations (Eqs. 8.27 and 8.28) for
the continuous-time decision process. Thus if we have a program for
the solution of Eqs. 6.3 and 6.4 for the discrete process, we may use
it for the solution of the continuous process described by the matrix
A by transforming the transition rates to ““pseudo”’ transition proba-
bilities according to the relation pij = aij + S4y.*
Asfar as the policy-improvementroutine is concerned, in the discrete
case we maximize either
N N

> putgy or ge + > payto;

jal j=1

with respect to all alternatives £ in state 7.

Our decisions would be unchanged if we instead maximized
N

>(pest — Sig)gy or gek + > (pask — 8yy)0;

= j=1

in state 2, since only terms dependent upon & affect decisions. In terms
of aiy* = piy* — 3, the quantities to be maximized are
N N

> aytg, and git + > ask;

j=1 j=1
However, these are the test quantities for the policy-improvement
routine of the continuous process. As a result, a policy-improvement
routine programmed for the discrete process may be used for the
continuous process if the transformation pij* = ay* + 84 is performed.
* If the computer program assumes that 0 < py < 1, it will be necessary to
scale the ay so that —1 < ay < 0.
114 THE CONTINUOUS-TIME DECISION PROCESS

The discrete and continuous decision processes are thus computation-

ally equivalent. The same computer program may be used for the
solution of both processes by a simple data transformation.

The Continuous-Time Decision Process with Discounting

In Chapter 7 we studied the discrete sequential process with dis-
counting or with an indefinite duration. We may analyze continuous-
time decision processes with similar elements by use of an analogous
approach. Let us define a discount rate 0 < « < oo insucha waythat
a unit quantity of money received after a very short time interval dt
is now worth 1 — «dt. This definition corresponds to continuous com-
pounding at the rate « An alternate interpretation of « that allows
the process an indefinite duration is that there is a probability « di
that the process will terminate in the interval dz.
If v,(¢) is the total expected earnings of the system in time #, then by
analogy with Eq. 8.15 we have

vi(t + dt) = (1 — adi)(1 _ >,4 at) re di + vi(t)]

+ > ai dilriy + oon} (8.40)
j#t

In this equation we assume that rewards are paid at the end of the
interval dt and that the process receives no reward from termination.
Using the definition given by Eq. 8.2, we may rewrite Eq. 8.40 as

vat + at) = (1 — 2 dt) ( + Ai at) (ri at + v4(t)]

+ > aij at\ rs; + os

o}
j#i
OT

vi(t + dt) = (1 _— a dt) (vs + > ars) dt + v4(t) + > Qij at o(0
j#t j=1
and
N

vi(t + dt) = (rs + > ap) dt + v;(t) + > aij at v;(t) —adat v4(t)
j#t j=l

where terms of higher order than dt have been neglected.

Introduction of the earning rate from Eq. 8.16 and rearrangement
yield
N
vi(t + dt) — v(t) + a dt v(t) = gedt + > aiy dt vj(?)
jg=1
CONTINUOUS-TIME DECISION PROCESS WITH DISCOUNTING 115

If this equation is divided by dt and the limit taken as dt approaches

zero, we have
N
adv; (Z)
+ avi(t) = qi + > ayv(t) t= 1,2,---,N (8.41)
at Jj= 1

Equations 8.41 are analogous to Eqs. 8.17 and reduce to them if

a = 0. In vector form, Eqs. 8.41 become
dv(t)
at
+ av(t) = q + Av(2) (8.42)
Since Eq. 8.42 is a linear constant-coefficient differential equation,
we should expect a Laplace transformation to be useful. If the
transform of Eq. 8.42 is taken, we obtain

vs(s) — v(O) + av(s) = 1 —q + Av(s)

s
or
i(s + aI — Alo(s) =
andfinally
v(s) = “Ks + aI — A}q + [(s + «I — A}v(0) (8.43)
We might use Eq. 8.43 and inverse transformation to find v(¢) for a
given process. As usual, however, we are interested in processes of
long duration, so that only the asymptotic form of v(#) for large 7
interests us. Let us recall from Eq. 8.11 that

(I — A)-2 = 2S + Fs) (8.11)

whereS is the matrix of limiting state probabilities and J (s) is a matrix
consisting of only transient components. It follows that

(s + aI —- AJ? =-—+
S+ 4
$4 F(s + @) (8.44)
so that [(s + a)I — A]~! has all transient components. If Eq. 8.44 is
used in Eq. 8.43, we have

_1p 1 7 !
v(s) = ‘\; + ;° + F(s + 2) + |——s + F(s + 2) ¥(0) 7 (8.45)

We now wish to know which components of v(z) will be nonzero for

large?. The matrix multiplying € contains a step component of magni-
tude [(1/«)S + 7(«)]; all other terms of Eq. 8.45 represent transient
116 THE CONTINUOUS-TIME DECISION PROCESS

components of v(t). Therefore, if we define a vector v of present

values v; so that
v = lim vit)
t—> oo

we have

v= Es + Fa)|4
0

or
v = (al — A)!q (8.46)

using Eq. 8.11.

The vector v represents the discounted future earnings in a very long
time if the system is started in each state. Equation 8.46 shows how
these present values are related to the discount rate «, the transition-
rate matrix A, and the earning-rate vector gq. Equation 8.46 mayalso
be written in the form
N
avi = git > ayn; t= 1,2,---,N (8.47)
j=
We maysolve Eqs. 8.47 to find the present values of any continuous-
time decision process with discounting.

Policy Improvement
Weare interested not only in evaluating a given policy but also in
finding the policy that has highest present values in all states. We
should like to be able to solve a problem such as that posed by Table
8.2 when discounting is an important element. Equations 8.47
constitute a value-determination operation; we still require a policy-
improvement routine.
If we desired to maximize the rate of growth of v;,(¢) at time ¢ in
Eq. 8.41, we should maximize
N

qi® + > aastu;(t) — avi(2)

j=
with respect to all the alternatives kin thezth state. If we are interested
only in large ¢, we may use the asymptotic present value v; rather than
v;(¢) to obtain the test quantity
N

qi* + > Asj*v; — AU;

j=l
 POLICY IMPROVEMENT 117

However, since v; does not depend upon &, the expression

N

qi® + > aajko;

j=1
is a sufficient test quantity to be maximized with respect to all alterna-
tives k in state 2. |
The policy-improvement routine is thus: For each state 7, find the
alternative k& that maximizes
N

qi® + > aajkoy

j=l
using the present values of the previous policy. This alternative
becomes the new decision in the 7th state. When the procedure has
been repeated for all states, a new policy has been determined. This
new policy must have present values that are greater than those of the
previous policy unless the two policies are identical. In the latter
case the optimal policy has been found.
The value-determination operation and the policy-improvement
routine are shown in the iteration cycle of Fig. 8.3. The rules for
entering and leaving the cycle are the same as those given for earlier
cases. Weshall now prove the properties of the cycle, following the
lines of the proof for the discrete case given in Chapter7.

Value-Determination Operation
Use aj and q; for a given policy to solve the set of equations

au, = Git ayjrj a= 1,2,---,N

N .

j
for all present values vj.

Policy-Improvement Routine
For each state 2, find the alternative k’ that maximizes
N
— gk + > agko; <—
j=l
using the present values v; from the previous policy. Then ?’
becomesthe new decision in the ith state, g;*’ becomes q;, and
ayj®’ becomesaj.

Fig. 8.3. Iteration cycle for continuous-time decision processes with discounting.
118 THE CONTINUOUS-TIME DECISION PROCESS

Suppose that the iteration cycle produces a policy B as a successor

to policy A. Since B followed A, we know that
N N
giB + > aizPujA > qa + > aiz4vj4 in every State 7.
j=l j=1

Equivalently,
N N
ve = GB + > aigBoj4 — giA — > aytvj4 > 0 for all
j=1 j=1
where y; is the improvement in the test quantity that the policy-
improvement routine was able to achieve in the 7th state. For the
individual policies the value-determination operation yields
N

av;4 = iA + > aizAvjA

j=1
N

au;e = gi® + > aqBu,;®

j=
If the first equation is subtracted from the second andtherelation
for yi 1s used to eliminate g;? — q;4, we obtain
N

a(vB — v¢4) = ys + >, aigB(vg2 — 044)

jg=1
or
N
av; = Yi t+ > aigBu;>
j=l
where v;4 = v;8 — v;4. These equations are the same as our value-
determination equations except that they are written in terms of
differences in present values. In vector form their solution is
v4 = (aI — A)-ly
where y is the vector with components y;. All elements of (aI — A)7!
are nonnegative, as were those of (I — @P)—! in the discrete case, again
on either physical or mathematical grounds. If any y; > 0, at least
one v;4 must be greater than zero and no v;4 can be less than zero. The
policy-improvement routine must increase the present values of at
least one state and can decrease the present value of no state.
Similarly, no policy B that has some higher present values than
policy A can remain undiscovered because of convergence on A.
This is true because in such a caseall y; would be <0, while at least one
v;4 would be >0O; this situation would contradict the relation derived
above. Whentheiteration cycle has converged on a policy, that policy
has higher present values than any other nonequivalent policy.
 AN EXAMPLE 119

An Example
Let us use our results to solve the sequential decision problem pre-
sented in Table 8.2 with « = 4. We may interpret this to mean
that the duration of the foreman’s operation is exponentially distrib-
uted with mean 9 hours, or we may think of some investmentsituation
in which the interest rate is important. As is the custom, we shall
choose as ourinitial policy the one that maximizes earningrate; thatis,

ef) ART a] ae Lg]

The value-determination equations (Eqs. 8.47) are
V1 = 6 — 5v1 + 5ve $2 = —3 + 4v1 — 4ve

Their solution is
783 702
U1 = "82 v2 = 33

Proceeding to find a better policy, we employthe policy-improvement

routine as shown in Table 8.4.

Table 8.4. First Poticy IMPROVEMENT FOR FOREMAN’S DILEMMA

WITH DISCOUNTING
State Alternative Test Quantity
N

t k qk + > aagko;
j=1

1 6 — 5(4#) + 5(B) = 33
2 4 — 20088) + 2(588) = At
2 1 —3 + 4733) — 4 (753*) = $2

2 —5 + 7 (Be) —~ 7 (Se) = Ape <

The second alternative in each state constitutes a better policy, so that

afl af? yo alg

The value-determination equations (Eqs. 8.47) are
371 = 4 — 201 + 2ve 3V2 = —5 + 7v1 — 7v2

Their solution is
v1 = “32 v2 = “32
120 THE CONTINUOUS-TIME DECISION PROCESS

Note that the present values have once more increased. The policy-
improvement routine is entered again, with results shown in Table
8.5.

Table 8.5. SECOND PoLicy IMPROVEMENT FOR FOREMAN’S DILEMMA

WITH DISCOUNTING
State Alternative Test Quantity
1 k qik + > aku;

1 1 32
9 188

2 1 32
2 AB7

Since v1 — vg has remained unchanged, the values for the test

quantities are the same as those in Table 8.4. The policy d = |.

has been found twice in succession. Therefore, it is the optimal policy;

it has higher present values in all states than any other policy. Even
when the expected duration of the processis only 9 hours, the foreman
should use expensive maintenance and outside repair.

Comparison with Discrete-Time Case

In the discrete sequential decision process with discounting the value-
determination equations are
N
v= Ge +B>pyvy 1=1,2,---,N (7.9)
j=1

If we have developed a computer program for this operation, we might

be interested in knowing whether such a program would be useful in
the continuous case. For the continuous case the analogous equations
are
N
ave = qi+ > avy 1=1,2,---,N (8.48)
j=1

where g;’ has been used to distinguish the continuous from the discrete
case. We maydefine ai; = fi; — 8;; and write Eq. 8.48 as
N

av, = gi’ + > (by — 3y)0;

j=
Or
N

(1 + a)vs = ge’ + > payor;

j=l
 COMPARISON WITH DISCRETE-TIME CASE 12]

and
1 , 1 N

Ta tTkem
If we define 8 = 1/(1 + «) and q = 1/(1 + «)qs’, then we have
N

Ve = ge + BD. Pan;
j=l
a set of equations of the same form as those for the discrete case. Thus
if we have a continuous problem described by «, q’, and A, we may use
the program for the discrete problem described by 6, q, and P by making
the transformations

B=
_ q = 6q : P=A+4+I

In the policy-improvement routine for the discrete case, the test

quantity is
N

gi*§ + BD pisto;
j=
For the continuouscaseit is
N
qk + > ayko;
,

j=1

This quantity may be rewritten as

N

gi'® + > (pik — 8e)0;

j=
where aij* = pij* — 843. We now have an expression equivalent to
N

gi'® + > piyto;

j=1
since v; does not depend on k&._ If qi’* = (1/8)qe*, where 8 = 1/(1 + a),
then we have
1 N

ga + > pejto;
j=1
and this of course, is proportional to
N

ge + BD pajho;
j=l
whichis the test quantity for the discrete case. Thus the same trans-
formation that allowed us to use a program for the discrete case in the
122 ITHE CONTINUOUS-TIME DECISION PROCESS

solution of the value-determination operation allows us to use a

program for the policy-improvement routine that is based upon the
discrete process.
Wesee that by suitable transformationsa single program suffices for
both the discrete and continuous cases with discounting. Since we
showed the same relation earlier for cases without discounting, it is
clear that the continuous-time decision process, with or without dis-
counting, is computationally equivalent to its discrete counterpart.
Conclusion

With the discussion of continuous-time processes we have completed

our present investigation of dynamic programming and Markov proc-
esses. We have seen that the analysis of discrete-time and con-
tinuous-time Markov processes is very similar. In the discrete case
the z-transform is a powerful analytic technique, whereas for the con-
tinuous case the Laplace transform assumes this role. In either
situation the pertinent transformation has allowed us to analyze the
Special cases of periodicity and multiple chains that so often complicate
other analytic approaches.
Even when a structure of rewards is added to the process, the trans-
formational methods are useful for calculating total expected rewards
as a function of time and for determining the asymptotic forms of the
reward expressions. For a system operating under a fixed policy, a
knowledge of the total expected rewards of the process constitutes a
complete understanding of the system.
The most interesting case arises when there are alternatives available
for the operation of the system. In general, we should like to find
which set of alternatives or policy will yield the maximum total
expected reward. If we are dealing with a discrete system, and if we
wish to maximize the total expected reward over only a few stages of
the process, then a value-iteration approachis indicated. If, however,
we expect the process to have an indefinite duration, the policy-
iteration method is preferable. This method will find the policy that
has a higher average return per transition than any other policy under
consideration. Even in processes with possible multiple-chain behavior,
123
124 CONCLUSION

no serious difficulties arise. The computational scheme involved is

simple, practical, and easily implemented.
If, however, we are interested in maximizing total expected reward
for a continuous-time system, our choice is more limited. The con-
tinuous analogue of the value-iteration approach is so laborious that
practicality forces us to make simplifications. If we are especially
interested in processes of short duration, then the easiest courseis to
approximate the continuous-time process by a discrete-time process
and then use value-iteration. If, on the other hand, we are interested
in processes of long duration, the policy-iteration method is just as
applicable as it was in the discrete-time case. Furthermore, the
computational requirements of the two types of processes are so similar
that the same general computer program will suffice for the solution of
both classes of problems. We may conclude that the policy-iteration
method is especially important in the solution of continuous-time
processes because of the lack of practical alternatives.
We have found that the presence of discounting does not change the
basic nature of the decision-making problem. The earlier remarks
comparing value- and policy-iteration methods for discrete- and
continuous-time processes apply with equal weight when discountingis
present. The existence of discounting does have some interesting
features, however. First, for processes of long duration the concept
of gain is replaced by that of present value, and our objective in policy
improvement is to maximize the present valuesof all states. Second,
the chain structure of the process can be ignored in our computations.
Third, there will exist regions of discount-factor values that have the
same optimal policy. These features, however, change our com-
putational procedure very little. A well-designed computer program
can solve both discrete- and continuous-time processes, with or
without discounting.
Wheneverthe policy-iteration methodis applied, a by-product of the
calculation of the optimal policy is a set of state values that permits
the evaluation of departures from this policy in special circumstances.
In most systems these values are moreinteresting and useful than their
origin might indicate. It is important to remember in using these
numbers that their validity rests on the assumption that the optimal
policy is being followed almost always.
The examples in baseball strategy, automobile replacement, and so
forth, that have been presented are so simplified that they only whet
the appetite for further applications. The considerations involved in
selecting possible applications are these. First, can the system be
adequately described by a numberof states small enough to make the
 CONCLUSION 125

solution of the corresponding simultaneous equations computationally

feasible? Second, are the data necessary to describe the alternatives
of the system available? If the answers to these questions are affirma-
tive, then a possible application has been discovered. ‘There is every
reason to believe that a possible application when combined with
diligent work will yield a successful application.
Appendix:
The Relationship of Transient
to Recurrent Behavior

In the value-determination operation for a completely ergodic

process, we must solve the following equation for the v; andtheg:
N
gtu= git > pin; a=1,2,---,N (4.1)
j=
Rearranging, we have
N

vi — > pis +E = 4
j=
When vy = 0,arbitrarily, then
N-1 354 Oift #7
>, (8 — pului + B= H iyij life = 7
j=1

If we define a matrix

M = [mi] men _ Y Ps Torys N

then
1—f11 —hfie —fin-i 1
—pfai 1 —fpee 1
M =

| —pwi —pye —py,n-1 1

128 APPENDIX

Note that the matrix M is formed by taking the P matrix, makingall

elements negative, adding ones to the main diagonal, and replacing the
last column by ones.
If we also define a vector ¥V where
Vv; = VU; L< N

UN = 4

then
V1
v2
5 .

UN-1
§
Equation A.1 in the v, and the g can then be written in matrix
form as
Mv = q
or
v = M"1q (A.2)
where q is the vector of expected immediate rewards. The matrix
M~—! will exist if the system is completely ergodic, as we have assumed.
Thus, by inverting M to obtain M-1 and then postmultiplying M-! by q,
vi for 1 < 1 < N — 1 and g will be determined.
Suppose that state N is a recurrent state and a trapping state, so
that py; = 0 for7 # N, and dyn = 1. Furthermore, let there be no
recurrent states among the remaining N — 1 states of the problem.
We knowthat
v = M-lq

where M assumesthe special form

[ l- piu — pie — fi, N-1 ! 17

— pai 1 —peoe ! 1

:
M =

—pn-1,1 —pwn-1,2 1 — py-1,n-1' 1

a 0 0 0 ! 1
RELATIONSHIP OF TRANSIENT TO RECURRENT BEHAVIOR 129

where the nature of W and f are evident by comparison with the M

defined above. From therelations for partitioned matrices we have

It is clear that MM-! = M-1M = I as required. The nature of f

shows us that the elements in the first N — 1 rows of the last column
of M-! are each equal to the negative sum of the first N — 1 elements
in each row. Also, from Eq. A.2, g = gn as expected.
What is the significance of W-! and W=1f? Let us consider the
relations for the number of times the system enters each transient
state before it is absorbed by the recurrent state. Let uj; equal the
expected number of times that a system started in state 7 will enter
state 7 before it enters state NV.
The balancingrelations for the ; are
N-1
Uz = > UixPaj + 4; 1,4 < N-—1 (A.3)
k=1

Equation A.3 may be developed as follows: The number of times a

state 7 will be occupied for a given starting state 7 depends primarily
on its probabilistic relations with other states. For example, if the
system spends an average amount of time “, in somestate & and if a
fraction px; of the times state & is occupied a transition is made to state
7, then the expected numberof transitions into state 7 from state & is
Uixhxj. his contribution to “;; must be summedoverall of the NV
states with the exception of the trapping state, and so we havethefirst
term of Eq. A.3. In addition to this mechanism, however, “4; will be
increased by 1 if 7 is the state z in which the system is started; this
accounts for the 8;; term of Eq. A.3.
Let us define an VN — 1 by N — 1 square matrix U with components
uij. Then if we write Eq. A.3 in the form
N-1

> win(Sei — Dus) = day

k=1
we see that we have in matrix form
UW =I
or
Wwi=U
That is, the matrix W—! is the matrix U of average times spent in each
state for each starting state. Since these quantities must be non-
negative, the elements of W—! are nonnegative.
130 APPENDIX

The matrix W or U—! has the form of the matrix [£+1[ — L+1, L+1Pp)]
used in Eq. 6.23 of Chapter 6. Here we would interpret the uw; as the
expected number of times the system will enter one of the transient
states 7 in the group L + 1 before it enters some recurrent chainif it
is started in state 7 of the group L + 1. With this definition, the
elements of [4t1[ — “+1, Z+1P]-1 must all be nonnegative by the same
argument given here.
Using W-! = U, Eq. A.2, and the partitioned form of M1, we may
write
N-1 N-1

Ve = > MeQ3 — GN > Uy 1<i<N-1

j=l j=1

Or

N-1 N-1
Ve = > Mag; — B > Uij l<ti<N-1 (A.4)
jal j=1

The v; may now be interpreted in the following way. The v;

represent the sum of the expected numberof times the system will enter
each state 7 multiplied by the expected immediate rewardin that state
less the total number of times any state other than N will be entered
multiplied by the gain for state N,all given that the system started in
state 2.
In particular, if the reward qy in the recurrentstate is zero, and ifall
gi > Ofor1 <7 < N — 1, then
N
vi = > uajq; > 0 l<z<N-1
j=l
This was exactly the situation encountered in the baseball example of
Chapter 5, where we found that no negative values occurred relative
to the recurrentstate.
Suppose that we are investigating various policies for a system that
has only one recurrent state, state N. Suppose further that we have at
some stage found a policy B as a successor to policy A. Equation 4.11
must hold for the changes in gain and values
N
g4 + viA = Yi + > pu? uj4 i= 1, 2,° a) N (4.11)
j=l

Since for this particular system we know that these equations are
equivalent to Eq. A.4,
N N
vid = > msBye — gd > Uay8 a=1,2,---,N-—1
7=1
j= j=l
RELATIONSHIP OF TRANSIENT TO RECURRENT BEHAVIOR 131

If there has been no changein gain between A and B, then g4 = 0, and

we have left the sum of nonnegative terms so that v;4 must be non-
negative. We thus see that when increases in gain are not possible
the policy-improvement routine will attempt to maximize the values
of the transient states. This is the behavior observed in the baseball
problem, where at first glance it appeared as if we were violating our
ground rules by working with a system in which the gain waszeroforall
policies.
If the words “recurrent chain with gain g’”’ are substituted for
“single recurrent state,’’ the preceding developmentis virtually un-
changed. The pohcy-improvement routine will not only maximize
the gain of a recurrent chain,it will also maximize the valuesof transient
states that run into that chain.
References
1. R. Bellman, Dynamic Programming, Princeton University Press, Princeton,
N.J., 1957, Chapter XI.
2. M. F. Gardner and J. L. Barnes, Transients in Linear Systems, John Wiley &
Sons, New York, 1942.
3. R. [Link], ““Systems Analysis of Discrete Markov Processes,’’ [RE Trans.
on Circuit Theory, CT-3, No. 1, 257 (1956).
4. Operations Research Center, M.I.T., Notes on Operations Research 1959,
Technology Press, Cambridge, 1959, Chapters 3, 5, 7.

General References
E. F. Beckenbach, Ed., Modern Mathematics for the Engineer, McGraw-Hill
Book Company, New York, 1956.
R. Bellman, ‘‘A Markovian Decision Process,’”’ J. Math. and Mech., 6, 679 (1957).
J. L. Doob, Stochastic Processes, John Wiley & Sons, New York, 1953.
G. Elving, ‘“‘Zur Theorie der Markoffschen Ketten,’”’ Acta Soc. Sci. Fennicae, 2,
No. 8, 1937.
W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, 2nd
Ed., John Wiley & Sons, New York, 1957.
B. Friedman, Principles and Techniques of Applied Mathematics, John Wiley &
Sons, New York, 1956.
W. H. Huggins, “Signal-Flow Graphs and Random Signals,” Proc. I.R.E., 45,
74 (1957).
J. G. Kemeny and J. L. Snell, Finite Markov Chains, D. Van Nostrand Com-
pany, Princeton, 1960.
V. I. Romanovsku, Diskretnye Tsept Markova, State Publishers, Moscow, 1949.
T. A. Sarymsakov, Osnovy Teorii Protsessov Markova, State Publishers, Moscow,
1954.

133
Index

Alternatives, 26-28, 33, 104, 105 Gain, changes related to policy changes, 43,
49, 72-75, 111
Barnes, J. L., 94 of a process, 22, 24, 32, 36, 102
Baseball problem, best long-run policy, 52 of a state, 23, 24, 61-63, 103
computational requirements, 52 in multiple-chain processes, 60-63
evaluation of base situations, 53 Gardner, M. F., 94
Bellman, R., 1, 29
Iteration cycle, for continuous-time proc-
Car problem, best long-run policy, 57, 58, esses, 108, 110
89, 90 for continuous-time processes with dis-
computational requirements, 58, 89 counting, 117
solution in special situations, 58, 89 for discrete-time processes, 38, 64
Chain, periodic, 15 for discrete-time processes with discount-
recurrent, 13 ing, 84
Computational considerations, 36, 37, 49-52, for multiple-chain processes, 64
112-114, 120-123
Laplace transforms, definition, 94
Decision, 28, 33, 105 of vectors and matrices, 95
Decision vector, 33 table of, 95
Discount factor, 76
Discount rate, 114 Markovprocesses, definition, 3, 92
Matrices, differential, 12, 23, 94, 98
Earning rate, 100 stochastic, 11, 23, 94, 98
Equivalenceof discrete- and continuous-time
processes, 96, 112-114, 120-122 Partial-fraction expansion, 10
Policy, 28, 33, 105
Foreman’s dilemma, 96-105, 111, 112, 119, optimal, 28, 33, 61, 81, 105, 116
120 Policy improvement by a change in chain
Frog example, 3, 17, 18 structure, 68
135
136 INDEX

Present values, 81, 116 Total expected reward, for continuous-time

changes related to policy changes, 87, processes, 99-104
118 for continuous-time processes with dis-
Principle of Optimality, 29 counting, 114-116
Process, completely ergodic, 6, 13, 24, 32, for discrete-time processes, 18
60, 98, 109-111 for discrete-time processes with discount-
continuous-time, 3, 92 ing, 76-79
discrete-time, 3 Total-value vector, 18, 21
discrete-time related to continuous-time, Toymaker example, 4-7, 10, 11, 18-21,
96, 98 39-42, 80, 84-86
finite-state, 3 Transientstate, 12
Transition, 3
Relative values, 35, 62, 107 Transition probability, 4
interpretation of, 35, 41, 112 Transition-probability matrix, 4
sufficiency of, 35, 65 Transition rate, 92
Reward, 17, 76 Transition-rate matrix, 93
expected immediate, 18 Transition reward, 99
scaling, 36, 37 Trapping state, 12
Rewardrate, 99
Value iteration, for discrete-time processes,
Stage of a process, 28 28-31
State, definition, 3 for discrete-time processes with discount-
State probability, 5, 92 ing, 80, 81
in periodic chains, 16 limitations, 30, 31
limiting, 7, 98, 99
State-probability vector, 5 z-transforms, definition, 7
examplesof, 8
Taxicab problem, best long-run policy, 48, of vectors and matrices, 9
87, 88 table of, 9