Foundations of Computational Economics #37¶

by Fedor Iskhakov, ANU

Dynamic programming theory and overview of solution methods¶

https://youtu.be/7Ta-zq2aXjc

Description: Overview of dynamic programming problem formulations and solution methods. Theoretical foundations of dynamic programming in infinite horizon. Contraction mappings and fixed points.

Plan¶

1. Classification of dynamic models
2. The list of solution methods and their domains
3. Contraction mappings and fixed points

General form of Bellman equation¶

$$ V(\text{state}) = \max_{\text{decisions}} \big[ U(\text{state},\text{decision}) + \beta \mathbb{E}\big\{ V(\text{next state}) \big| \text{state},\text{decision} \big\} \big] $$

• $ V(\text{state}) $ is value function = maximum attainable (discounted) expected reward/utility/payoff
• $ U(\text{state},\text{decision}) $ is per-period/flow/instantaneous reward/utility/payoff
• (next state) is the stochastic next period state resulting from current state and decision
• expectation $ \mathbb{E}\{\cdot\} $ is taken over the distribution of the next period state conditional on current state and decision
• $ \beta $ is a discount factor to measure future rewards in terms of current ones

The optimal choices are revealed along the solution of the Bellman equation as decisions which solve the maximization problem in the right hand side!

Variety of problems: existence of choice¶

Problems with no optimal choice (solved by dynamic programming)

• tiling problems (video 27)
• in computer science rather than economics

Dynamic (or sequential) discrete/discretized choice

• deal or no deal problem (video 27)
• inventory management model (video 27)
• Rust model of bus engine replacement (video 28, 29)
• cake eating problem (video 30, 32)
• consumption-savings problem (video 35)

Variety of problems: nature of choice¶

Problems with discrete choice

• deal or no deal problem, inventory management model (video 27)
• Rust model of bus engine replacement (video 28, 29)

Problems with continuous choice

• discretized: cake eating problem (video 30), consumption-savings models (video 35)
• treated as continuous: coming up next
• require interpolating of value function in Bellman equation

Problems with discrete and continuous choice

• much more complicated: kinks in value functions, discontinuous policy function
• problems go away if choices are discretized

What about state space?¶

• When choice is discrete, typically state space is also finite
• Even when state variables are continuous, by discretization it is converted to discrete

This is true in general when using numerical solvers: state space is discretized within some reasonable bounds

• choice of upper bounds, number and placement of grid points influence the (accuracy of the) solution

Another approach is to approximate the value function, for example, using orthogonal polynomials

• only works well when value function is sufficiently smooth

Variety of problems: continuity of time¶

Discrete time

• time periods $ t $, $ t+1 $
• dynamics given by difference equations

Continuous time

• all entities in the model are functions of time
• dynamics given by differential equation
• so, math is very different
• continuous time for cleaner theoretical models, sometimes also solved numerically
• not part of this course

Variety of problems: horizon¶

Finite horizon

• there is terminal period $ T $
• special form of Bellman equation in period $ T $
• value function and policy function are time dependent
• solved by backwards induction with $ T $ number of steps

Infinite horizon

• time subscripts are dropped, primes for next period values instead
• solution is given by fixed point of the Bellman operator
• have to actually solve a functional equation

Most problems can be specified in finite or infinite horizon

Variety of problems: stochasticity¶

Deterministic models

• No random elements, all motion rules deterministic
• No need for expectation operator in Bellman equation

Stochastic models with idiosyncratic shocks (Rust model, stochastic inventory dynamics)

• expectation does not have to be conditioned on current period shocks
• solving the fixed point in expected value function space is beneficial

General form stochastic models

• expectation in Bellman equation has to be computed with quadrature or Monte Carlo integration

Classification of dynamic models¶

• Discrete or continuous time?
• Finite or infinite horizon?
• Choice space (discrete, continuous, mixed)?
• State space (finite, discretized)?
• Stochastic or deterministic evolution of states?

Solving (discrete time) dynamic models¶

Various types of dynamic models require different implementations and admit various solution methods:

• Choice space (discrete, continuous, mixed)?
• State space (finite, discretized)?
• Stochastic or deterministic evolution of states?

$ \Rightarrow $ influence how Bellman operator is formulated and implemented numerically

• Choice space (discrete, continuous, mixed)?
• Finite or infinite horizon?

$ \Rightarrow $ decides which overall solution method can be applied

Solving finite horizon dynamic models¶

1. Standard backwards induction: solving Bellman equation sequentially (video 27)
2. Backwards induction using F.O.C. of Bellman maximization problem (for problems with continuous choice)
3. Finite horizon version of endogenous gridpoint method (for a particular class of problems)

Solving infinite horizon dynamic models¶

1. Value function iterations (successive approximations to solve for the fixed point of Bellman operator) (video 28-35)
2. Time iterations (successive approximations to solve for the fixed point of Coleman-Reffett operator in policy function space)
3. Policy iteration method (Howard’s policy improvement algorithm, iterative solution for the fixed point of Bellman operator)
4. Newton-Kantorovich method (Newton solver for the fixed point of Bellman operator)
5. Endogenous gridpoint method (for a particular class of problems)

Convergence of infinite horizon solution methods¶

• In infinite horizon all solution methods continue until convergence.
• How can we be sure that the algorithm would terminate?

The answer is given by the theory of contraction mappings:

• Bellman operator is generally a contraction mapping
• Banach theorem guarantees uniqueness of the fixed point, and
• successive approximation solver is globally convergent (works with any starting point)

Definition of contraction mapping¶

Let

• $ (S,\rho) $ be a complete metric space
• $ T: S \rightarrow S $ denote an operator mapping $ S $ to itself

$ T $ is called a contraction on $ S $ with modulus $ \lambda $ if $ 0 \le \lambda < 1 $ and

$$ \rho(Tx,Ty) \le \lambda \rho(x,y) \; \forall x,y \in S $$

Contraction mapping brings points in its domain “closer” to each other!

Simple example of contraction mapping¶

$$ \stackrel{\nearrow}{V} \quad \stackrel{\searrow}{c} \quad \stackrel{\searrow}{c} \quad \stackrel{\searrow}{c} \quad \dots $$

• interest rate $ r $
• What is the value of the annuity $ V $?

Value of annuity¶

$$ \stackrel{\nearrow}{V} \quad \stackrel{\searrow}{c} \quad \stackrel{\searrow}{c} \quad \stackrel{\searrow}{c} \quad \dots $$$$ V=\quad \frac{c}{(1+r)^0} + \quad \frac{c}{(1+r)^1} + \quad \frac{c}{(1+r)^2} + \quad \frac{c}{(1+r)^3} + \quad \dots $$$$ \beta = \frac{1}{1+r} $$$$ V=\quad c + \quad c \beta + \quad c \beta^2 + \quad c \beta^3 + \quad \dots = \sum_{t=0}^{\infty} \beta^t c $$

Answer by the geometric series formula¶

Assuming $ \beta<1 $

$$ V = \sum_{t=0}^{\infty} \beta^t c = \frac{c}{1-\beta} $$

Can reformulate recursively (as “Bellman equation” without choice)

$$ V = c + \beta ( c + \beta c + \beta^2 c + \dots ) = c + \beta V $$

Contraction!¶

$$ T(V) = c + \beta V $$$$ |T(V_1) - T(V_2)| = |(c + \beta V_1) - (c + \beta V_2)| = \beta | V_1 - V_2 | $$

• contraction mapping under Euclidean norm
• modulus $ \beta $

Successive approximations¶

1. Start with a guess $ V_0 $
2. Insert into the “Bellman equation”

$$ V_{i+1} = c + \beta V_i $$

1. Repeat until convergence

$$ ||V_{i}-V_{i-1}|| \le \varepsilon \text{ (small number)} $$

Banach contraction mapping theorem (fixed point theorem)¶

Let $ (S,\rho) $ be a complete metric space with a contraction mapping $ T: S \rightarrow S $. Then

1. $ T $ admits a unique fixed-point $ V^{\star} \in S $, i.e. $ T(V^{\star}) = V^{\star} $.
2. $ V^{\star} $ can be found by repeated application of the operator $ T $, i.e. $ T^n(V) \rightarrow V^{\star} $ as $ n\rightarrow \infty $.

In other words, the fixed point can be found by successive approximations from any starting point $ \rightarrow $ VFI method follows

What about Bellman operator?¶

$$ T(V)(\text{state}) = \max_{\text{decisions}} \big[ U(\text{state},\text{decision}) + \beta \mathbb{E}\big\{ V(\text{next state}) \big| \text{state},\text{decision} \big\} \big] $$

• Bellman operator $ T: U \rightarrow U $ from functional space $ U $ to itself
• metric space $ (U,d_{\infty}) $ with uniform/infinity/sup norm (max abs distance between functions over their domain)

Blackwell sufficient conditions for contraction¶

Let $ X \subseteq \mathbb{R}^n $ and $ B(x) $ be the space of bounded functions $ f: X \rightarrow \mathbb{R} $ defined on $ X $. Suppose that $ T: B(X) \rightarrow B(X) $ is an operator satisfying the following conditions:

1. (monotonicity) For any $ f,g \in B(X) $ and $ f(x) \le g(x) $ for all $ x\in X $ implies $ T(f)(x) \le T(g)(x) $ for all $ x\in X $,
2. (discounting) There exists $ \beta \in (0,1) $ such that

$$ T(f+a)(x) \le T(f)(x) + \beta a, \text{ for all } f\in B(X), a \ge 0, x\in X, $$

Then $ T $ is a contraction mapping with modulus $ \beta $.

Bellman operator is contraction mapping by Blackwell condition¶

• Monotonicity of Bellman equation follows trivially due to maximization in $ T(V)(x) $
• Discounting: satisfied by elementary argument when $ \beta<1 $

Under additional boundedness conditions, Bellman operator is a contraction mapping by Blackwell sufficient conditions

$ \Rightarrow $

• unique solution
• VFI algorithm is globally convergent
• does not depend on the numerical implementation of the Bellman operator

Examples of other contraction mappings¶

• All successive approximation examples (video 22)
• Markov chain stationary distributions
• Platform market equilibrium model
• Bellman operators in all infinite horizon models we have considered

Why do we need other solution algorithms?¶

Although VFI is guaranteed to find the solution, it may be very inefficient when modulus of contraction (discount factor $ \beta $) is close to one.

• Time iterations algorithm (sequentially solving F.O.C.) have the same linear convergence
• Newton-based method converge quadratically, but are not globally convergent, have to be initialized at their domain of attraction

Polyalgorithm would be a good idea!

Further learning resources¶

• Banach spaces crash course https://www.youtube.com/watch?v=yDdxFBcvSGw&list=PLBh2i93oe2qsGKDOsuVVw-OCAfprrnGfr&ab_channel=TheBrightSideOfMathematics
• Fixed points around us https://www.youtube.com/watch?v=csInNn6pfT4&ab_channel=Vsauce