Bhattacharya R., Majumdar M. Random Dynamical Systems: Theory and Applications

Подождите немного. Документ загружается.

6.6 Complements and Details 413

[A.3] r(x, a) is upper semicontinuous (u.s.c.) on S × A and bounded

above. Also,

R(x) ≡

∞



k=0

(x) < ∞ (x ∈ S), (C6.8)

where

(x) ≡ sup

| r (x, a)τ

(x, a),

k+1

(x) = sup

(z)q(dz | x, a)(k = 0, 1, 2,...). (C6.9)

[A.4] (x, a) → q(dz | x, a) is weakly continuous on S × A into P(S).

Remark C6.4.1 By the property [P.3],

−β



∞



k=0



)

:0≤ k < ∞}) =

∞

k=0

−βu

γ (du | X

)

∞

k=0



). (C6.10)

By assumption [A.2], the last product is zero. Therefore,



∞

k=0

=∞

almost surely, and the process Y

in (C6.1) is deﬁned for all t ≥ 0. Further,

by assumption [A.3], and the computation in (C6.4),

)

∞

−βt

r(Y

) dt

)

≤ E

∞

−βt

r(Y

)

≤ τ

(x, f

(x))

r(x, f

(x))

+ E

∞



k=1

(x, f

(x))δ

) ···

k−1

)τ

)

r(X

)

≤

∞



k=0

(x) < ∞. (C6.11)

Thus (C6.4) is justiﬁed.

414 Discounted Dynamic Programming Under Uncertainty

Before proceeding further let us specify how the model and the as-

sumptions specialize to two important cases.

Special Case 1. (Discrete time models). In this case γ ({1}|x, a) = 1

for all x, a, i.e., T

≡ 1 for all k. Assumption [A.2] is redundant

here. Since τ

(x, a) ≡ (1 − e

−β

)/β, r

(x) in (C6.8) may be taken

to be sup

r(x, a)

in the statement of [A.3]. The discounted reward

for a policy ζ in this case is usually deﬁned by

I (ζ)(x) =

∞



k=0

r(X

, a

) = (1 − e

−β

)

−1

βV (ζ)(x), (C6.12)

where β and δ are related by

δ = e

−β

= θ . (C6.13)

Special Case 2.(Continuous time Markov models). This arises if the

holding time distribution is exponential, i.e.,

γ (du

x, a) = λ(x, a)exp{−λ(x, a)u} du, (C6.14)

where λ(x, a) is a continuous function on S × A into [0, ∞). The

process {Y

} in (C6.1) is then Markovian if the policy ζ is Marko-

vian, and is time-homogeneous Markovian if ζ is stationary. For

this case

(x, a) =

λ(x, a)

β + λ(x, a)

,τ

(x, a) =

β + λ(x, a)

. (C6.15)

Hence (C6.7) becomes

sup

x,a

λ(x, a) < ∞. (C6.16)

We are now ready to state our main result.

Theorem C6.4.1 Assume [A.1]–[A.4].

(a) The optimal discounted reward is an upper semicontinuous func-

tion on S satisfying

V (x) = max



r(x, a)τ

(x, a) + δ

(x, a)

V (z)q(dz

x, a)



(C6.17)

6.6 Complements and Details 415

(b) There exists a Borel measurable function f

∗

on S into A such that

a = f

∗

(x) maximizes, for each x, the right-hand side of (C6.17). The

stationary policy ζ

∗

= ( f

∗(∞)

) is optimal.

For a complete analysis, see Bhattacharya and Majumdar (1989a).

Controlled semi-Markov models in which the optimality criterion is the

maximization of “long-run average returns” are studied in Bhattacharya

and Majumdar (1989b).

6.6.3 State-Dependent Actions

Consider an optimization problem speciﬁed by "S, A, q(·|s, a),

u(s, a),δ#, where

– S is a (nonempty) Borel subset of a Polish (complete, separable metric)

space (the set of all states);

– A is a compact metric space (the set of all conceivable actions);

– ϕ is a continuous correspondence from S into A (ϕ(s) is the set of all

actions that are feasible at s);

– q(·|s, a) for each (s, a) ∈ S × A is a probability measure on the Borel

sigmaﬁeld of S (the law of motion: the distribution of the state s



tomorrow given and state s and the action a today);

– u(s, a) is the (real-valued) immediate return or utility function on

S × A;

– δ(0 <δ<1) is the discount factor;

– A policy ζ = (ζ

) is a sequence where ζ

associates with each h

, a

,...,s

) a probability distribution such that

(ϕ(s

)|s

, a

,...,s

) = 1 for all (s

, a

,...,s

– A Markov policy is a sequence (g

) where each g

is a Borel measurable

function from S into A such that g

(s) ∈ ϕ(s) for all s ∈ S. A stationary

policy is a Markov policy in which g

≡ g for some Borel measurable

function g for all t. A policy ζ associates with each initial state s,

the expected total discounted return over the inﬁnite future I (ζ)(s).

A policy ζ

∗

is optimal if I (ζ)

∗

(s) ≥ I (ζ)(s) for all policies ζ and

all s ∈ S.

– Note that in this description of the optimization problem, one recog-

nizes explicitly that the actions feasible for the decision maker depend

on the observed state, and a policy must specify feasible actions.

416 Discounted Dynamic Programming Under Uncertainty

The existence of an optimal stationary policy was proved by Furukawa

(1972). We state a typical result. We make the following assumptions:

[A.1] u(s, a) is bounded continuous function on S × A.

[A.2] For each ﬁxed s ∈ S, and any bounded measurable function w,

w(·) dq(·|s, a) is continuous in a ∈ A.

Proposition C6.4.1 Let A be a (nonempty) compact subset of

and ϕ

a continuous correspondence. Under assumption [A.1] and [A.2], there

exists a stationary optimal policy.

Section 6.5. Majumdar, Mitra, and Nyarko (1989) provide a detailed

analysis of the problem of “discounted” optimal growth under uncer-

tainty. In particular, several results are derived under weaker assumptions

(e.g. [T.6] was not assumed). In addition to the class of utility functions

that satisfy [U.1]–[U.4] they treat the case where u is continuous

, and lim

c↓0

u(c) =−∞. Finally, they consider the long-run

behavior of optimal processes when [T.4] is not assumed. See Nyarko and

Olson (1991, 1994) for models in which the one-period return function

depends on the stock. The role of increasing returns in economic growth

was emphasized by Young (1928), which has remained a landmark. For a

review of the literature on deterministic growth with increasing returns,

see Majumdar (2006). Example 5.1 is elaborated in Levhari and Srini-

vasan (1969) and Mirman and Zilcha (1975). The dynamic programming

model of Foley and Hellwig (1975) is of particular interest. The evolu-

tion of the optimal process of money balances is described by a random

dynamical system with two possible laws of motion (corresponding to

the employment status: the agent is employed with probability q and

unemployed with probability 1 −q). The question of convergence to a

unique invariant probability was studied by the authors.

The problem of selecting the optimal investment policy under uncer-

tainty and assessing the role of risk on the qualitative properties of the

optimal policy is central to the microeconomic theory of ﬁnance. A

related important issue is portfolio selection: the problem of the investor

who has to allocate the total investment among assets with alternative

patterns of risk and returns. The literature is too vast for a sketchy survey.

For a representative sample of early papers, see Phelps (1962), Hakansson

(1970), Sandmo (1970), Cass and Stiglitz (1972), Chipman (1973), and

Miller (1974, 1976).

6.6 Complements and Details 417

Models of discrete time Markovian decision processes (MDPs) with

incomplete information about (or, partial observation of) the state space

have been studied by several authors. An interesting theme is to recast

or transform such a model into a new one in which the state space is the

set of all probability distributions on the states of the original model. See

Sawarigi and Yoshikawa (1970) and Rhenius (1974) for formal treat-

ments, and Easley and Kiefer (1988, 1989) for applications. Dynamic

programming techniques have been widely used in variations of the

“bandit” model in order to treat optimal information acquisition and

learning. See the monographs by Berry and Friested (1985) and Gittins

(1989) on the mathematical framework and the wideranging applications

in many ﬁelds. An early application to economics is to be found in Roth-

schild (1974). Other examples from economics are spelled out in the

review article by Sundaram (2004).

This literature on stochastic games is also of interest. See Majumdar

and Sundaram (1991) for an economic model, and the lists of references

in Maitra and Parthasarathy (1970), Parthasarathy (1973), and Nowak

(1985).

Bibliographical Notes. In our exposition we deal with the inﬁnite

horizon problem directly. An alternative is to start with a T-period prob-

lem (ﬁnite) and to study the impact of changing T. Other comparative

static/dynamic problems involve studying the impact of (a) variations

of the discount factor δ: and (b) variations of the parameters in the

production and utility functions. For a sample of results, see Schal (1975),

Bhattacharya and Majumdar (1981), Danthene and Donaldson (1981a, b),

Dutta (1987), Majumdar and Zilcha (1987), and Dutta, Majumdar, and

Sundaram (1994).

Appendix

A1. METRIC SPACES: SEPARABILITY, COMPLETENESS,

AND COMPACTNESS

We review a few concepts and results from metric spaces. For detailed

accounts see Dieudonn´e (1960) and Royden (1968). Students from eco-

nomics are encouraged to review Debreu (1959, Chapter 1), Nikaido

(1968, Chapter 1), or Hildenbrand (1974, Part 1). An excellent exposi-

tion of some of the material in this and the next section is Billingsley

(1968).

Let (S, d) be a metric space. The closure of a subset A of S is denoted

A, its interior by A

, and its boundary by ∂ A(=

A\A

A is the

intersection of all closed sets containing A. A

is the union of all open

sets contained in A. We deﬁne the distance from x to A as

d(x, A) = inf {d(x, y): y ∈ A},

d(x, A) is uniformly continuous in x: verify that

|d(x, A) − d(y, A)|≤d(x, y).

Denote by B(x,ε) the open ball with center x and radius ε: B(x,ε) =

{y: d(x, y) <ε}.

Two metrics d

and d

on S are said to be equivalent if (write B

(x,ε) =

{y: d

(x, y) <ε}) for each x and ε there is a δ with B

(x,δ) ⊂ B

(x,ε)

and B

(x,δ) ⊂ B

(x,ε), so that S with d

is homeomorphic to S with

For any subset A of S, the complement of A is denoted by A

≡ S\A.

419

420 Appendix

A1.1. Separability

A metric space (S, d)isseparable if it contains a countable, dense subset.

A base for S is a class of open sets such that each open subset of S is the

union of some of the members of the class. An open cover of A is a class

of open sets whose union contains A.Aset A is discrete if around each

point of A there is an open “isolated” ball containing no other points of

A – in other words, if each point of A is isolated in the relative topology.

If S itself is discrete, then taking the distance between distinct points to

be 1 deﬁnes a metric equivalent to the original one.

Theorem A.1 These three conditions are equivalent:

(i) S is separable.

(ii) S has a countable base.

(iii) Each open cover of each subset of S has a countable subcover.

Moreover, separability implies

(iv) S contains no uncountable discrete set, and this in turn implies

(v) S contains no uncountable set A with

inf {d(x, y): x, y ∈ A, x = y} > 0. (A.1)

A1.2. Completeness

A sequence (x

) in a metric space (S, d)isaCauchy sequence if for every

ε>0 there exists a positive integer

n(ε) such that d(x

, x

) <εfor all

p, q ≥

n(ε).

Clearly, every convergent sequence in a metric space (S, d) is a Cauchy

sequence. Every subsequence of a Cauchy sequence is also a Cauchy

sequence. One can show that a Cauchy sequence either converges or has

no convergent subsequence.

It should be stressed that in the deﬁnition of a Cauchy sequence the

metric d is used explicitly. The same sequence can be Cauchy in one

metric but not Cauchy for an equivalent metric. Let S =

R, and consider

the usual metric d(x, y) =|x − y|.

This metric d is equivalent to

d(x, y) =

)

1 +|x|

−

1 +|y|

)

A1. Metric Spaces 421

The sequence {n: n = 1, 2,...} in R is not Cauchy in the d-metric,

but is Cauchy in the

d-metric.

A metric space (S, d)iscomplete if every Cauchy sequence in S

converges to some point of S.

The diameter of A is denoted by diam( A) ≡ sup

x,y∈A

d(x, y). A is

bounded if diam(A) is ﬁnite.

Theorem A.2 In a complete metric space, every non-increasing se-

quence of closed nonempty sets A

such that the sequence of their diam-

eters diam(A

) converges to 0 has a nonempty intersection consisting of

one point only.

Proof. Choose x

∈ A

(n ≥ 1). Then {x

} is a Cauchy sequence since



, n



≥ n, d(x



, x



) ≤ diam( A

), which, by completeness of S, must

converge to a limit, say, y. We will show that y ∈ A

for every n. Suppose,

if possible, that y /∈ A

. Since A

is closed, this means there is δ>0

such that B(y,δ) ⊂ A

. Then B(y,δ) ⊂ A

for all n ≥ m, which implies

d(x

, y) ≥ δ ∀n ≥ m, contradicting the fact x

→ y.

Theorem A.3 (Baire category) If a complete metric space (S, d) is

a countable union of closed sets, at least one of these closed subsets

contains a nonempty open set.

Proof. Suppose that S =

, where {A

} is a sequence of closed

sets. Suppose, to the contrary, that no A

contains a nonempty open

set. Thus, A

= S, and A

, the complement of A, is open and con-

tains an open ball B

= B( p

,ε

) with 0 <ε

. By assumption,

does not contain the open set B( p

,ε/2). Hence, the nonempty

open set A

∩ B( p

,ε/2) contains an open ball B

= B( p

,ε/2) with

0 <ε

. By induction, a sequence {B

}={B( p

,ε

)} of open

balls is obtained with the properties 0 <ε

, B

n+1

⊂ B( p

,ε

/2),

∩ A

= φ, n = 1, 2.

Since for n < m

d(p

, p

) ≤ d( p

, p

n+1

) +···+d( p

m−1

, p

)

n+1

+···+

422 Appendix

the centers (p

) form a Cauchy sequence, and hence, converge to a

point p. Since

d(p

, p) ≤ d( p

, p

) + d( p

, p)

+ d( p

, p) →

it is seen that p ∈ B

for all n. This implies that p does not belong to

any A

, hence, p /∈

∞

n=1

= S, a contradiction.

A set E in a metric space (S, d)isnowhere dense in S if (

= φ.

This is equivalent to saying that E is nowhere dense if S\

E is dense in

S.(S, d)isoftheﬁrst category if S is the union of a countable family

of nowhere dense sets. S is of the second category if it is not of the

ﬁrst category. Thus, by Theorem A.2, a complete metric space is of the

second category. From this theorem we can also conclude that if (S, d)

is a complete metric space, the intersection of a countable family of open

dense subsets of S is itself dense in S.

A1.3. Compactness

A set A is compact if each open cover of A contains a ﬁnite subcover.

An ε-net for A is a set of points {x

} with the property that for each

x in A there is an x

such that d(x, x

) <ε(the x

are not required to

lie in A). A set is totally bounded if, for every positive ε, it has a ﬁnite

ε-net.

Theorem A.4 For an arbitrary set A in S, these four conditions are

equivalent:

(i)

A is compact.

(ii) Each countable open cover of

A has a ﬁnite subcover.

(iii) Each sequence in A has a limit point (has a subsequence con-

verging to a limit, which necessarily lies in

A).

(iv) A is totally bounded and

A is complete.

A subset of k-dimensional Euclidean space

(with the usual metric)

has compact closure if and only if it is bounded (Bolzano–Weirstrass

theorem).

Theorem A.5 If h is a continuous mapping of S into another metric

space S



and if K is a compact subset of S, then hK is a compact subset

of S

