📖 Practice: infinite horizon

Drop the terminal period and backwards induction has nothing to start from: the Bellman equation becomes an equation in function space, solved by finding a fixed point. Why that point exists and is unique, and the two algorithms that find it.

Running the code for this lecture

The code for this class is in the folder session08-sep17/ of the course code repository. Today is a practical, so that folder holds the pre-code skeleton we fill in together, and the completed version appears there afterwards.

You should have cloned that repository already — if not, the instructions are in the algorithms and complexity lecture.

Update your copy before the class. Editing a file in place makes git pull refuse to update it, so discard whatever you changed while experimenting:

cd sb-dse-code
git reset --hard HEAD
git pull

Nothing in this repository is submitted, so experiment freely — but copy anything you want to keep out of it first, or commit that to a branch of your own.

Setting up the Python environment is covered in Python.

Contraction mappings and fixed points¶

Solution of a dynamic model in infinite horizon is the solution to the Bellman euqation which is an actual equation in function space

We rely on contraction properties of the Bellman operator to find the fixed point that in order to solve infinite horizon dynamic models

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

Example: the value of an annuity

\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$ ?

\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

Assuming $\beta<1$

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

But we can also reformulate recursively (as "Bellman equation" without choice)

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

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 to find the value of annuity

Start with a guess $V_0$
Insert into the "Bellman equation"

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

Repeat until convergence

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

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

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

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

217.38928066546833

Main solution algorithms for infinite horizon dynamic models¶

Value function iterations = successive approximations on the Bellman operator $\rightarrow$ to solve for the fixed point of Bellman operator
Policy iterations = Howard's policy improvement algorithm, iterative solution for the fixed point of Bellman operator
Newton-Kantorovich iterations = Newton solver for the fixed point of Bellman operator, mathematically identical to Howard's iterations

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)

In other words, the fixed point can be found by successive approximations from any starting point!

This immediately gives rise to the following solution algorithm

So is Bellman operator a contraction?¶

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)

Definition

Blackwell sufficient conditions for a 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)$

f(x) \le g(x) \implies T(f)(x) \le T(g)(x) \; \forall x\in X,

(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$ .

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

Why do we need other solution algorithms besides VFI?
What happens when the modulus of contraction is close to one?

Newton-based method converge quadratically if started from the basin of attraction
Polyalgorithm would be a good idea, see the poly-algorithm in the next lecture

Inventory dynamics problem with stochastic demand in infinite time¶

The model is given by the Bellman equation

\begin{array}{rcl} V(x_t,d_t) &=& \max_{q_t \ge 0} \Big\{ \pi_t + \beta \mathbb{E}\Big[ V\big(x_{t+1} , d_{t+1} \big) \Big| x_t,d_t,q_t \Big] \Big\} \\ &=& \max_{q_t \ge 0} \Big\{ s_t p - k_t r - c \mathbb{1}\{q_t>0\} + \beta \mathbb{E}\Big[ V\big( k_t, d_{t+1} \big) \Big] \Big\} \end{array}

\begin{array}{rcl} s_t &=& \min\{x_t,d_t\} \\ k_t &=& \max\{x_t-d_t,0\} + q_t \end{array}

Dropping the time subscripts¶

Because we’ll be solving the problem in infinite horizon, the time subscripts can be dropped, and we can just have current period variables $x,d,q,s,k$ , and next period variables denoted by prime, i.e. $x'$

The Bellman equation is then

\begin{array}{rcl} V(x,d) &=& \max_{q \ge 0} \Big\{ \pi + \beta \mathbb{E}\Big[ V\big(x', d' \big) \Big| x,d,q \Big] \Big\} \\ &=& \max_{q \ge 0} \Big\{ s\cdot p - k\cdot r - c \mathbb{1}\{q>0\} + \beta \mathbb{E}\Big[ V\big( k, d' \big) \Big] \Big\} \end{array}

\begin{array}{rcl} s &=& \min\{x,d\} \\ k &=& \max\{x-d,0\} + q \end{array}

Trick 1: Bellman equation in expected value function space¶

Idiosyncratic random shocks lead to the possibility of rewriting the Bellman equation in expected value function space, which reduces the dimensionality of the problem!

This is the EV trick in dynamic programming.

Define a new function, the expected value function $EV(x)$ as

EV(x') = \mathbb{E}\Big[ V\big(x', d' \big) \Big| x,d,q \Big] = \mathbb{E}\Big[ V\big(x', d' \big) \Big],

where the expectation is taken over the distribution of the next period demand $d'$ . The conditioning on $x,d,q$ can be dropped exactly because $d'$ is idiosyncratic.

We can then write the Bellman equation as

V(x,d) = \max_{q \ge 0} \Big\{ s\cdot p - k\cdot r - c \mathbb{1}\{q>0\} + \beta EV(k) \Big\}

V(x,d) = \max_{q \ge 0} \Big\{ p \min\{x,d\} - r ( \max\{x-d,0\} + q ) - c \mathbb{1}\{q>0\}

+ \beta EV(\max\{x-d,0\} + q) \Big\}

Taking the expectation with respect to $d$ on both sides, we get

EV(x) = \mathbb{E}\Big[ \max_{q \ge 0} \Big\{ p \min\{x,d\} - r ( \max\{x-d,0\} + q ) - c \mathbb{1}\{q>0\}

+ \beta EV(\max\{x-d,0\} + q) \Big\} \Big]

Compute the expectation by summing over all possible values of $d$ weighted by their probabilities $pr(d)$ , as

EV(x) = \sum_{d} \Big[ \max_{q \ge 0} \Big\{ p \min\{x,d\} - r ( \max\{x-d,0\} + q ) - c \mathbb{1}\{q>0\}

+ \beta EV(\max\{x-d,0\} + q) \Big\} \Big] pr(d)

This is functional equation in $EV$ which is also a contraction mapping!

Let as before demand have the truncated geometric distribution $pr_i = (1-\lambda)^i \lambda$ on $i \in \{0,1,\dots,N\}$ , with the last probability corrected for truncation.

Trick 2: Post-trade stock¶

The order is decided after trading, so it depends on what is left rather than on $x$ and $d$ separately. Let $y = \max\{x-d,0\} = x - \min\{x,d\}$ denote the post-trade stock:

\begin{array}{rcl} q^\star(x,d) &=& \arg\max_{q \ge 0} \Big\{ p \min\{x,d\} - (y + q)r - c \mathbb{1}\{q>0\} + \beta EV(y+q) \Big\}\\ &=& \arg\max_{q \ge 0} \Big\{ - q r - c \mathbb{1}\{q>0\} + \beta EV(y+q) \Big\} = q^\star(y) \end{array}

Everything that does not involve $q$ drops out of the $\arg\max$ , so the policy is a function of one variable. The solution of the model is then the pair

EV(x) = \sum_{d} \Big[ p \min\{x,d\} - yr + \max_{q \ge 0} \Big\{ -qr -c \mathbb{1}\{q>0\} + \beta EV(y+q) \Big\} \Big] pr(d)

q^\star(y) = \arg\max_{q \ge 0} \Big\{ -qr - c \mathbb{1}\{q>0\} + \beta EV(y+q) \Big\}

Practical task: solving the infinite horizon inventory model

We code this together in class, starting from session08-sep17/inventory_pre.ipynb. Pull the code repository before the class:

cd sb-dse-code && git pull

The Bellman operator in expected value function space, and the policy as a function of the post-trade stock $y$
A VFI solver on top of it, with a callback that plots the convergence path
What happens to the solution when parameters change, in particular the discount factor $\beta$ is close to one?

References¶

Sargent, T. J., & Stachurski, J. (2025). Dynamic Programming: Finite States. Cambridge University Press. 10.1017/9781009540780
Adda, J., & Cooper, R. W. (2023). Dynamic Economics: Quantitative Methods and Applications. MIT Press. https://mitpress.mit.edu/9780262547888/dynamic-economics
Rust, J. (2016). Dynamic programming. In The new palgrave dictionary of economics (pp. 1–26). Palgrave Macmillan UK. https://doi.org/10.1057/978-1-349-95121-5₁932-1
Ma, Q., & Stachurski, J. (2021). Dynamic Programming Deconstructed: Transformations of the Bellman Equation and Computational Efficiency. Operations Research, 69(5), 1591–1607. 10.1287/opre.2020.2006