# 4. Discrete State Dynamic Programming¶

In addition to what’s in Anaconda, this lecture will need the following libraries:

!pip install --upgrade quantecon

Requirement already up-to-date: quantecon in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (0.5.1)

Requirement already satisfied, skipping upgrade: sympy in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (1.6.2)


## 4.1. Overview¶

In this lecture we discuss a family of dynamic programming problems with the following features:

1. a discrete state space and discrete choices (actions)

2. an infinite horizon

3. discounted rewards

4. Markov state transitions

We call such problems discrete dynamic programs or discrete DPs.

Discrete DPs are the workhorses in much of modern quantitative economics, including

• monetary economics

• search and labor economics

• household savings and consumption theory

• investment theory

• asset pricing

• industrial organization, etc.

When a given model is not inherently discrete, it is common to replace it with a discretized version in order to use discrete DP techniques.

This lecture covers

• the theory of dynamic programming in a discrete setting, plus examples and applications

• a powerful set of routines for solving discrete DPs from the QuantEcon code library

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import quantecon as qe
import scipy.sparse as sparse
from quantecon import compute_fixed_point
from quantecon.markov import DiscreteDP


### 4.1.1. How to Read this Lecture¶

We use dynamic programming many applied lectures, such as

The objective of this lecture is to provide a more systematic and theoretical treatment, including algorithms and implementation while focusing on the discrete case.

### 4.1.2. Code¶

Among other things, it offers

• a flexible, well-designed interface

• multiple solution methods, including value function and policy function iteration

• high-speed operations via carefully optimized JIT-compiled functions

• the ability to scale to large problems by minimizing vectorized operators and allowing operations on sparse matrices

JIT compilation relies on Numba, which should work seamlessly if you are using Anaconda as suggested.