Lecture 9: Dynamic Programming and the Bellman Equation

In many economic problems, the decision maker faces a sequence of choices, each affecting the next. A household that saves today has more to spend tomorrow; a firm that invests today produces more next year. Today’s choice earns a payoff now and changes the situation for every later choice, so the choices at different dates cannot be studied separately. Dynamic programming is a tool for solving such problems.

1 Sequential problems and their recursive form

1.1 The growth problem

Time is discrete, $t=0,1,2,\dots$. An agent (decision-maker) starts with a stock of capital $k_{0}>0$. Capital $k_{t}$ produces output $f(k_{t})$ at date $t$, and output is either consumed, $c_{t}$, or carried forward as next period’s capital, $k_{t+1}$. The agent values consumption streams by a discounted sum of one-period utilities and solves

The number $\beta\in(0,1)$ is the discount factor. The utility function $u:\mathbb{R}_{+}\to\mathbb{R}$ is continuous, strictly increasing, and strictly concave, and $f:\mathbb{R}_{+}\to\mathbb{R}_{+}$ is continuous, increasing, and concave with $f(0)=0$; both are differentiable on $(0,\infty)$. When we differentiate a value function we assume in addition that $u'(c)\to\infty$ as $c\to0$, so that an agent never chooses zero consumption.

Problem (1) is written as a sequential problem: the unknown is the whole sequence of consumptions and capital stocks, $c_{0},k_{1},c_{1},k_{2},\dots$, chosen at once. Since $c_{t}=f(k_{t})-k_{t+1}$, the capital sequence determines the consumption sequence. We can therefore use $k_{t+1}\in[0,f(k_{t})]$ as the choice at date $t$. Every date has the same structure, drawn in Figure 1.1: $$\underbrace{k_{t}}_{\text{state}} \ \longrightarrow\ \underbrace{k_{t+1}}_{\text{choice}} \ \longrightarrow\ \underbrace{k_{t+1}}_{\text{tomorrow's state}} .$$ The agent inherits the state $k_{t}$ at date $t$ and chooses $k_{t+1}$, earning the current payoff $u(f(k_{t})-k_{t+1})$. The transition makes today’s choice tomorrow’s state.

The state is not simply “a variable indexed by $t$.” It is the information inherited from the past that matters for the choices still to be made. In the growth problem, once $k_{t}$ is known, the feasible choices at date $t$ and everything after depend on the past only through $k_{t}$: two histories that arrive at the same $k_{t}$ face the same future. Which sequence of earlier consumptions produced $k_{t}$ is irrelevant, so it is not part of the state. If instead the payoff at date $t$ were $u(c_{t},c_{t-1})$, so that yesterday’s consumption changed the value of today’s, then $c_{t-1}$ would have to be carried in the state along with $k_{t}$. A state must therefore contain all information from the history that affects future feasible choices, payoffs, or transitions.

1.2 The principle of optimality and the Bellman equation

Suppose the agent begins a date with capital $k$ and chooses $k'$. From tomorrow on the agent faces the same continuation problem as (1), with $k'$ in place of $k_{0}$: the same technology, preferences, and infinite horizon. The highest utility attainable from tomorrow on therefore depends only on $k'$.

Whenever we write a maximum, we assume that the objective is finite and the maximum is attained. Bounded one-period utility is sufficient for convergence: if $\lvert u(c) \rvert\leq M$ for every $c\geq0$, every feasible stream has discounted utility of absolute value at most $M/(1-\beta)$ by the geometric-sum calculation of Lecture 8’s Example 3.9. Attainment requires additional conditions supplied by the macroeconomics sequence.

Now split lifetime utility from $k$ into today’s payoff and everything after. If today’s choice is $k'$, then today yields $u(f(k)-k')$, and the most that tomorrow and later can yield is $V(k')$, discounted once because it starts one period later. An optimal choice of $k'$ makes the total as large as possible:

This is the Bellman equation of the growth problem. Its terms correspond to the pieces of Section 1.1:

• $k$ is the current state;

• $k'$ is the choice, and $[0,f(k)]$ is the set of feasible choices;

• $u(f(k)-k')$ is the current payoff;

• today’s choice $k'$ becomes tomorrow’s state, which is why the same letter appears inside $V(\cdot)$;

• $V(k')$ is the continuation value, the value of behaving optimally from tomorrow on;

• $\beta$ discounts the continuation value back to today.

The reasoning that produced (2) is Bellman’s principle of optimality: after any feasible first choice, the best continuation is an optimal plan for the problem that starts from the resulting state. In particular, every tail of an optimal plan is optimal from the state reached at that date. Otherwise, replacing the tail by an optimal continuation would raise lifetime utility without changing any earlier payoff.

The unknown in (2) is a function. The equation must hold at every $k\geq0$, and the same $V$ appears on both sides, once evaluated at $k$ and once at $k'$. Thus solving the Bellman equation means finding a function $V$ that satisfies it at every state. For a fixed $k$ and a fixed candidate $V$, the maximization inside the braces is a one-variable problem of the kind solved in Lecture 6. The recursive formulation repeats this one-period choice at every state.

The recursive formulation gives more than an equation for $V$. Under our assumptions, the value function of Definition 1.1 is the unique bounded solution of the Bellman equation when $u$ is bounded. Moreover, a feasible capital sequence is optimal for (1) if and only if, at every date, its $k_{t+1}$ attains the maximum in (2) at the state $k_{t}$. We use these facts without proof; Section 3.2 returns to the uniqueness claim.

1.3 Value function and policy function

Solving (2) produces two objects, and it is important to keep them apart. The first is the value function $V$. The second is the choice that attains the maximum at each state.

Under our assumptions the maximizer is unique at every $k$, so $g$ is a function; we take this without proof. Consumption then follows from the constraint, $c=f(k)-g(k)$. The two functions answer different questions: $$k\ \overset{V}{\longmapsto}\ \text{lifetime utility from }k , \qquad\qquad k\ \overset{g}{\longmapsto}\ \text{tomorrow's capital }k' .$$ The policy function describes the agents’s choice at each state and generates the whole optimal path from $k_{0}$ alone: $$k_{1}=g(k_{0}),\qquad k_{2}=g(k_{1}),\qquad k_{3}=g(k_{2}),\ \dots$$ The Bellman equation determines the value function. Its continuation term $\beta V(k')$ values tomorrow’s capital in today’s utility. The sequential problem (1) and the recursive problem (2) generate the same optimal paths; the recursive formulation describes them with a rule $g$ rather than a list of numbers.

2 First-order and envelope conditions

The maximization inside the Bellman equation is a one-variable problem. Lecture 6 supplies its first-order condition, and Lecture 8’s envelope theorem gives the derivative of the optimized value. In this section we assume, for $k>0$, that $V$ is differentiable and concave and that the maximizer $g(k)$ is interior, $0<g(k)<f(k)$, and differentiable in $k$. Standard dynamic-programming results establish these properties under suitable hypotheses; we impose them rather than prove them.

2.1 The first-order condition

Fix $k$ and let $c=f(k)-k'$. The objective in (2) is $u(f(k)-k')+\beta V(k')$, and Lecture 6’s interior first-order condition, differentiating in $k'$, gives

Since the objective is concave in $k'$, the first-order condition is sufficient by Lecture 6’s Theorem 3.2: it locates the maximizer $k'=g(k)$. In words, one more unit of capital carried into tomorrow costs $u'(c)$ in utility today and is worth $\beta V'(k')$, the discounted marginal value of capital tomorrow. At the optimum the two are equal.

To eliminate the unknown derivative $V'(k')$ from (3), we use the envelope condition.

2.2 The envelope condition and the Euler equation

The Bellman equation defines $V(k)$ as an optimized value with parameter $k$. By Lecture 8’s Theorem 2.1, part 1, we hold the choice at its optimum and differentiate the objective only with respect to $k$. The parameter appears only in $u(f(k)-k')$, so

This is the envelope condition. One more unit of capital today raises output by $f'(k)$, and at the margin the extra output is worth $u'(c)$ whether it is consumed or saved, because the first-order condition has equated the two uses; the response of $g(k)$ contributes nothing to first order.

Equation (4) holds at every state, so it holds at tomorrow’s state $k'$ with tomorrow’s consumption $c'=f(k')-g(k')$: $V'(k')=u'(c')f'(k')$. Substituting into (3),

where we have restored time subscripts, $c=c_{t}$, $k'=k_{t+1}$, and $c'=c_{t+1}$. This is the Euler equation of the growth problem. Its left side is the utility cost of saving one more unit today. Its right side is the benefit: the unit becomes $f'(k_{t+1})$ units of output tomorrow, each worth $u'(c_{t+1})$, discounted once. Substitution has eliminated $V'$ and left a relation between consumption at adjacent dates and the model’s primitives.

The calculation has three steps that recur throughout macroeconomics: $$\boxed{\ \text{Bellman equation} \ \longrightarrow\ \text{first-order condition and envelope condition} \ \longrightarrow\ \text{Euler equation}\ }$$

2.3 The same Euler equation from the sequential problem

We can also derive (5) directly from the sequential formulation. Substitute $c_{t}=f(k_{t})-k_{t+1}$ into (1), so that the objective becomes $$\sum_{t=0}^{\infty}\beta^{t}u\left(f(k_{t})-k_{t+1}\right) ,$$ a function of the capital sequence alone. The variable $k_{t+1}$ appears in exactly two terms of the sum, dated $t$ and $t+1$. At an interior optimum, Lecture 6’s first-order condition in the single variable $k_{t+1}$, all other capital stocks held fixed, gives $$-\beta^{t}u'(c_{t})+\beta^{t+1}u'(c_{t+1})f'(k_{t+1})=0 ,$$ which is (5) after dividing by $\beta^{t}$. The economics is a one-period perturbation: consume one unit less at $t$, carry it forward, and consume the proceeds at $t+1$; at an optimum the change in lifetime utility is zero to first order.

The two derivations produce the same condition because the recursive and sequential formulations describe the same problem. The Bellman equation, its first-order condition, and its envelope condition reproduce the intertemporal optimality condition obtained directly from the sequential problem, using a one-period problem with the same form at every state. The Euler equation is a relation between three consecutive capital stocks $(k_{t},k_{t+1},k_{t+2})$; the initial condition $k_{0}$ pins down one end of the path, and the macroeconomics sequence supplies the condition that pins down the other, the transversality condition. We do not develop the transversality condition in this course.

2.4 Writing down a Bellman equation

Given a new dynamic problem, the procedure is: identify the state, the choice, the payoff, and the transition; then write today’s payoff plus $\beta$ times the value at tomorrow’s state, maximized over today’s choice. The consumption–saving problem also shows how two choices can parameterize the same recursion.

3 Why the recursion works: finite horizons and the fixed point

Finite horizons make the recursive logic explicit because they provide a last date from which to work backward. For an infinite horizon, the contraction mapping theorem determines the value function without a last date.

3.1 Finite horizons and backward induction

Suppose the world ends after date $T$: the agent solves

with no use for capital after date $T$. The value function now depends on the date as well as on the state, because the agent at date $t$ has $T-t+1$ decision dates remaining. Write $V_{t}(k)$ for the largest utility from date $t$ on when the date-$t$ state is $k$.

At the last date the problem is trivial. Capital left over is wasted and $u$ is increasing, so the agent consumes all output: $$V_{T}(k)=u\left(f(k)\right) .$$ At date $T-1$ the agent chooses $k_{T}$ knowing its continuation value, $V_{T}(k_{T})$: $$V_{T-1}(k)=\max_{0\leq k'\leq f(k)} \left\{u\left(f(k)-k'\right)+\beta V_{T}(k')\right\} .$$ Once $V_{T}$ is known, this is a one-variable problem of Lecture 6, and solving it at every $k$ gives the function $V_{T-1}$. Then $V_{T-2}$ is obtained from $V_{T-1}$ in the same way, and so on down to $V_{0}$: $$V_{T}\ \longrightarrow\ V_{T-1}\ \longrightarrow\ V_{T-2} \ \longrightarrow\ \cdots\ \longrightarrow\ V_{0} .$$

Computing $V_{T},V_{T-1},\dots,V_{0}$ in that order is called backward induction: it is Lecture 1’s induction, run from the last date toward the first. Each step is a static problem, and each maximum is attained by the Weierstrass theorem of Lecture 2 when the objective is continuous, since $[0,f(k)]$ is compact. The principle of optimality is also established by the argument: an optimal plan’s continuation from any date is optimal for the problem starting from the state reached on that date.

3.2 The infinite horizon as a fixed point

With no last date there is no $V_{T}$ from which to start. Example 3.2 shows the coefficient on $\sqrt{k}$ and the fraction carried forward approaching limits as dates are added. In a stationary problem, one whose payoff, feasible set, and transition are the same at every date, the infinite-horizon value does not depend on the calendar. The recursion of Proposition 3.1 with $V_{t}=V_{t+1}=V$ is the Bellman equation (2). Whether an infinite-horizon $V$ exists, and whether it is unique, is a fixed-point question. Under bounded rewards, a contraction argument on the space of bounded functions answers it.

To state the contraction result, write a stationary problem in general notation. It has a state $s$ in a state space $S$, a set $\Gamma(s)$ of feasible actions at $s$, a reward $r(s,a)$, a transition $s'=F(s,a)$, and a discount factor $\beta\in(0,1)$; the growth problem is the case $s=k$, $\Gamma(k)=[0,f(k)]$, $a=k'$, $r(k,k')=u(f(k)-k')$, and $F(k,k')=k'$. Table 3.1 lists the correspondence. The Bellman equation is $$V(s)=\sup_{a\in\Gamma(s)}\left\{r(s,a)+\beta V\left(F(s,a)\right)\right\} \qquad\text{for every }s\in S ,$$ written with a supremum so that it makes sense before anything is known about attainment.

The number $(\mathcal{T}v)(s)$ is the supremum value of a one-period choice at $s$ when $v$ values tomorrow’s state. The Bellman equation says $\mathcal{T}V=V$: the value function is a fixed point of $\mathcal{T}$. Backward induction is iteration of $\mathcal{T}$, since $V_{t}=\mathcal{T}V_{t+1}$ in Proposition 3.1. The operator $\mathcal{T}$ is the function-valued version of the map $T(x)=a+\beta x$ in Lecture 8’s Example 3.9: today’s reward plus $\beta$ times the continuation.

The space $B(S)$ is complete in the sup norm, a fact we use without proof. The contraction mapping theorem therefore gives three conclusions. The Bellman equation has exactly one bounded solution. Starting from any bounded $v_{0}$, even $v_{0}=0$, the iterates $v_{n+1}=\mathcal{T}v_{n}$ converge to it in sup norm, with the worst-case error shrinking by the factor $\beta$ each time. This procedure is called value function iteration. For $v_{0}=0$, the iterate $v_{n}$ is the value of the problem with $n$ dates remaining and no terminal value. Thus the infinite-horizon value is the limit of finite-horizon values, as in Example 3.2. More generally, value iteration can start from any bounded function, and the effect of that starting function vanishes at the geometric rate $\beta$.

Discounting supplies the contraction modulus $\beta$. As $\beta\to1$, the worst-case convergence bound becomes arbitrarily slow; at $\beta=1$, Lecture 8’s map $T(x)=a+x$ has no fixed point when $a\neq0$: an undiscounted constant stream of nonzero rewards has no finite value. The theorem also requires a bounded reward. In Example 3.2, $S=[0,\bar k]$ and $0\leq\sqrt{k-k'}\leq\sqrt{\bar k}$, so the hypothesis holds and the finite-horizon values converge uniformly to the unique bounded fixed point. If instead the state space were all of $\mathbb{R}_{+}$, the same reward would be unbounded above and this theorem would no longer apply.

4 A Bellman equation solved by hand

Value function iteration is useful for numerical work. When the primitives are special enough, the Bellman equation can be solved analytically by guess and verify: conjecture that $V$ has a particular functional form with unknown constants, substitute the conjecture into the Bellman equation, carry out the maximization, and check whether the result has the conjectured form again; if it does, matching constants yields equations for them. The guess proposes a candidate; substitution verifies that the candidate is a fixed point. A separate theorem is still needed to show that this fixed point is the value function and is unique in the relevant class.