DP2015-15

Deterministic Dynam ic Program mingin Discrete Time:A M onotone Convergence Principle
Takashi KAMIHIGASHI
Masayuki YAOMarch 30, 2015

Deterministic Dynamic Programming inDiscrete Time: A Monotone ConvergencePrinciple∗
Takashi Kamihigashi†

Masayuki Yao‡

March 30, 2015

Abstract
We consider infinite-horizon deterministic dynamic programming
problems in discrete time. We show that the value function is always a fixed point of a modified version of the Bellman operator. Wealso show that value iteration monotonically converges to the valuefunction if the initial function is dominated by the value function,
is mapped upward by the modified Bellman operator, and satisfies
a transversality-like condition. These results require no assumption
except for the general framework of infinite-horizon deterministic dynamic programming.
Keywords: Dynamic programming, Bellman operator, fixed point,value iteration.

∗Financial support from the Japan Society for the Promotion of Science is gratefully
acknowledged.
†RIEB, Kobe University, Rokkodai, Nada, Kobe 657-8501 Japan.
Email: tkamihig@rieb.kobe-u.ac.jp.
‡Graduate School of Economics, Keio University, 2-15-45 Mita, Minato, Tokyo 1088345, Japan.
Email: myao@gs.econ.keio.ac.jp

1Introduction

Infinite-horizon dynamic programming in discrete time is one of the mostfundamental tools in economics. Of particular importance in dynamic programming is the convergence of the value iteration algorithm to the (true)
value function. While this convergence is fairly easy to establish for models
with bounded returns [1], unbounded returns are common in practice, especially in economic models. Accordingly, various results on the convergenceof value iteration have been established for such models under numerous
technical—especially topological—assumptions [2–9].
Recently, an order-theoretic approach that does not require topology wasdeveloped and applied to deterministic dynamic programming [10–12]. Thisapproach can be viewed as an extension of the earlier order-theoretic approach of [13]. One of the results based on the new approach is the following [10, Theorem 2.2]: value iteration monotonically converges to the valuefunction if the initial function is dominated by the value function, is mapped
upward by the Bellman operator, and satisfies a transversality-like condition.
This result requires only two assumptions in addition to the general framework of infinite-horizon deterministic dynamic programming. First, the constraint correspondence is nonempty-valued. Second, the value function neverequals +∞. The second assumption ensures that the Bellman operator iswell defined for any function dominated by the value function, but can benontrivial to verify since the value function is a priori unknown.
In this paper we establish a more general result that does not require eventhe above assumptions. We call this result a monotone convergence principle
since it requires no assumption except for the general framework itself. Toshow this principle, we follow the approach of [14] in modifying the Bellman
operator in such a way that it is well defined for any function. We showthat the value function is a fixed point of this modified Bellman operator.
The monotone convergence principle is that value iteration monotonicallyconverges to the value function if the initial function is dominated by thevalue function, is mapped upward by the modified Bellman operator, andsatisfies the same transversality-like condition as in the result of [10, Theorem
2.2].

1

2

Dynamic Programming

Our setup closely follows those of [10, 14]. Let X be a set, and let Γ be acorrespondence from X to X. Let D be the graph of Γ:
D = {(x, y) ∈ X × X : y ∈ Γ(x)}.

(1)

Let u : D → [−∞, ∞). A sequence {xt }∞t=0 in X is called a feasible path if
xt+1 ∈ Γ(xt ) for all t ∈ Z+ . A sequence {xt }∞t=1 in X is called a feasible path∞from x0 if the sequence {xt }t=0 is feasible. Let Π and Π(x0 ) denote the setof feasible paths and that of feasible paths from x0 , respectively:∞Π = {{xt }∞: ∀t ∈ Z+ , xt+1 ∈ Γ(xt )},t=0 ∈ X∞∞Π(x0 ) = {{xt }t=1 ∈ X : {xt }∞x0 ∈ X.
t=0 ∈ Π},(2)
(3)

Throughout the paper, we follow the convention thatsup ∅ = −∞.

(4)Let β ≥ 0. The value function v ∗ : X → [−∞, ∞] is defined byv ∗ (x0 ) =supLTXT ↑∞{xt }∞t=1 ∈Π(x0 )t=0β t u(xt , xt+1 ),x0 ∈ X,(5)where L ∈ {lim, lim} with lim = lim inf and lim = lim sup. Though L can belim or lim, its definition is fixed for the rest of the paper. Since u(x, y) < ∞for all (x, y) ∈ D, the right-hand side of (5) is well defined for any feasible
path. This together with (4) means that v ∗ is always well defined.
Let W be the set of functions from X to [−∞, ∞]. Let V = {v ∈ W :∀x ∈ X, v(x) < ∞}. The Bellman operator B on V is defined by(Bv)(x) = sup {u(x, y) + βv(y)},x ∈ X.

(6)y∈Γ(x)

Although Bv is well defined for any function v ∈ V , it may not be welldefined for all functions in W . This is because the right-hand side of (6) is
not well defined if u(x, y) = −∞ and v(y) = ∞ for some (x, y) ∈ D. This
problem and its consequences are discussed in [14].

2Following [14] we avoid the above problem by slightly modifying the righthand side of (6). For this purpose, we defineΓ̌(x) = {y ∈ Γ(x) : u(x, y) > −∞}, x ∈ X,)(TX
β t u(xt , xt+1 ) > −∞ ,Π̌ = {xt }∞t=0 ∈ Π : LT ↑∞(7)
(8)

t=0T
Π̌(x0 ) = {{xt }∞t=1 ∈ Π(x0 ) : {xt }t=0 ∈ Π̌},x0 ∈ X.

(9)

β t u(xt , xt+1 ).

(10)

Recalling (4) we see that∀x0 ∈ X,∗v (x0 ) =supL

TXT ↑∞{xt }∞
t=0
t=1 ∈Π̌(x0 )We define the modified Bellman operator B̌ on W by(B̌v)(x) = sup {u(x, y) + βv(y)},x ∈ X.

(11)y∈Γ̌(x)The right-hand side above is well defined for any v ∈ W and x ∈ X sincefor any y ∈ Γ̌(x) we have u(x, y) ∈ (−∞, ∞), which implies that the sumu(x, y) + βv(y) is well defined even if v(y) = −∞ or +∞. The following
result shows that B̌ is an extension of B to W .
Lemma 2.1. For any v ∈ V we have B̌v = Bv.
Proof. Let v ∈ V and x ∈ X. We claim that∀y ∈ Γ(x) \ Γ̌(x),u(x, y) + βv(y) = −∞.

(12)

To see this, let y ∈ Γ(x) \ Γ̌(x). Then u(x, y) = −∞. Since v ∈ V , we havev(y) < −∞. Hence u(x, y) + βv(y) = −∞; thus (12) follows.
To simplify notation, let g(x, y) = u(x, y) + βv(y) for y ∈ Γ(x). We have()(Bv)(x) = max

sup g(x, y),y∈Γ̌(x)sup(= maxg(x, y)(13)y∈Γ(x)\Γ̌(x))
sup g(x, y), −∞(14)y∈Γ̌(x)= sup g(x, y) = (B̌v)(x),y∈Γ̌(x)where (14) uses (12). Since x was arbitrary, it follows that Bv = B̌v.
3(15)

A function v ∈ W satisfying B̌v = v is called a fixed point of B̌. A fixed
point of B is defined similarly. We have the following result.
Theorem 2.1. Any fixed point of B in V is a fixed point of B̌. Furthermore,v ∗ is a fixed point of B̌.
Proof. See Section 4.
The first statement above is immediate from Lemma 2.1. The second
statement uses the argument of [14, Theorem 1]. Since β is only required tobe nonnegative, Theorem 2.1 applies to undiscounted problems of the typestudied by [15, 16].

3

Monotone Convergence Principle

We define the partial order ≤ on W as follows:v≤w⇔∀x ∈ X, v(x) ≤ w(x).

(16)

It is easy to see that B̌ is order-preserving in the sense that for any v, w ∈ W ,v≤w

⇒B̌v ≤ B̌w.

(17)

Given a sequence {vn }n∈N in W and a function v ∈ W , we say that {vn }n∈Nmonotonically converges to v pointwise if {vn (x)}n∈N is an increasing (i.e.,nondecreasing) sequence with limn↑∞ vn (x) = v(x) ∈ [−∞, ∞] for every x ∈X. We are ready to sate what we call a monotone convergence principle:Theorem 3.1. Let v ∈ W satisfyv ≤ v∗,(18)v ≤ B̌v.

(19)

Then the sequence {B̌ n v}n∈N monotonically converges to a fixed point v ∗ ofB̌ pointwise. Furthermore, if∀{xt }∞
t=0 ∈ Π̌,lim β t v(xt ) ≥ 0,t↑∞then v ∗ = v ∗ ; i.e., {B̌ n v}n∈N monotonically converges to v ∗ pointwise.
4(20)Proof. See Section 4.
The results of [10, Theorem 2.2] and [12, Theorems 2, 3] easily follow
from the above result; see [10, 12] for discussion of other related results inthe literature.
In Section 4 we prove Theorem 3.1 by extending the proof of [12, Theorem
3]. Unlike the latter proof, we directly show the first conclusion of Theorem
3.1 without using Kleene’s fixed point theorem. It is worth emphasizing thatTheorem 3.1 requires no additional assumption; thus it can be regarded as aprinciple in deterministic dynamic programming.

4Proofs of Theorems 2.1 and 3.1

4.1

Preliminary Result

In this subsection we state an elementary result shown in [14]. Recall from(4) that sup A is well defined for any A ⊂ R. We emphasize that none of thesets in the following result is required to be nonempty.
Lemma 4.1. Let Y and Z be sets. Let Ω ⊂ Y × Z, and let f : Ω → R. Fory ∈ Y and z ∈ Z, defineΩy = {z ∈ Z : (y, z) ∈ Ω},Ωz = {y ∈ Y : (y, z) ∈ Ω}.

(21)
(22)

sup f (y, z) = sup sup f (y, z) = sup sup f (y, z).

(23)Then(y,z)∈Ωz∈Z y∈Ωzy∈Y z∈ΩyProof. See [14, Lemma 1].

4.2

Proof of Theorem 2.1Let v ∈ V be a fixed point of B. Then v = Bv = B̌v by Lemma 2.1. Hencev is a fixed point of B̌.
To show that v ∗ is a fixed point of B̌, let x0 ∈ X. Note that {xt }∞t=1 ∈Π̌(x0 ) if and only ifu(x0 , x1 ) > −∞,LT ↑∞TX
t=1

5β t u(xt , xt+1 ) > −∞.

(24)

Therefore∞Π̌(x0 ) = {{xt }∞t=1 ∈ X × X × · · · : x1 ∈ Γ̌(x0 ), {xt }t=2 ∈ Π̌(x1 )}.

(25)

We apply Lemma 4.1 with y = x1 , z = {xt }∞t=2 , Ω = Π̌(x0 ), Y = Γ̌(x0 ),Z = X × X × · · · , and Ωy = Π̌(x1 ). Note from (10) thatv ∗ (x0 ) =supnu(x0 , x1 ) + L

T ↑∞{xt }∞t=1 ∈Π̌(x0 )=supsupn
sup u(x0 , x1 ) +(26)t=1T ↑∞(27)t=1TXoβ u(xt , xt+1 )t(28)sup {u(x0 , x1 ) + βv ∗ (x1 )} = (B̌v ∗ )(x0 ),(29)

x1 ∈Γ̌(x0 )=oβ t u(xt , xt+1 )TnoXtu(x0 , x1 ) + L
β u(xt , xt+1 )x1 ∈Γ̌(x0 ) {xt }∞t=2 ∈Π̌(x1 )=TXsupLT ↑∞{xt }∞
t=1t=2 ∈Π̌(x1 )x1 ∈Γ̌(x0 )where (27) uses Lemma 4.1 and (25). Since x0 was arbitrary, it follows thatB̌v ∗ = v ∗ .

4.3

Proof of Theorem 3.1

We first prove two lemmas.
Lemma 4.2. Suppose that there exists v ∈ W satisfying (18) and (19).
Define v ∗ = supn∈N (B̌ n v), where the supremum is taken pointwise. Then{B̌ n v}n∈N monotonically converges to v ∗ pointwise. Furthermore, v ∗ is afixed point of B̌.
Proof. For n ∈ N, let vn = B̌ n v. It follows from (17) and (19) that {vn }n∈N
is an increasing sequence. Hence {vn }n∈N monotonically converges to v ∗pointwise. To see that v ∗ is a fixed point of B̌, fix x ∈ X. Note thatv ∗ (x) = sup(B̌vn )(x) = sup sup {u(x, y) + βvn (y)}n∈N(30)n∈N y∈Γ̌(x)= sup sup{u(x, y) + βvn (y)}(31)y∈Γ̌(x) n∈N= sup {u(x, y) + βv ∗ (y)} = (B̌v ∗ )(x),y∈Γ̌(x)6(32)

where (31) uses Lemma 4.1. Since x ∈ X was arbitrary, it follows thatv ∗ = B̌v ∗ ; i.e., v ∗ is a fixed point of B̌.
Lemma 4.3. Let v ∈ W satisfy (20). Let v ∈ W be a fixed point of B̌ withv ≤ v. Then v ∗ ≤ v.
Proof. Let v ∈ W be a fixed point of B̌ with v ≤ v. Let x0 ∈ X. IfΠ̌(x0 ) = ∅, then v ∗ (x0 ) = −∞ ≤ v(x0 ). For the rest of the proof, supposethat Π̌(x0 ) 6= ∅. Let {xt }∞t=1 ∈ Π̌(x0 ). Then xt+1 ∈ Γ̌(xt ) for all t ∈ Z+ . We
havev(x0 ) = sup {u(x0 , y) + βv(y)}(33)

y∈Γ̌(x0 )≥ u(x0 , x1 ) + βv(x1 )≥ u(x0 , x1 ) + βu(x1 , x2 ) + β 2 v(x2 )
..
.
≥
≥

T −1
X
t=0
T−1
X

(34)
(35)
(36)

β t u(xt , xt+1 ) + β T v(xT )(37)

β t u(xt , xt+1 ) + β T v(xT ).

(38)

t=0Let δ > 0. By (20) we have β T v(xT ) ≥ −δ for sufficiently large T . For
such T we havev(x0 ) ≥T −1
X

β t u(xt , xt+1 ) − δ.

(39)

t=0Hence we havev(x0 ) ≥ LT ↑∞T −1X

β t u(xt , xt+1 ) − δ.

(40)

t=0

Since this holds for any {xt }∞to thet=1 ∈ Π̌(x0 ), applying sup{xt }∞t=1 ∈Π̌(x0 )right-hand side of (40) and recalling (10), we have v(x0 ) ≥ v ∗ (x0 ) − δ. Sinceδ was arbitrary, we obtain v(x0 ) ≥ v ∗ (x0 ). Since this is true for any x0 ∈ X,
we have v ≥ v ∗ .
7

To complete the proof of Theorem 3.1, let v ∈ W satisfy (18) and (19).
Then by Lemma 4.2, {B̌ n v}n∈N monotonically converges to v ∗ pointwise, andv ∗ is a fixed point of B̌. Assume (20). We have v ∗ ≤ v ∗ since v ≤ v ∗ by (18),B̌ is order-preserving, and v ∗ is a fixed point of B̌ by Theorem 2.1. We alsohave v ∗ ≥ v ∗ by Lemma 4.3. Hence v ∗ = v ∗ .

References[1] Stokey, N., Lucas, R.E., Jr.: Recursive Methods in Economic Dynamics,Harvard University Press, Cambridge, MA (1989)[2] Alvarez, F., Stokey, N. L.: Dynamic programming with homogeneousfunctions. Journal of economic theory, 82, 167–189 (1998)[3] Durán, J.: On dynamic programming with unbounded returns. Economic
Theory 15, 339–352 (2000)[4] Le Van, C., Morhaim, L.: Optimal growth models with bounded or unbounded returns: a unifying approach. Journal of Economic Theory 105,158–187 (2002)[5] Rincón-Zapatero, J.P., Rodrı́guez-Palmero, C.: Existence and uniquenessof solutions to the Bellman equation in the unbounded case. Econometrica
71, 1519–1555 (2003)[6] Rincón-Zapatero, J.P., Rodrı́guez-Palmero, C.: Corrigendum to “Existence and uniqueness of solutions to the Bellman equation in the unbounded case” Econometrica, Vol. 71, No. 5 (September, 2003), 1519–1555.
Econometrica 77, 317–318 (2009)[7] Martins-da-Rocha, V.F., Vailakis, Y.: Existence and uniqueness of a fixed
point for local contractions. Econometrica 78, 1127–1141 (2010)[8] Matkowski, J., Nowak, A.S.: On discounted dynamic programming withunbounded returns. Economic Theory 46, 455-474 (2011)[9] Jaśkiewicz, A., Nowak, A.S.: Discounted dynamic programming withunbounded returns: application to economic models. Journal of Mathematical Analysis and Applications 378, 450–462 (2011)8

[10] Kamihigashi, T.: Elementary results on solutions to the Bellman equation of dynamic programming: existence, uniqueness, and convergence.
Economic Theory 56, 251–273 (2014)[11] Kamihigashi, T.: An order-theoretic approach to dynamic programming: an exposition. Economic Theory Bulletin 2, 13–21 (2014)[12] Kamihigashi, T., Reffett, K., Yao, M.: An application of Kleene’s fixed
point theorem to dynamic programming: a note. International Journalof Economic Theory, forthcoming (RIEB Discussion Paper DP2014-24)(2014)[13] Bertsekas, D.P., Shreve, S.E., Stochastic Optimal Control: The DiscreteTime Case, Academic Press, New York (1978)[14] Kamihigashi, T.: On the principle of optimality for nonstationary deterministic dynamic programming. International Journal of Economic Theory
4, 519–525 (2008)[15] Dana, R.A., Le Van, C.: On the Bellman equation of the overtaking
criterion. Journal of Optimization Theory and Applications 67, 587–700(1990)[16] Dana, R.A., Le Van, C.: On the Bellman equation of the overtaking
criterion: addendum. Journal of Optimization Theory and Applications78, 605–623 (1993)

9