Dynamic programming theory and overview of solution methods¶
Description: Overview of dynamic programming problem formulations and solution methods. Theoretical foundations of dynamic programming in infinite horizon. Contraction mappings and fixed points.
Plan¶
- Classification of dynamic models
- The list of solution methods and their domains
- 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¶
- Standard backwards induction: solving Bellman equation sequentially (video 27)
- Backwards induction using F.O.C. of Bellman maximization problem (for problems with continuous choice)
- Finite horizon version of endogenous gridpoint method (for a particular class of problems)
Solving infinite horizon dynamic models¶
- Value function iterations (successive approximations to solve for the fixed point of Bellman operator) (video 28-35)
- Time iterations (successive approximations to solve for the fixed point of Coleman-Reffett operator in policy function space)
- Policy iteration method (Howard’s policy improvement algorithm, iterative solution for the fixed point of Bellman operator)
- Newton-Kantorovich method (Newton solver for the fixed point of Bellman operator)
- 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¶
- Start with a guess $ V_0 $
- Insert into the “Bellman equation”
- Repeat until convergence
In [1]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
class annuity():
def __init__(self,c=1,beta=.9):
self.c = c # Annual payment
self.beta = beta # Discount factor
self.analytic = c/(1-beta) # compute analytic solution right away
def bellman(self,V):
'''Bellman equation'''
return self.c + self.beta*V
def solve(self, maxiter = 1000, tol=1e-4, verbose=False):
'''Solves the model using successive approximations'''
if verbose: print('{:<4} {:>15} {:>15}'.format('Iter','Value','Error'))
V0=0
for i in range(maxiter):
V1=self.bellman(V0)
if verbose: print('{:<4d} {:>15.8f} {:>15.8f}'.format(i,V1,V1-self.analytic))
if abs(V1-V0) < tol:
break
V0=V1
else: # when i went up to maxiter
print('No convergence: maximum number of iterations achieved!')
return V1
In [2]:
a = annuity(c=10,beta=0.954)
print('Analytic solution is',a.analytic)
print('Numeric solution is ',a.solve())
Analytic solution is 217.3913043478259 Numeric solution is 217.38928066546833
In [3]:
a.solve(verbose=True)
Iter Value Error 0 10.00000000 -207.39130435 1 19.54000000 -197.85130435 2 28.64116000 -188.75014435 3 37.32366664 -180.06763771 4 45.60677797 -171.78452637 5 53.50886619 -163.88243816 6 61.04745834 -156.34384600 7 68.23927526 -149.15202909 8 75.10026860 -142.29103575 9 81.64565624 -135.74564811 10 87.88995605 -129.50134829 11 93.84701808 -123.54428627 12 99.53005524 -117.86124910 13 104.95167270 -112.43963164 14 110.12389576 -107.26740859 15 115.05819655 -102.33310779 16 119.76551951 -97.62578484 17 124.25630562 -93.13499873 18 128.54051556 -88.85078879 19 132.62765184 -84.76365251 20 136.52677986 -80.86452449 21 140.24654798 -77.14475636 22 143.79520678 -73.59609757 23 147.18062726 -70.21067708 24 150.41031841 -66.98098594 25 153.49144376 -63.89986058 26 156.43083735 -60.96046700 27 159.23501883 -58.15628552 28 161.91020797 -55.48109638 29 164.46233840 -52.92896595 30 166.89707083 -50.49423351 31 169.21980557 -48.17149877 32 171.43569452 -45.95560983 33 173.54965257 -43.84165178 34 175.56636855 -41.82493580 35 177.49031560 -39.90098875 36 179.32576108 -38.06554327 37 181.07677607 -36.31452828 38 182.74724437 -34.64405998 39 184.34087113 -33.05043322 40 185.86119106 -31.53011329 41 187.31157627 -30.07972808 42 188.69524376 -28.69606059 43 190.01526255 -27.37604180 44 191.27456047 -26.11674388 45 192.47593069 -24.91537366 46 193.62203788 -23.76926647 47 194.71542414 -22.67588021 48 195.75851463 -21.63278972 49 196.75362295 -20.63768140 50 197.70295630 -19.68834805 51 198.60862031 -18.78268404 52 199.47262377 -17.91868057 53 200.29688308 -17.09442127 54 201.08322646 -16.30807789 55 201.83339804 -15.55790631 56 202.54906173 -14.84224262 57 203.23180489 -14.15949946 58 203.88314187 -13.50816248 59 204.50451734 -12.88678701 60 205.09730954 -12.29399481 61 205.66283330 -11.72847104 62 206.20234297 -11.18896138 63 206.71703520 -10.67426915 64 207.20805158 -10.18325277 65 207.67648120 -9.71482314 66 208.12336307 -9.26794128 67 208.54968837 -8.84161598 68 208.95640270 -8.43490165 69 209.34440818 -8.04689617 70 209.71456540 -7.67673895 71 210.06769539 -7.32360895 72 210.40458141 -6.98672294 73 210.72597066 -6.66533369 74 211.03257601 -6.35872834 75 211.32507751 -6.06622683 76 211.60412395 -5.78718040 77 211.87033425 -5.52097010 78 212.12429887 -5.26700548 79 212.36658112 -5.02472322 80 212.59771839 -4.79358596 81 212.81822335 -4.57308100 82 213.02858507 -4.36271928 83 213.22927016 -4.16203419 84 213.42072373 -3.97058062 85 213.60337044 -3.78793391 86 213.77761540 -3.61368895 87 213.94384509 -3.44745926 88 214.10242822 -3.28887613 89 214.25371652 -3.13758783 90 214.39804556 -2.99325879 91 214.53573546 -2.85556888 92 214.66709163 -2.72421272 93 214.79240542 -2.59889893 94 214.91195477 -2.47934958 95 215.02600485 -2.36529950 96 215.13480863 -2.25649572 97 215.23860743 -2.15269692 98 215.33763149 -2.05367286 99 215.43210044 -1.95920391 100 215.52222382 -1.86908053 101 215.60820152 -1.78310283 102 215.69022425 -1.70108010 103 215.76847394 -1.62283041 104 215.84312414 -1.54818021 105 215.91434043 -1.47696392 106 215.98228077 -1.40902358 107 216.04709585 -1.34420850 108 216.10892944 -1.28237491 109 216.16791869 -1.22338566 110 216.22419443 -1.16710992 111 216.27788148 -1.11342286 112 216.32909894 -1.06220541 113 216.37796038 -1.01334396 114 216.42457421 -0.96673014 115 216.46904379 -0.92226055 116 216.51146778 -0.87983657 117 216.55194026 -0.83936409 118 216.59055101 -0.80075334 119 216.62738566 -0.76391869 120 216.66252592 -0.72877843 121 216.69604973 -0.69525462 122 216.72803144 -0.66327291 123 216.75854200 -0.63276235 124 216.78764906 -0.60365528 125 216.81541721 -0.57588714 126 216.84190802 -0.54939633 127 216.86718025 -0.52412410 128 216.89128996 -0.50001439 129 216.91429062 -0.47701373 130 216.93623325 -0.45507110 131 216.95716652 -0.43413783 132 216.97713686 -0.41416749 133 216.99618856 -0.39511578 134 217.01436389 -0.37694046 135 217.03170315 -0.35960120 136 217.04824481 -0.34305954 137 217.06402555 -0.32727880 138 217.07908037 -0.31222398 139 217.09344267 -0.29786167 140 217.10714431 -0.28416004 141 217.12021567 -0.27108868 142 217.13268575 -0.25861860 143 217.14458221 -0.24672214 144 217.15593142 -0.23537292 145 217.16675858 -0.22454577 146 217.17708768 -0.21421666 147 217.18694165 -0.20436270 148 217.19634234 -0.19496201 149 217.20531059 -0.18599376 150 217.21386630 -0.17743805 151 217.22202845 -0.16927590 152 217.22981514 -0.16148921 153 217.23724365 -0.15406070 154 217.24433044 -0.14697391 155 217.25109124 -0.14021311 156 217.25754104 -0.13376331 157 217.26369415 -0.12761019 158 217.26956422 -0.12174013 159 217.27516427 -0.11614008 160 217.28050671 -0.11079764 161 217.28560340 -0.10570095 162 217.29046565 -0.10083870 163 217.29510423 -0.09620012 164 217.29952943 -0.09177492 165 217.30375108 -0.08755327 166 217.30777853 -0.08352582 167 217.31162072 -0.07968363 168 217.31528616 -0.07601818 169 217.31878300 -0.07252135 170 217.32211898 -0.06918537 171 217.32530151 -0.06600284 172 217.32833764 -0.06296671 173 217.33123411 -0.06007024 174 217.33399734 -0.05730701 175 217.33663346 -0.05467089 176 217.33914832 -0.05215603 177 217.34154750 -0.04975685 178 217.34383631 -0.04746803 179 217.34601984 -0.04528450 180 217.34810293 -0.04320142 181 217.35009020 -0.04121415 182 217.35198605 -0.03931830 183 217.35379469 -0.03750966 184 217.35552013 -0.03578421 185 217.35716621 -0.03413814 186 217.35873656 -0.03256779 187 217.36023468 -0.03106967 188 217.36166388 -0.02964046 189 217.36302735 -0.02827700 190 217.36432809 -0.02697626 191 217.36556900 -0.02573535 192 217.36675282 -0.02455153 193 217.36788219 -0.02342216 194 217.36895961 -0.02234474 195 217.36998747 -0.02131688 196 217.37096805 -0.02033630 197 217.37190352 -0.01940083 198 217.37279595 -0.01850839 199 217.37364734 -0.01765701 200 217.37445956 -0.01684479 201 217.37523442 -0.01606993 202 217.37597364 -0.01533071 203 217.37667885 -0.01462550 204 217.37735162 -0.01395272 205 217.37799345 -0.01331090 206 217.37860575 -0.01269860 207 217.37918989 -0.01211446 208 217.37974715 -0.01155720 209 217.38027878 -0.01102557 210 217.38078596 -0.01051839 211 217.38126980 -0.01003454 212 217.38173139 -0.00957295 213 217.38217175 -0.00913260 214 217.38259185 -0.00871250 215 217.38299262 -0.00831172 216 217.38337496 -0.00792938 217 217.38373971 -0.00756463 218 217.38408769 -0.00721666 219 217.38441965 -0.00688469 220 217.38473635 -0.00656800 221 217.38503848 -0.00626587 222 217.38532671 -0.00597764 223 217.38560168 -0.00570267 224 217.38586400 -0.00544035 225 217.38611426 -0.00519009 226 217.38635300 -0.00495135 227 217.38658076 -0.00472358 228 217.38679805 -0.00450630 229 217.38700534 -0.00429901 230 217.38720309 -0.00410125 231 217.38739175 -0.00391260 232 217.38757173 -0.00373262 233 217.38774343 -0.00356092 234 217.38790723 -0.00339711 235 217.38806350 -0.00324085 236 217.38821258 -0.00309177 237 217.38835480 -0.00294955 238 217.38849048 -0.00281387 239 217.38861992 -0.00268443 240 217.38874340 -0.00256095 241 217.38886121 -0.00244314 242 217.38897359 -0.00233076 243 217.38908080 -0.00222354 244 217.38918309 -0.00212126 245 217.38928067 -0.00202368
Out[3]:
217.38928066546833
Banach contraction mapping theorem (fixed point theorem)¶
Let $ (S,\rho) $ be a complete metric space with a contraction mapping $ T: S \rightarrow S $. Then
- $ T $ admits a unique fixed-point $ V^{\star} \in S $, i.e. $ T(V^{\star}) = V^{\star} $.
- $ 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:
- (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 $,
- (discounting) There exists $ \beta \in (0,1) $ such that
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