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

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

6.2 The Model 383

By using the optimality equation (2.2), we are now able to prove the

existence of a stationary policy ζ

∗

= (

(∞)

) that is optimal.

Theorem 2.2 Let

f be a function that selects for each i ∈ S, an action

that maximizes the right-hand side of (2.2), i.e.,

u(i,

f (i)) + δ



(

f (i))V ( j)

≡ max

a∈A



u(i, a) + δ



(a)V ( j)



. (2.3)

Then, writing ζ

∗

= (

(∞)

), we have

I (ζ

∗

)(i) = V (i) for all i ∈ S.

Hence, ζ

∗

is optimal.

Proof. Let B(S) be the set of real-valued bounded functions on S.For

any g : S → A, the mapping

: B(S) → B(S), deﬁned by

u)(i) = u(i, g(i)) +δ



(g(i))u( j).

u evaluated at i represents the expected discounted return if the initial

state is i and we employ g for one period and then are terminated with

a ﬁnal return u( j)). One can show (see Section 6.4) that for bounded

functions u and v

(i) “u ≥ v” implies “L

u ≥ L

v”.

(ii) L

u → I (g

(∞)

)asn →∞, where L

u = L

u, L

u =

n−1

u).

(iii) I (g

(∞)

) is the unique ﬁxed point of L

f is a function that satisﬁes (2.3)

V = V

V = L

n−1

V ) = L

n−1

V =···=V.

Hence, letting n →∞, using (ii),

I (

(∞)

) = V.

384 Discounted Dynamic Programming Under Uncertainty

Exercise 2.1 In this chapter we focus on dynamic programming models

with discounting. But “undiscounted” models have also been explored;

examples are “negative” dynamic programming (the reward function

u(i, a) ≤ 0) and “positive” dynamic programming (the reward function

u(i, a) ≥ 0) with δ = 1 (see Blackwell 1967 and Ross 1983). Here is an

example of a positive dynamic programming problem with an important

feature.

The state space S is denumerable S ={0, 1, 2,...}, and there are two

actions A ={a

, a

}. The immediate return function is deﬁned as

u(0, a

) = u(0, a

) = 0;

u(i, a

) = 0 for i ≥ 1, i ∈ S;

u(i, a

) = 1 −(1/i) for i ≥ 1, i ∈ S.

The law of motion is described as follows:

) = q

) = 1;

i,i+1

) = 1 for i ≥ 1, i ∈ S,

i,0

) = 1 for i ≥ 1, i ∈ S.

Note that if the system is in state 0, then it remains there irrespective

of the chosen action, and yields no immediate return. If the state is

i ≥ 1, the choice of a

takes the system to the state i + 1, again yielding

no immediate return. If the state is i ≥ 1, the choice of a

yields an

immediate return of 1 − (1/ i), but no future return is generated as the

system moves to state 0 from i.

Again, with δ = 1, the problem is to maximize the sum of expected

one-period returns. As before write I (ζ)(i) =



∞

t=1

(ζ), where u

the expected return in date t from policy ζ (and i is the initial state).

Deﬁne V (i) = sup

I (ζ)(i) where ζ is any policy. Show that

(a) for i ≥ 1, V (i) = 1, but I (ζ)(i) < 1 for any policy ζ. Hence, there

is no optimal policy.

(b) Look at the right-hand side of the functional equation (2.2) with

δ = 1. What happens to the solution of the maximization problem in this

case? Compare your conclusion with Theorem 2.2.

6.3 The Maximum Theorem: A Digression 385

6.3 The Maximum Theorem: A Digression

Consider a static model in which an agent who chooses an action a after

observing the state s. Let S be the (nonempty) set of all states and A be

the (nonempty) set of all conceivable actions. Suppose that ϕ : S → A

is a correspondence (a set-valued mapping) which associates with each

s ∈ S, a (nonempty) subset ϕ(s)of A. One interprets ϕ(s) as the set of

actions that are feasible for the agent, given the state s. Let u be a real-

valued function on S × A, and interpret u(s, a) as the utility or return for

the agent when the state is s and his action is a.Givens, one is interested

in the elements ψ(s)ofϕ(s) which maximize u(s, ·) (now a function of

a alone) on ϕ(s), and m(s), the value of the maximum of u on ϕ(s). The

maximum theorem addresses these issues. For a precise statement of this

theorem, we ﬁrst need to develop some deﬁnitions involving set-valued

maps.

6.3.1 Continuous Correspondences

We shall assume in this subsection and in the next that S is a (nonempty)

metric space, with S its Borel sigmaﬁeld. A is a (nonempty) compact

metric space. We write x

→ x to denote a sequence x

converging to x.

Deﬁnition 3.1 A correspondence ϕ : S → A is a rule which associates

with each element s ∈ S,anonempty subset ϕ(s)of A.

We now deﬁne some continuity properties of a correspondence.

Deﬁnition 3.2 A correspondence ϕ : S → A upper semicontinuous at

s ∈ S iff:

“s

→ s, a

∈ ϕ(s

), a

→ a” implies a ∈ ϕ(s).

ϕ is upper semicontinuous if ϕ is upper semicontinuous at every s ∈ S.

Deﬁnition 3.3 A correspondence ϕ : S → A is lower semicontinuous

at s ∈ S iff:

“s

→ s, a ∈ ϕ(s)” implies “there is a

such that a

∈ ϕ(s

) and

→ a.”

ϕ is lower semicontinuous if ϕ is lower semicontinuous at every s ∈ S.

386 Discounted Dynamic Programming Under Uncertainty

Deﬁnition 3.4 A correspondence ϕ : S → A is continuous at s if it is

both upper and lower semicontinuous at s; ϕ is continuous if it is con-

tinuous at every s ∈ S.

Remark 3.1 When for all s ∈ S, ϕ(s) consists of a single element (so

that ϕ can be viewed as a function from S into A) the deﬁnition of upper

semicontinuity at s (or lower semicontinuity at s) is obviously equivalent

to the deﬁnition of continuity at s for the function ϕ(s).

Note that, since A is assumed to be compact, if ϕ is upper semicon-

tinuous at s, ϕ(s) is a nonempty compact subset of A.

6.3.2 The Maximum Theorem and the Existence

of a Measurable Selection

We shall now prove the maximum theorem which has wide applications

to models of optimization. Recall that S is a (nonempty) metric space

(with its Borel sigmaﬁeld S) and A a (nonempty) compact metric space.

Let ϕ be a continuous correspondence from S into A, and u a real-valued

continuous function on S × A. For each s ∈ S, deﬁne

m(s) = max

a∈ϕ(s)

u(s, a). (3.1)

Since ϕ(s) is a nonempty compact set, and u(s, ·) is continuous on

ϕ(s), m(s) is a well-deﬁned real-valued function on S. Next, for s ∈ S

deﬁne

ψ(s) ={a ∈ ϕ(s): u(s, a) = m(s)}. (3.2)

Since ψ (s) is nonempty for each s ∈ S, ψ is a correspondence from

S → A.

Theorem 3.1

(a) The function m : S →

R is continuous.

(b) The correspondence ψ : S → A is upper semicontinuous.

f : S → A such that

f (s) ∈ ψ

(

)

i.e.,

u(s,

f (s)) = m(s) ≡ max

a∈ϕ(s)

u(s, a). (3.3)

6.3 The Maximum Theorem: A Digression 387

Proof.

(a) To prove the continuity of m on S, let s ∈ S, and s

→ s. One has

to show that m(s

) → m(s). Write y

≡ m(s

). Choose a

∈ ϕ(s

) such

that

u(s

, a

) = y

≡ m(s

) for all n. (3.4)

Choose any subsequence y



of y

. Recalling that y



= u(s



, a



), and

that A is compact, a subsequence (a



)of(a



) converges to some a ∈ A.

Hence, (s



, a



) → (s, a). By upper semicontinuity of ϕ, we can assert

that a ∈ ϕ(s). Also, by continuity of u,



= m(s



) ≡ u(s



, a



) → u(s, a). (3.5)

We shall show that m(s) = u(s, a). Clearly, as a ∈ ϕ(s),

u(s, a)

 m(s). (3.6)

There is some z ∈ ϕ(s) such that

u(s, z) = m(s). (3.7)

By lower semicontinuity of ϕ, there is some z



such that z



∈ ϕ(s



)

and z



→ z. Hence,

u(s



, a



)  u(s



, z



Taking limit as n



→∞,

u(s, a)

 u(s, z) = m(s). (3.8)

By (3.6) and (3.8)

u(s, a) = m(s).

Hence by (3.5), the subsequence y



of y



converges to m(s). Hence, the

original sequence m(s

) must converge to m(s).

(b) The upper semicontinuity of ψ is left as an exercise.

is compact, hence, it is complete and separable. To prove the existence

of a Borel measurable

f such that

f (s) ∈ ψ(s) for every s ∈ S,weap-

peal to a well-known theorem on measurable selection due to Kuratowski

and Ryll-Nardzewski (1965) (stated and proved in Hildenbrand (1974,

Lemma 1, p. 55) and reviewed in detail in Wagner (1977, Theorem 4.2)).

To use this result we need to show that if F is any closed subset of A, the

388 Discounted Dynamic Programming Under Uncertainty

set ψ

−

(F) ≡{s ∈ S : ψ(s) ∩ F = φ} belongs to the Borel sigmaﬁeld S

of S. We show that ψ

−

(F) is closed. Let s

∈ ψ

−

(F) and s

→ s. Then

ψ(s

) ∩ F = φ for all n. Choose some a

∈ ψ(s

) ∩ F. By compact-

ness of A, there is some subsequence (a



) converging to some a. Since

F is closed, a ∈ F. Since (s



, a



) converges to (s, a) and ψ is upper

semicontinuous, a ∈ ψ(s). Hence a ∈ ψ(s) ∩ F, and this implies that

s ∈ ψ

−

(F).

We shall refer to

f as a measurable selection from the correspon-

dence ϕ.

Example 3.1 Let S = A = [0, 1], and ϕ(s) = A = [0, 1] for all s. Then

ϕ is clearly continuous. Deﬁne u(s, a) = sa.Fors = 0, ψ(s) consists of

a single element: ψ (s) = 1. For s = 0, ψ(s) = [0, 1]. Hence, ψ(s)isnot

lower semicontinuous at s = 0. For all s ∈ S, m(s) = s.

6.4 Dynamic Programming with a Compact Action Space

In this section, we deal with a more general framework under the follow-

ing assumptions on S, A, q, and u:

[A.1] S is a (nonempty) Borel subset of a Polish (complete, separable

metric) space;

[A.2] A is a compact metric space;

[A.3] u is a bounded continuous function on S × A; and

[A.4] if s

→ s, a

→ a, then q(.|s

, a

) converges weakly to q(.|s, a).

The main result asserts the existence of a stationary optimal policy ζ

∗

(

(∞)

); moreover, it is shown that the value function V (≡ I (

(∞)

) which

satisﬁes the functional equation is a bounded continuous function on S.

Let us ﬁrst note a preliminary result which follows from [A.3].

Lemma 4.1 Let w : S →

R be a bounded continuous function. Then

g : S × A →

R deﬁned by g(s, a) =

w(.) dq(.|s, a) is continuous.

Recall that C

(S) is the class of all bounded continuous functions on

S.Forv, v



∈ C

(S), we use, as before, the metric d(v, v



) =v − v



=

sup

s∈S

|v(s) −v



(s)|. The metric space (C

(S), d) is complete.

6.4 Dynamic Programming with a Compact Action Space 389

For every w ∈ C

(S), let w : S → R be the function deﬁned by

(w)(s) = max

a∈A



(u(s, a) +δw(.)) dq(.|s, a)



. (4.1)

Note that, by virtue of Lemma 4.1, the expression within square

brackets on the right-hand side of (4.1) is continuous in s and a, and,

consequently, the maximum is assumed for every s. Moreover, Lemma

4.1 implies that w is continuous and, since it is obviously bounded,

w ∈ C

(S). Thus,  maps C

(S) into C

(S).

Lemma 4.2  is a uniformly strict contraction mapping on C

(S) and,

consequently, has a unique ﬁxed point.

Proof. Let w

, w

∈ C

(S). Clearly, w

 w

+w

− w

. Since, as

is easy to check,  is monotone,

w

 (w

+w

− w

) =w

+ δw

− w

.

Consequently, w

−w

 δw

− w

.

Interchanging w

and w

we get

w

−w

 δw

− w

.

Hence w

−w

  δw

− w

,

which proves that  is a uniformly strict contraction mapping, since

δ<1.

Since C

(S) is a complete metric space, it follows that  has a unique

ﬁxed point V in C

(S).

The central result on the existence of a stationary optimal policy is

now stated.

Theorem 4.1 There exists a stationary optimal policy ζ

∗

= (

(∞)

) and

the value function V (≡ sup

I (ζ)) = I (ζ

∗

) on S is bounded and contin-

uous.

Proof. As in Section 6.2, with each Borel map g : S → A, associate

the operator L

on B(S) that sends u ∈ B(S) into L

u ∈ B(S), where

u is deﬁned by

u(s) =

[u(s, g(s)) +δu(.)] dq(.|s, g(s)), s ∈ S. (4.2)

390 Discounted Dynamic Programming Under Uncertainty

It is known that I (g

(∞)

) is the unique ﬁxed point of the operator L

(see

Theorem 5.1 (f ), Strauch (1966)).

Now let  be as in (4.1) and let V ∈ C

(S) be its unique ﬁxed point,

i.e., V = V. It follows from Theorem 3.1 that there exists a Borel map

f from S into A such that V = L

V . Consequently L

V = V so that

by the remark made in the preceding paragraph, V = I (

(∞)

). Hence

V = V can be rewritten as

I (

(∞)

(s)) = max

a∈A



(u(s, a) +δ I (

(∞)

)(.)) dq(.|s, a)



, s ∈ S. (4.3)

Thus I (

(∞)

) satisﬁes the optimality equation so that by a theorem of

Blackwell (1965, Theorem 6(f )) ζ

∗

= (

(∞)

) is an optimal policy. More-

over, as V = I (

(∞)

) and V ∈ C

(S), it follows that the value function

is continuous.

6.5 Applications

6.5.1 The Aggregative Model of Optimal Growth

Under Uncertainty: The Discounted Case

Initially (at “the beginning” of period t = 0), the planner observes the

stock y ≥ 0 (the state) and chooses some point a (an action) in A ≡ [0, 1].

Interpret a as the fraction of the stock y to be used as an input, and

write x ≡ ay to denote the input. Choice of a determines the current

consumption c ≡ (1 − a)y. This consumption generates an immediate

return or utility according to a function u :

→ R

(satisfying the

assumptions listed below): u(c) = u((1 − a)y).

To describe the law of motion of the states, consider a ﬁxed set of func-

tions  ={f

,... f

,..., f

}, where each f

: R

→ R

is interpreted

as a possible gross output function (we shall introduce assumptions on the

structure of f

below as we proceed). With each f

we assign a positive

probability q

(1 ≤ k ≤ N),



k=1

= 1. Let Q ={q

,...,q

After the choice of a (at “the end” of period t = 0), Tyche picks an

element f at random from  : f = f

with probability q

. The stock in

the next period is given by

= f (x). (5.1)

Thus, given the initial y and the chosen a, y

= f

(ay) with probability

. This stock y

is observed at “the beginning” of the next period, and

6.5 Applications 391

action a

is chosen from A, and, at the end of period t = 1, independent

of the choice in period 0, Tyche again picks an element f from  accord-

ing to the same distribution Q ={q

,...,q

}. The story is repeated.

One may take the initial stock y to be a random variable with a given

distribution µ independent of the choices of gross output functions. To

ease notation, we write

t+1

= f (x

remembering that f is randomly picked from  at the end of period t

independent of the past choices and according to the same distribution

Q on .

We make the following assumptions on the utility function:

[U.1] u is continuous on

;

[U.2] u is increasing on

;

[U.3] u is strictly concave.

The following assumptions on each f

are also made:

[T.1] f

is continuous on R

;

[T.2] f

(0) = 0; f

is increasing on R

;

[T.3] There is β

> 0 such that

(x) > xfor0 < x <β

(x) < x for x >β

We assume that β

< ···<β

Given an initial stock y > 0, a policy ζ = (ζ

) generates an input

process x

= (x

), a consumption process c

= (c

), and a stock process

= (y

) according to the description of Section 6.1. Formally,

≡ ζ

(y) · y, c

= [1 − ζ

(y)]y, y

= y (5.2)

and for t ≥ 1, for each history h

= (y

, a

;...y

t−1

, a

t−1

; y

), one has

) = ζ

, c

= [1 − ζ

)]y

= f (x

t−1

), (5.3)

where f = f

with probability q

Clearly,

+ x

= y

+ x

= f (x

t−1

) for t ≥ 1,

≥ 0, x

≥ 0 for t ≥ 0. (5.4)

392 Discounted Dynamic Programming Under Uncertainty

In view of [T.3] we can ﬁnd B > 0 such that f (x) < x for all x > B, and

for all k (k = 1, 2,...N ). Hence, the following boundedness property is

not difﬁcult to derive:

Lemma 5.1 Assume [T.1]–[T.3] and let y be any initial stock such that

y ∈ [0, B].

If ζ is any policy generating a stock process y

, then for all t ≥ 0

0 ≤ y

≤ B. (5.5)

It follows that the input and consumption process x

and c

generated

by ζ also satisfy for all t ≥ 0

0 ≤ x

≤ B, 0 ≤ c

≤ B. (5.6)

In what follows, we choose the state space S = [0, B]. If as in Sec-

tion 6.1, q(·|y, a) denotes the law of motion, i.e., the conditional distri-

bution of the stock y

t+1

in period t + 1, given the stock y and action a

in period t, then q(·|y, a) has the Feller property (see Example 11.2 of

Chapter 2). The following existence theorem follows from an application

of Theorem 4.1 in the present context:

Theorem 5.1 Assume [T.1]–[T.3] and [U.1]. There exists a stationary

optimal policy ζ

∗

= (ˆη

(∞)

), where ˆη : S → A is a Borel measurable func-

tion. The value function V = I (ζ

∗

)[= sup

I (ζ)] is continuous on S and

satisﬁes

V (y) = max

a∈A



u[(1 −a)y] +δ



k=1

V [ f

(ay)]q



= u[y − ˆη(y) · y] +δ



i=1

V [ f

(ˆη(y) · y)]q

. (5.7)

Moreover, V is increasing.

We refer to the function i(y) ≡ ˆη(y) · y as an optimal investment

policy function and the function c(y) ≡ [1 − ˆη(y)]y as an optimal con-

sumption policy function.