Lecture Notes on Dynamic Programming

Elmer Sterken
October 26, 2004

1 Introduction
This set of notes helps in understanding and solving dynamic programming
problems in economics. Dynamic programming is typically one branch of dy-
namic optimization techniques. The theory of optimal control (see Chiang,
1992) is the other main branch pointed at continuous models. Dynamic pro-
gramming is especially interesting if time is discrete. As known calculus of
variations is a special case of both techniques as we will show below.
It is useful to distinguish conceptual and methodological issues in dynamic
programming. First we need the intuition and after that we can go for the
direct solution of a problem. We will try to get the intuition from a basic
model, the optimal growth model See section 2. After that we go the more
formal derivations and solutions.

2 Optimal growth model

We consider the Cass-Koopmans optimal growth model. This model is an exten-
sion of the Solow growth model. In the Solow model the savings rate is imposed,
and there is no representation of preferences. the optimal growth model adds
preferences for households, and derives the optimal savings rate. Utility of con-
sumers is optimized, given the technology the firms can offer. We can write the
model in terms of decisions to be made by a social planner.
We model preferences in an instantaneous utility function:

U (ct ), t = 0, . . . , ∞ (1)

where ct is per capita consumption. We assume a constant population which we

normalize to 1. Utility is assumed to be separable in time: marginal utility of
consumption only depends on today’s consumption. Households discount utility
in the future by a constant factor β = 1/(1 + r) < 1 for positive rates r. So the
objective of a consumer is to maximize the present discounted value of future
utility:
Σ∞ t
t=0 β U (ct ) (2)

1
Now we go to the technology. We assume that output is produced using capital
as input:
yt = f (kt ) (3)
We assume that kt is capital available at the beginning of period t. This is capital
that was accumulated in the previous period t − 1. Capital accumulation takes
place through investment:

kt+1 = kt (1 − δ) + it (4)

Depreciation δ is assumed to be 100 per cent: δ = 1, so we get from the resource

constraint
ct + it = f (kt ) = yt (5)
the budget constraint:
ct + kt+1 = f (kt ) (6)
So the easy way of thinking of this equality is seeing kt+1 as savings.
So the whole problem is how to optimize lifetime utility given the budget
constraint and some initial value of k0 . The solution will be a sequence of ct
and kt+1 for all t’s. There is some structure though, since the problem is the
same for all periods, so we can derive a nice policy rule. This policy rule tells
us what is optimal to do, given the current state of the economy.
Back to the intuition. In economic models a subset of all variables often
fully summarizes the state of the system at any point of time. The behavior of
the other variables can be derived from the behavior of this subset. For instance
in the optimal growth model the capital stock kt fulfills this role. We call such
a variable a state variable. For each non-state variable we have a behavioral
equation relating its value at time t to the values of the state variables at t. For
example: yt = f (kt ). Knowing the subset of state variables can be handy, since
we reduce the complexity of the model to a large extent.
The evolution of the state variables over time determines the dynamics of
the model. So we need to describe this using a so-called transition equation for
each of the state variables. Another term used is law of motion. In the example
above this is the equation that relates kt+1 to kt : kt+1 = kt (1 − δ) + it .
In a model of explicit optimizing behavior we distinguish state variables from
choice variables, or instruments. This choice variables is in the control of the
agent and can be set as a function of the state variables at the beginning of the
period in which the choice is made. In the example above consumption ct plays
this role. One should be careful here though, since sometimes state variables at
time t + 1 can be in the instrument set.
So for our optimal growth model we need to find a sequence of kt , kt+1 , . . .
that gives maximum discounted utility. In this line it is worthwhile to introduce
the concept of a value function. A value function describes the maximum present
discounted value of the objective function from a specific point in time as a
function of the state variables at that date. So for the problem above we could
define a value function by V (kt ). This can be seen as follows. kt determines kt+1 ,
which determines kt+2 , etc. This series describes the whole sequence ct , ct+1 , . . ..

2
These values for consumption define the maximum attainable utility. The value
function concept argues that we do not need to know this sequence, but it is
sufficient to know kt and so V (kt ). We will use this idea in solving the dynamic
programming problem using the so-called Bellman approach.

3 Finite horizon problems

It is easy to start with a finite horizon approach. Assume you die at time T . We
can consider an infinite horizon problem as the case T → ∞. For the problem
above the assumption of a finite T affects the problem to some extent. One will
consume all in T such that kT +1 = 0.
Let us now look at optimality. Consider the problem:

max ΣTt=0 β t U [f (kt ) − kt+1 ] (7)

which we need to optimize for the path for kt . For one specific period this
objective function is:

. . . + β t U (f (kt ) − kt+1 ) + β t+1 U (f (kt+1 ) − kt+2 ) + . . . (8)

which includes all appearances of kt+1 . Take the derivative with respect to kt+1
and divide by β t :

U 0(f (kt ) − kt+1 ) = βU 0 (f (kt+1 − kt+2 )f 0 (kt+1 ) (9)

which holds for all t < T . This condition is an Euler-type condition. In equi-
librium today’s marginal utility is in balance with discounted marginal utility
of tomorrow. We discount by the rate of time preference and the interest rate
(in equilibrium R = f 0 (k)). So for all periods this marginal necessary condition
holds, except for the last period.

3.1 Special case

Consider the case of a logarithmic utility function U (ct ) = log(ct ) and a Cobb-
Douglas production function: yt = ktα . For the first-order condition we get:
 
1 1 α−1
= β αkt+1 (10)
ktα − kt+1 α −k
kt+1 t+2

As one can see this is a rather unpleasant second-order difference equation. Here
we use a trick. define:
kt+1
zt = α (11)
kt
So we can simplify the first-order condition into:
   
1 1 β 1 α−1
= αkt+1 (12)
ktα 1 − zt α
kt+1 1 − zt−1

3
which we can simplify into:
 
zt 1
= αβ (13)
1 − zt 1 − zt+1

The solution might be characterized by:

αβ
zt+1 = 1 + αβ − (14)
zt
This is not an explicit solution per se. Note that in order to get zt = zt+1 zt = 1
and zt = αβ are candidate solutions.
If we start from the terminal condition that zT = 0 we will get zt = αβ as
the solution. One can see this as follows. Start from ZT = 0 to get:
αβ
zT = 0 = 1 + αβ − (15)
zT −1

So:
αβ
zT −1 = (16)
1 + αβ
In a similar way we get:

αβ(1 + αβ)
zT −2 = (17)
1 + αβ(1 + αβ)

In the limit we get zt = αβ. This is rather ad hoc way of solving a dynamic
programming model. We we leave the example right now and go to the infinite
solution.

4 Deterministic infinite models

4.1 Intuition
In general terms it is rather difficult to get the infinite case as a limiting case
from the finite problems. The main reason is that the limit and max operators
cannot be interchanged. So the max of the limit is not the limit of the max.
So we will follow another route and use the Bellman principle. Let’s return
to the optimal growth model. If we can decide on today’s consumption and
tomorrow’s beginning capital, the other decisions can wait until tomorrow to be
made. So we will treat the problem in two separate terms. We are concerned
about today’s choices for the choice variables and the inheritance for tomorrow’s
state variables. Here it will be easy to use the value function. Suppose we start
at time t = 0. in the optimal growth model the single state variable is kt , so we
can express the value function of the problem as v(k0 ).

v(k0 ) = Σ∞ t
t=0 β U (ct ) (18)

4
We can rewrite this equation into:
v(k0 ) = max U (c0 ) + max Σ∞ t
 
t=1 β U (ct ) (19)
or
v(k0 ) = max [U (c0 ) + βv(k1 )] (20)
If we know the true shape of the value function v(k) we can compute the optimal
policy function kt+1 = g(kt ) for this problem. But we do not know the value
function and we do not need to know it.
We can substitute the restriction c0 = −k1 + f (k0 ) into the problem to get:
v(k0 ) = max [U (f (k0 ) − k1 ) + βv(k1 )] (21)
This is the Bellman equation, whose solution v(.) this function is stationary. k0
is the state variable, k1 is the choice variable. If we would not have substituted
consumption c0 out of the problem, it would have been a choice variable as well.
A simple first-order condition is:
U 0 (f (k0 ) − k1 ) = βv 0 (k1 ) (22)
So what this expression tell us? The marginal utility of consuming current
output must be equal; to the marginal utility of allocating it to capital and
enjoying consumption next period.

4.2 Using the envelope theorem

In the last condition expressed above we have a nasty v 0 it would be easy to
get rid of this term and express it in other model terms. Here we use the
envelope theorem. It argues that given an optimal choice of the other variables,
an optimal choice of our instrument yields the optimal solution. Let us start
from the policy rule we have in mind:
k1 = g(k0 ) (23)
Substitute this into the value function:
v(k0 ) = U (f (k0 ) − g(k0 )) + βv(g(k0 )) (24)
So now we expressed the value function totally in terms of the state variable k0 .
Optimality with respect to k0 will yield optimality for the whole problem. So
differentiate the value function with respect to k0 :
v 0 (k0 ) = U 0 (.)f 0 (k0 ) − U 0 (.)g 0 (k0 ) + βv 0 (g(k0 ))g 0 (k0 ) (25)
But above we showed that for the optimal solution we have U 0 (f (k0 ) − k1 ) =
βv 0 (k1 ), so:
v 0 (k0 ) = U 0 (f (k0 ) − k1 )f 0 (k0 ) (26)
which we can also use for k1 : v 0 (k1 ) = U 0 (f (k1 ) − k2 )f 0 (k1 ). So we get finally:
U 0 [f (k0 ) − k1 ] = βU 0 (f (k1 ) − k2 ))f 0 (k2 ) (27)

5
4.3 Example
Suppose we have our example again: The Cobb-Douglas production function:
yt = f (kt ) = ktα and the logarithmic utility function: u(ct ) = log(ct ). So we get
the Bellman equation:

v(kt ) = max (log(ct ) + βv(kt+1 )) + λt (ktα − ct − kt+1 ) (28)

Differentiate with respect to ct :

1
= λt (29)
ct
And with respect to kt+1 :
βv 0 (kt+1 ) = λt (30)
Let’s work out the envelope condition here. So we write the solution to all
variables as functions of the state variables: ct = c(kt ) and kt+1 = k(kt ). So the
Bellman equation turns unto:

v(kt ) = max log(c(kt )) + βv(k(kt )) + λt (kt )(ktα − c(kt ) − k(kt )) (31)

Differentiate with respect to kt :

c0t
v 0 (kt ) = + βv 0 (kt+1 )kt+1
0
+ λ0t [ktα − c(kt ) + kt+1 ] + λt [αktα−1 − c0t − kt+1
0
] (32)
ct
The second term vanishes because of the constraint. So we regroup into:
 
0 0 1 0
v (kt ) = ct − λt + kt+1 (βv 0 (kt+1 ) − λt ) + λt αktα−1 (33)
ct
Because of the first-order conditions we get rid of the first two terms, so we
have:
1
v 0 (kt ) = αktα−1 (34)
ct
So we get the first-order condition:
1 1 α−1
= αβ k (35)
ct ct+1 t+1
This is a difference equation, which we can solve using various methods. We
will give an overview of these methods in the next section.

5 Solving the first-order conditions

We have two basic methods to solve difference equations like in the example
above:
• Solution by conjecture;
• Solution by iteration.

6
5.1 Solving by conjecture
Suppose in the example on the optimal growth model with the log consump-
tion function and the Cobb-Douglas production function we conjecture that
households save a fixed fraction θ of income. This implies:

kt+1 = θktα (36)

Or equivalently ct = (1 − θ)ktα . Substitute in the first-order condition:

α
kt+1 θ
αβ = (37)
ct+1 1−θ

Using the consumption function for ct+1 it is easy to see that:

α
kt+1 θ
αβ α = (38)
(1 − θ)kt+1 1−θ

or αβ = θ. So we get the solution:

ct = (1 − αβ)ktα (39)

So this shows the ease of solving by conjecture in simple models.

5.2 Solving by iterating the value function

This principle is based on the notion that the value function of the problem
will differ each period, but it will gradually converge the further away we get
from the terminal period. The method is tedious, but must work in all cases.
One needs to know a little about limit values (and don’t be afraid to optimize
repeatedly).
Suppose we have a finite problem and we know that we die in period T + 1,
so v(kT +1 ) = 0. This implies that savings at time T will be zero kT = 0 and all
income is consumed cT = kTα . So counting back we have that:

v1 (kT ) = log kTα (40)

So in the period before we have:

v2 (kT −1 ) = max(log(cT −1 ) + β log(kTα )) (41)

subject to cT −1 = kTα−1 − kT . This is a problem we can solve easily using a

simple Lagrange step. We get the first-order conditions:
1
λ= (42)
cT −1
1
λ = αβ (43)
kT

7
With the budget constraint we get:
αβ
kT = kα (44)
1 + αβ T −1
1
cT −1 = kT −1 α (45)
1 + αβ

We can plug these values into the expression for v2 (kT −1 ):

v2 (kT −1 ) = αβ log(αβ) − (1 + αβ) log(1 + αβ) + (1 + αβ) log(kTα−1 ) (46)

and we can proceed with v3 (kT −2 ). It can be shown that the sequence of value
functions converges to:
    
−1 αβ α
v(kt ) = max log ct + β (1 − β) log(1 − αβ) + log αβ + log kt+1
1 − αβ 1 − αβ
(47)
The first-order condition was:

U 0(ct ) = βv0(kt+1 ) (48)

We have:
α 1
v0(kt+1 ) = (49)
1 − αβ kt+1
So:
ct 1 − αβ
= (50)
kt+1 αβ
Rewrite the resource constraint into:
ct ktα
= −1 (51)
kt+1 kt+1

So we get:
kt+1 = αβktα (52)
which we have seen before!

6 Further reading
There are some nice introductory texts on dynamic optimization. One can look
at Dixit (1990), the appendix of Kreps (1990), and Simon and Blume (1994).
A book on optimal control theory in economics is Chiang (1992).
Macroeconomic applications can be found everywhere. Sargent (1987), Blan-
chard and Fischer (1989), Heijdra and Van der Ploeg (2002), and Walsh (2003)
are some nice examples.