Optimal Growth I: The Stochastic Optimal Growth Model¶

Assumptions and Comments¶

In what follows,

• The sequence \(\{\xi_t\}\) is assumed to be IID
• The common distribution of each \(\xi_t\) will be denoted \(\phi\)
• The production function \(f\) is assumed to be increasing and continuous
• Depreciation of capital is not made explicit but can be incorporated into the production function

While many other treatments of the stochastic growth model use \(k_t\) as the state variable, we will use \(y_t\)

This will allow us to treat a stochastic model while maintaining only one state variable

We consider alternative states and timing specifications in some of our other lectures

Optimization¶

Taking \(y_0\) as given, the agent wishes to maximize

subject to

where

• \(u\) is a bounded, continuous and strictly increasing utility function and
• \(\beta \in (0, 1)\) is a discount factor

In (3) we are assuming that the resource constraint (1) holds with equality — which is reasonable because \(u\) is strictly increasing and no output will be wasted at the optimum

In summary, the agent’s aim is to select a path \(c_0, c_1, c_2, \ldots\) for consumption that is

1. nonnegative,
2. feasible in the sense of (1),
3. optimal, in the sense that it maximizes (2) relative to all other feasible consumption sequences, and
4. adapted, in the sense that the action \(c_t\) depends only on observable outcomes, not future outcomes such as \(\xi_{t+1}\)

In the present context

• \(y_t\) is called the state variable — it summarizes the “state of the world” at the start of each period
• \(c_t\) is called the control variable — a value chosen by the agent each period after observing the state

The Policy Function Approach¶

One way to think about solving this problem is to look for the best policy function

A policy function is a map from past and present observables into current action

We’ll be particularly interested in Markov policies, which are maps from the current state \(y_t\) into a current action \(c_t\)

For dynamic programming problems such as this one (in fact for any Markov decision process), the optimal policy is always a Markov policy

In other words, the current state \(y_t\) provides a sufficient statistic for the history in terms of making an optimal decision today

This is quite intuitive but if you wish you can find proofs in texts such as [SLP89] (section 4.1)

Hereafter we focus on finding the best Markov policy

In our context, a Markov policy is a function \(\sigma \colon \mathbb R_+ \to \mathbb R_+\), with the understanding that states are mapped to actions via

In what follows, we will call \(\sigma\) a feasible consumption policy if it satisfies

In other words, a feasible consumption policy is a Markov policy that respects the resource constraint

The set of all feasible consumption policies will be denoted by \(\Sigma\)

Each \(\sigma \in \Sigma\) determines a continuous state Markov process \(\{y_t\}\) for output via

This is the time path for output when we choose and stick with the policy \(\sigma\)

We insert this process into the objective function to get

This is the total expected present value of following policy \(\sigma\) forever, given initial income \(y_0\)

The aim is to select a policy that makes this number as large as possible

The next section covers these ideas more formally

Optimality¶

The policy value function \(v_{\sigma}\) associated with a given policy \(\sigma\) is the mapping defined by

when \(\{y_t\}\) is given by (5) with \(y_0 = y\)

In other words, it is the lifetime value of following policy \(\sigma\) starting at initial condition \(y\)

The value function is then defined as

The value function gives the maximal value that can be obtained from state \(y\), after considering all feasible policies

A policy \(\sigma \in \Sigma\) is called optimal if it attains the supremum in (8) for all \(y \in \mathbb R_+\)

The Bellman Equation¶

With our assumptions on utility and production function, the value function as defined in (8) also satisfies a Bellman equation

For this problem, the Bellman equation takes the form

This is a functional equation in \(w\)

The term \(\int w(f(y - c) z) \phi(dz)\) can be understood as the expected next period value when

• \(w\) is used to measure value
• the state is \(y\)
• consumption is set to \(c\)

As shown in EDTC, theorem 10.1.11 and a range of other texts

The value function \(v^*\) satisfies the Bellman equation

In other words, (9) holds when \(w=v^*\)

The intuition is that maximal value from a given state can be obtained by optimally trading off

• current reward from a given action, vs
• expected discounted future value of the state resulting from that action

The Bellman equation is important because it gives us more information about the value function

It also suggests a way of computing the value function, which we discuss below

Greedy policies¶

The primary importance of the value function is that we can use it to compute optimal policies

The details are as follows

Given a continuous function \(w\) on \(\mathbb R_+\), we say that \(\sigma \in \Sigma\) is \(w\)-greedy if \(\sigma(y)\) is a solution to

for every \(y \in \mathbb R_+\)

In other words, \(\sigma \in \Sigma\) is \(w\)-greedy if it optimally trades off current and future rewards when \(w\) is taken to be the value function

In our setting, we have the following key result

A feasible consumption policy is optimal if and only if it is \(v^*\)-greedy

The intuition is similar to the intuition for the Bellman equation, which was provided after (9)

See, for example, theorem 10.1.11 of EDTC

Hence, once we have a good approximation to \(v^*\), we can compute the (approximately) optimal policy by computing the corresponding greedy policy

The advantage is that we are now solving a much lower dimensional optimization problem

The Bellman Operator¶

How, then, should we compute the value function?

One way is to use the so-called Bellman operator

(An operator is a map that sends functions into functions)

The Bellman operator is denoted by \(T\) and defined by

In other words, \(T\) sends the function \(w\) into the new function \(Tw\) defined (11)

By construction, the set of solutions to the Bellman equation (9) exactly coincides with the set of fixed points of \(T\)

For example, if \(Tw = w\), then, for any \(y \geq 0\),

which says precisely that \(w\) is a solution to the Bellman equation

It follows that \(v^*\) is a fixed point of \(T\)

Review of Theoretical Results¶

One can also show that \(T\) is a contraction mapping on the set of continuous bounded functions on \(\mathbb R_+\) under the supremum distance

See EDTC, lemma 10.1.18

Hence it has exactly one fixed point in this set, which we know is equal to the value function

It follows that

• The value function \(v^*\) is bounded and continuous
• Starting from any bounded and continuous \(w\), the sequence \(w, Tw, T^2 w, \ldots\) generated by iteratively applying \(T\) converges uniformly to \(v^*\)

This iterative method is called value function iteration

We also know that a feasible policy is optimal if and only if it is \(v^*\)-greedy

It’s not too hard to show that a \(v^*\)-greedy policy exists (see EDTC, theorem 10.1.11 if you get stuck)

Hence at least one optimal policy exists

Our problem now is how to compute it

Unbounded Utility¶

The results stated above assume that the utility function is bounded

In practice economists often work with unbounded utility functions — and so will we

In the unbounded setting, various optimality theories exist

Unfortunately, they tend to be case specific, as opposed to valid for a large range of applications

Nevertheless, their main conclusions are usually in line with those stated for the bounded case just above (as long as we drop the word “bounded”)

Consult, for example, section 12.2 of EDTC, [Kam12] or [MdRV10]

Fitted Value Iteration¶

The first step is to compute the value function by value function iteration

In theory, the algorithm is as follows

1. Begin with a function \(w\) — an initial condition
2. Solving (11), obtain the function \(T w\)
3. Unless some stopping condition is satisfied, set \(w = Tw\) and go to step 2

This generates the sequence \(w, Tw, T^2 w, \ldots\)

However, there is a problem we must confront before we implement this procedure: The iterates can neither be calculated exactly nor stored on a computer

To see the issue, consider (11)

Even if \(w\) is a known function, unless \(Tw\) can be shown to have some special structure, the only way to store it is to record the value \(Tw(y)\) for every \(y \in \mathbb R_+\)

Clearly this is impossible

What we will do instead is use fitted value function iteration

The procedure is to record the value of the function \(Tw\) at only finitely many “grid” points \(y_1 < y_2 < \cdots < y_I\) and reconstruct it from this information when required

More precisely, the algorithm will be

1. Begin with an array of values \(\{ w_1, \ldots, w_I \}\) representing the values of some initial function \(w\) on the grid points \(\{ y_1, \ldots, y_I \}\)
2. Build a function \(\hat w\) on the state space \(\mathbb R_+\) by interpolation or approximation, based on these data points
3. Obtain and record the value \(T \hat w(y_i)\) on each grid point \(y_i\) by repeatedly solving (11)
4. Unless some stopping condition is satisfied, set \(\{ w_1, \ldots, w_I \} = \{ T \hat w(y_1), \ldots, T \hat w(y_I) \}\) and go to step 2

How should we go about step 2?

This is a problem of function approximation, and there are many ways to approach it

What’s important here is that the function approximation scheme must not only produce a good approximation to \(Tw\), but also combine well with the broader iteration algorithm described above

One good choice from both respects is continuous piecewise linear interpolation (see this paper for further discussion)

The next figure illustrates piecewise linear interpolation of an arbitrary function on grid points \(0, 0.2, 0.4, 0.6, 0.8, 1\)

import numpy as np
import matplotlib.pyplot as plt

def f(x):
    y1 = 2 * np.cos(6 * x) + np.sin(14 * x)
    return y1 + 2.5

c_grid = np.linspace(0, 1, 6)

def Af(x):
    return np.interp(x, c_grid, f(c_grid))

f_grid = np.linspace(0, 1, 150)

fig, ax = plt.subplots(figsize=(10, 6))
ax.set(xlim=(0, 1), ylim=(0, 6))
ax.plot(f_grid, f(f_grid), 'b-', lw=2, alpha=0.8, label='true function')
ax.plot(f_grid, Af(f_grid), 'g-', lw=2, alpha=0.8,
        label='linear approximation')
ax.vlines(c_grid, c_grid * 0, f(c_grid), linestyle='dashed', alpha=0.5)
ax.legend(loc='upper center')

plt.show()

Another advantage of piecewise linear interpolation is that it preserves useful shape properties such as monotonicity and concavity / convexity

The Bellman Operator¶

Here’s a function that implements the Bellman operator using linear interpolation

from scipy.optimize import fminbound


def bellman_operator(w, grid, β, u, f, shocks, Tw=None, compute_policy=0):
    """
    The approximate Bellman operator, which computes and returns the
    updated value function Tw on the grid points.  An array to store
    the new set of values Tw is optionally supplied (to avoid having to
    allocate new arrays at each iteration).  If supplied, any existing data in 
    Tw will be overwritten.

    Parameters
    ----------
    w : array_like(float, ndim=1)
        The value of the input function on different grid points
    grid : array_like(float, ndim=1)
        The set of grid points
    β : scalar
        The discount factor
    u : function
        The utility function
    f : function
        The production function
    shocks : numpy array
        An array of draws from the shock, for Monte Carlo integration (to
        compute expectations).
    Tw : array_like(float, ndim=1) optional (default=None)
        Array to write output values to
    compute_policy : Boolean, optional (default=False)
        Whether or not to compute policy function

    """
    # === Apply linear interpolation to w === #
    w_func = lambda x: np.interp(x, grid, w)

    # == Initialize Tw if necessary == #
    if Tw is None:
        Tw = np.empty_like(w)

    if compute_policy:
        σ = np.empty_like(w)

    # == set Tw[i] = max_c { u(c) + β E w(f(y  - c) z)} == #
    for i, y in enumerate(grid):
        def objective(c):
            return - u(c) - β * np.mean(w_func(f(y - c) * shocks))
        c_star = fminbound(objective, 1e-10, y)
        if compute_policy:
            σ[i] = c_star
        Tw[i] = - objective(c_star)

    if compute_policy:
        return Tw, σ
    else:
        return Tw

The arguments to bellman_operator are described in the docstring to the function

Notice that the expectation in (11) is computed via Monte Carlo, using the approximation

where \(\{\xi_i\}_{i=1}^n\) are IID draws from \(\phi\)

Monte Carlo is not always the most efficient way to compute integrals numerically but it does have some theoretical advantages in the present setting

(For example, it preserves the contraction mapping property of the Bellman operator — see, e.g., [PalS13])

An Example¶

Let’s test out our operator when

• \(f(k) = k^{\alpha}\)
• \(u(c) = \ln c\)
• \(\phi\) is the distribution of \(\exp(\mu + \sigma \zeta)\) when \(\zeta\) is standard normal

As is well-known (see [LS18], section 3.1.2), for this particular problem an exact analytical solution is available, with

The optimal consumption policy is

Let’s wrap this model in a class because we’ll use it some later lectures too

class LogLinearOG:
    """
    Log linear optimal growth model, with log utility, CD production and
    multiplicative lognormal shock, so that

        y = f(k, z) = z k^α

    with z ~ LN(μ, s).

    The class holds parameters and true value and policy functions.
    """

    def __init__(self, α=0.4, β=0.96, μ=0, s=0.1):

        self.α, self.β, self.μ, self.s = α, β, μ, s 

        # == Some useful constants == #
        self.ab = α * β
        self.c1 = np.log(1 - self.ab) / (1 - β)
        self.c2 = (μ + α * np.log(self.ab)) / (1 - α)
        self.c3 = 1 / (1 - β)
        self.c4 = 1 / (1 - self.ab)

    def u(self, c):
        " Utility "
        return np.log(c)

    def u_prime(self, c):
        return 1 / c

    def f(self, k):
        " Deterministic part of production function.  "
        return k**self.α

    def f_prime(self, k):
        return self.α * k**(self.α - 1)

    def c_star(self, y):
        " True optimal policy.  "
        return (1 - self.α * self.β) * y

    def v_star(self, y):
        " True value function. "
        return self.c1 + self.c2 * (self.c3 - self.c4) + self.c4 * np.log(y)

A First Test¶

To test our code, we want to see if we can replicate the analytical solution numerically, using fitted value function iteration

First, having run the code for the log linear model shown above, let’s generate an instance

lg = LogLinearOG()
# == Unpack parameters / functions for convenience == #
α, β, μ, s = lg.α, lg.β, lg.μ, lg.s
v_star = lg.v_star

We need a grid and some shock draws for Monte Carlo integration

grid_max = 4         # Largest grid point
grid_size = 200      # Number of grid points
shock_size = 250     # Number of shock draws in Monte Carlo integral

grid = np.linspace(1e-5, grid_max, grid_size)
shocks = np.exp(μ + s * np.random.randn(shock_size))

Now let’s do some tests

As one preliminary test, let’s see what happens when we apply our Bellman operator to the exact solution \(v^*\)

In theory, the resulting function should again be \(v^*\)

In practice we expect some small numerical error

w = bellman_operator(v_star(grid),
                     grid,
                     β,
                     np.log,
                     lambda k: k**α,
                     shocks)

fig, ax = plt.subplots(figsize=(9, 5))
ax.set_ylim(-35, -24)
ax.plot(grid, w, lw=2, alpha=0.6, label='$Tv^*$')
ax.plot(grid, v_star(grid), lw=2, alpha=0.6, label='$v^*$')
ax.legend(loc='lower right')
plt.show()

Here’s the output:

The two functions are essentially indistinguishable, so we are off to a good start

Now let’s have a look at iterating with the Bellman operator, starting off from an arbitrary initial condition

The initial condition we’ll start with is \(w(y) = 5 \ln (y)\)

w = 5 * np.log(grid)  # An initial condition
n = 35
fig, ax = plt.subplots(figsize=(9, 6))
ax.set_ylim(-40, 10)
ax.set_xlim(np.min(grid), np.max(grid))
lb = 'initial condition'
ax.plot(grid, w, color=plt.cm.jet(0), lw=2, alpha=0.6, label=lb)
for i in range(n):
    w = bellman_operator(w,
                         grid,
                         β,
                         np.log,
                         lambda k: k**α,
                         shocks)

    ax.plot(grid, w, color=plt.cm.jet(i / n), lw=2, alpha=0.6)

lb = 'true value function'
ax.plot(grid, v_star(grid), 'k-', lw=2, alpha=0.8, label=lb)
ax.legend(loc='lower right')
plt.show()

The figure shows

1. the first 36 functions generated by the fitted value function iteration algorithm, with hotter colors given to higher iterates
2. the true value function \(v^*\) drawn in black

The sequence of iterates converges towards \(v^*\)

We are clearly getting closer

We can write a function that iterates until the difference is below a particular tolerance level

def solve_optgrowth(initial_w, tol=1e-6, max_iter=500):

    w = initial_w  # Set initial condition
    error = tol + 1
    i = 0

    # == Create storage array for bellman_operator. Reduces  memory
    # allocation and speeds code up == #
    Tw = np.empty(len(grid))

    # Iterate to find solution
    while error > tol and i < max_iter:
        w_new = bellman_operator(w,
                                 grid,
                                 β,
                                 np.log,
                                 lambda k: k**α,
                                 shocks,
                                 Tw)
        error = np.max(np.abs(w_new - w))
        w[:] = w_new
        i += 1

    return w

We can check our result by plotting it against the true value

initial_w = 5 * np.log(grid)

fig, ax = plt.subplots(figsize=(9, 5))
ax.set_ylim(-35, -24)
ax.plot(grid, solve_optgrowth(initial_w), lw=2, alpha=0.6, label='approximate value function')
ax.plot(grid, v_star(grid), lw=2, alpha=0.6, label='true value function')
ax.legend(loc='lower right')
plt.show()

Alternatively, we can use QuantEcon’s compute_fixed_point function to converge to \(v^*\)

from quantecon import compute_fixed_point

initial_w = 5 * np.log(grid)

# Turn the Bellman operator into a function of one variable
T = lambda w: bellman_operator(w,
                               grid,
                               β,
                               np.log,
                               lambda k: k**α,
                               shocks,
                               compute_policy=False)

v_star_approx = compute_fixed_point(T, initial_w,
                                    error_tol=1e-5,     # error_tol
                                    max_iter=500,       # max_iter
                                    verbose=2,          # verbose
                                    print_skip=10,      # print_skip
                                    method='iteration')

Here’s the output

Iteration    Distance       Elapsed (seconds)
---------------------------------------------
10           7.052e-01      9.205e-01
20           4.683e-01      1.875e+00
30           3.114e-01      2.779e+00
40           2.070e-01      3.695e+00
50           1.376e-01      4.594e+00
60           9.149e-02      5.513e+00
70           6.083e-02      6.383e+00
80           4.044e-02      7.315e+00
90           2.689e-02      8.191e+00
100          1.787e-02      9.069e+00
110          1.188e-02      9.981e+00
120          7.901e-03      1.088e+01
130          5.253e-03      1.175e+01
140          3.492e-03      1.261e+01
150          2.322e-03      1.349e+01
160          1.544e-03      1.439e+01
170          1.026e-03      1.533e+01
180          6.822e-04      1.630e+01
190          4.536e-04      1.722e+01
200          3.016e-04      1.816e+01
210          2.005e-04      1.904e+01
220          1.333e-04      1.995e+01
230          8.861e-05      2.085e+01
240          5.891e-05      2.184e+01
250          3.917e-05      2.270e+01
260          2.604e-05      2.355e+01
270          1.731e-05      2.440e+01
280          1.151e-05      2.526e+01
284          9.776e-06      2.561e+01
Converged in 284 steps

Let’s have a look at the result

fig, ax = plt.subplots(figsize=(9, 5))
ax.set_ylim(-35, -24)
ax.plot(grid, v_star_approx, lw=2, alpha=0.6, label='approximate value function')
ax.plot(grid, v_star(grid), lw=2, alpha=0.6, label='true value function')
ax.legend(loc='lower right')
plt.show()

The figure shows that we are pretty much on the money

The Policy Function¶

To compute an approximate optimal policy, we take the approximate value function we just calculated and then compute the corresponding greedy policy

The next figure compares the result to the exact solution, which, as mentioned above, is \(\sigma(y) = (1 - \alpha \beta) y\)

Tw, σ = bellman_operator(v_star_approx,
                         grid,
                         β,
                         np.log,
                         lambda k: k**α,
                         shocks,
                         compute_policy=True)


fig, ax = plt.subplots(figsize=(9, 5))
ax.plot(grid, σ, lw=2, alpha=0.6, label='approximate policy function')
cstar = (1 - α * β) * grid
ax.plot(grid, cstar, lw=2, alpha=0.6, label='true policy function')
ax.legend(loc='lower right')
plt.show()

The figure shows that we’ve done a good job in this instance of approximating the true policy

Exercise 1¶

Once an optimal consumption policy \(\sigma\) is given, income follows (5)

The next figure shows a simulation of 100 elements of this sequence for three different discount factors (and hence three different policies)

In each sequence, the initial condition is \(y_0 = 0.1\)

The discount factors are discount_factors = (0.8, 0.9, 0.98)

We have also dialed down the shocks a bit

s = 0.05
shocks = np.exp(μ + s * np.random.randn(shock_size))

Otherwise, the parameters and primitives are the same as the log linear model discussed earlier in the lecture

Notice that more patient agents typically have higher wealth

Replicate the figure modulo randomness

Exercise 1¶

Here’s one solution (assuming as usual that you’ve executed everything above)

def simulate_og(σ, y0=0.1, ts_length=100):
    '''
    Compute a time series given consumption policy σ.
    '''
    y = np.empty(ts_length)
    ξ = np.random.randn(ts_length-1)
    y[0] = y0
    for t in range(ts_length-1):
        y[t+1] = (y[t] - σ(y[t]))**α * np.exp(μ + s * ξ[t])
    return y

fig, ax = plt.subplots(figsize=(9, 6))

for β in (0.8, 0.9, 0.98):

    Tw = np.empty(len(grid))
    initial_w = 5 * np.log(grid)

    v_star_approx = compute_fixed_point(bellman_operator,
                                        initial_w,
                                        1e-5,        # error_tol
                                        500,         # max_iter
                                        False,       # verbose
                                        5,           # print_skip
                                        'iteration',
                                        grid,
                                        β,
                                        np.log,
                                        lambda k: k**α,
                                        shocks,
                                        Tw=Tw,
                                        compute_policy=False)

    Tw, σ = bellman_operator(v_star_approx,
                             grid,
                             β,
                             np.log,
                             lambda k: k**α,
                             shocks,
                             compute_policy=True)

    σ_func = lambda x: np.interp(x, grid, σ)
    y = simulate_og(σ_func)
    ax.plot(y, lw=2, alpha=0.6, label=rf'$\beta = {β}$')


ax.legend(loc='lower right')
plt.show()