37_dp_theory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Foundations of Computational Economics #37\n",
    "\n",
    "by Fedor Iskhakov, ANU\n",
    "\n",
    "<img src=\"_static/img/dag3logo.png\" style=\"width:256px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Dynamic programming theory and overview of solution methods\n",
    "\n",
    "<img src=\"_static/img/lecture.png\" style=\"width:64px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"_static/img/youtube.png\" style=\"width:65px;\">\n",
    "\n",
    "[https://youtu.be/7Ta-zq2aXjc](https://youtu.be/7Ta-zq2aXjc)\n",
    "\n",
    "Description: Overview of dynamic programming problem formulations and solution methods. Theoretical foundations of dynamic programming in infinite horizon. Contraction mappings and fixed points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Plan\n",
    "\n",
    "1. Classification of dynamic models  \n",
    "1. The list of solution methods and their domains  \n",
    "1. Contraction mappings and fixed points  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### General form of Bellman equation\n",
    "\n",
    "$$\n",
    "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]\n",
    "$$\n",
    "\n",
    "- $ V(\\text{state}) $ is **value function** = maximum attainable (discounted) expected reward/utility/payoff  \n",
    "- $ U(\\text{state},\\text{decision}) $ is per-period/flow/instantaneous reward/utility/payoff  \n",
    "- (*next state*) is the *stochastic* next period state resulting from current state and decision  \n",
    "- expectation $ \\mathbb{E}\\{\\cdot\\} $ is taken over the distribution of the next period state conditional on current state and decision  \n",
    "- $ \\beta $ is a discount factor to measure future rewards in terms of current ones  \n",
    "\n",
    "\n",
    "The optimal choices are revealed along the solution of the Bellman equation as decisions which solve the maximization problem in the right hand side!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Variety of problems: existence of choice\n",
    "\n",
    "Problems with no optimal choice (solved by dynamic programming)\n",
    "\n",
    "- tiling problems (video 27)  \n",
    "- in computer science rather than economics  \n",
    "\n",
    "\n",
    "Dynamic (or sequential) discrete/discretized choice\n",
    "\n",
    "- deal or no deal problem (video 27)  \n",
    "- inventory management model (video 27)  \n",
    "- Rust model of bus engine replacement (video 28, 29)  \n",
    "- cake eating problem (video 30, 32)  \n",
    "- consumption-savings problem (video 35)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Variety of problems: nature of choice\n",
    "\n",
    "Problems with discrete choice\n",
    "\n",
    "- deal or no deal problem, inventory management model (video 27)  \n",
    "- Rust model of bus engine replacement (video 28, 29)  \n",
    "\n",
    "\n",
    "Problems with continuous choice\n",
    "\n",
    "- discretized: cake eating problem (video 30), consumption-savings models (video 35)  \n",
    "- treated as continuous: coming up next  \n",
    "- require interpolating of value function in Bellman equation  \n",
    "\n",
    "\n",
    "Problems with discrete and continuous choice\n",
    "\n",
    "- much more complicated: kinks in value functions, discontinuous policy function  \n",
    "- problems go away if choices are discretized  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### What about state space?\n",
    "\n",
    "- When choice is discrete, typically state space is also finite  \n",
    "- Even when state variables are continuous, by discretization it is *converted* to discrete  \n",
    "\n",
    "\n",
    "This is true in general when using numerical solvers: state space is discretized within some reasonable bounds\n",
    "\n",
    "- choice of upper bounds, number and placement of grid points influence the (accuracy of the) solution  \n",
    "\n",
    "\n",
    "Another approach is to approximate the value function, for example, using orthogonal polynomials\n",
    "\n",
    "- only works well when value function is sufficiently smooth  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Variety of problems: continuity of time\n",
    "\n",
    "Discrete time\n",
    "\n",
    "- time periods $ t $, $ t+1 $  \n",
    "- dynamics given by difference equations  \n",
    "\n",
    "\n",
    "Continuous time\n",
    "\n",
    "- all entities in the model are functions of time  \n",
    "- dynamics given by differential equation  \n",
    "- so, math is very different  \n",
    "- continuous time for cleaner theoretical models, sometimes also solved numerically  \n",
    "- *not part of this course*  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Variety of problems: horizon\n",
    "\n",
    "Finite horizon\n",
    "\n",
    "- there is terminal period $ T $  \n",
    "- special form of Bellman equation in period $ T $  \n",
    "- value function and policy function are time dependent  \n",
    "- solved by backwards induction with $ T $ number of steps  \n",
    "\n",
    "\n",
    "Infinite horizon\n",
    "\n",
    "- time subscripts are dropped, primes for next period values instead  \n",
    "- solution is given by fixed point of the Bellman operator  \n",
    "- have to actually solve a functional equation  \n",
    "\n",
    "\n",
    "*Most problems can be specified in finite or infinite horizon*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Variety of problems: stochasticity\n",
    "\n",
    "Deterministic models\n",
    "\n",
    "- No random elements, all motion rules deterministic  \n",
    "- No need for expectation operator in Bellman equation  \n",
    "\n",
    "\n",
    "Stochastic models with idiosyncratic shocks (Rust model, stochastic inventory dynamics)\n",
    "\n",
    "- expectation does not have to be conditioned on current period shocks  \n",
    "- solving the fixed point in expected value function space is beneficial  \n",
    "\n",
    "\n",
    "General form stochastic models\n",
    "\n",
    "- expectation in Bellman equation has to be computed with quadrature or Monte Carlo integration  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Classification of dynamic models\n",
    "\n",
    "- Discrete or continuous time?  \n",
    "- Finite or infinite horizon?  \n",
    "- Choice space (discrete, continuous, mixed)?  \n",
    "- State space (finite, discretized)?  \n",
    "- Stochastic or deterministic evolution of states?  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Solving (discrete time) dynamic models\n",
    "\n",
    "Various types of dynamic models require different implementations and admit various solution methods:\n",
    "\n",
    "- Choice space (discrete, continuous, mixed)?  \n",
    "- State space (finite, discretized)?  \n",
    "- Stochastic or deterministic evolution of states?  \n",
    "\n",
    "\n",
    "$ \\Rightarrow $ influence how Bellman operator is formulated and implemented numerically\n",
    "\n",
    "- Choice space (discrete, continuous, mixed)?  \n",
    "- Finite or infinite horizon?  \n",
    "\n",
    "\n",
    "$ \\Rightarrow $ decides which overall solution method can be applied"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Solving finite horizon dynamic models\n",
    "\n",
    "1. Standard backwards induction: solving Bellman equation sequentially (video 27)  \n",
    "1. Backwards induction using F.O.C. of Bellman maximization problem (for problems with continuous choice)  \n",
    "1. Finite horizon version of endogenous gridpoint method (for a particular class of problems)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Solving infinite horizon dynamic models\n",
    "\n",
    "1. Value function iterations (successive approximations to solve for the fixed point of Bellman operator) (video 28-35)  \n",
    "1. Time iterations (successive approximations to solve for the fixed point of Coleman-Reffett operator in policy function space)  \n",
    "1. Policy iteration method (Howard’s policy improvement algorithm, iterative solution for the fixed point of Bellman operator)  \n",
    "1. Newton-Kantorovich method (Newton solver for the fixed point of Bellman operator)  \n",
    "1. Endogenous gridpoint method (for a particular class of problems)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Convergence of infinite horizon solution methods\n",
    "\n",
    "- In infinite horizon all solution methods continue until convergence.  \n",
    "- How can we be sure that the algorithm would terminate?  \n",
    "\n",
    "\n",
    "The answer is given by the theory of contraction mappings:\n",
    "\n",
    "- Bellman operator is generally a contraction mapping  \n",
    "- Banach theorem guarantees uniqueness of the fixed point, and  \n",
    "- successive approximation solver is globally convergent (works with any starting point)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Definition of contraction mapping\n",
    "\n",
    "Let\n",
    "- $ (S,\\rho) $ be a complete metric space\n",
    "- $ T: S \\rightarrow S $ denote an operator mapping $ S $ to itself\n",
    "\n",
    "$ T $ is called a *contraction* on $ S $ with modulus $ \\lambda $ if $ 0 \\le \\lambda < 1 $ and\n",
    "\n",
    "$$\n",
    "\\rho(Tx,Ty) \\le \\lambda \\rho(x,y) \\; \\forall x,y \\in S\n",
    "$$\n",
    "\n",
    "*Contraction mapping brings points in its domain “closer” to each other!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Simple example of contraction mapping\n",
    "\n",
    "$$\n",
    "\\stackrel{\\nearrow}{V} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\dots\n",
    "$$\n",
    "\n",
    "- interest rate $ r $  \n",
    "- What is the value of the annuity $ V $?  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Value of annuity\n",
    "\n",
    "$$\n",
    "\\stackrel{\\nearrow}{V} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\stackrel{\\searrow}{c} \\quad\n",
    "\\dots\n",
    "$$\n",
    "\n",
    "$$\n",
    "V=\\quad\n",
    "\\frac{c}{(1+r)^0} + \\quad\n",
    "\\frac{c}{(1+r)^1} + \\quad\n",
    "\\frac{c}{(1+r)^2} + \\quad\n",
    "\\frac{c}{(1+r)^3} + \\quad\n",
    "\\dots\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\beta = \\frac{1}{1+r}\n",
    "$$\n",
    "\n",
    "$$\n",
    "V=\\quad\n",
    "c + \\quad\n",
    "c \\beta + \\quad\n",
    "c \\beta^2 + \\quad\n",
    "c \\beta^3 + \\quad\n",
    "\\dots\n",
    "=\n",
    "\\sum_{t=0}^{\\infty} \\beta^t c\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Answer by the geometric series formula\n",
    "\n",
    "Assuming $ \\beta<1 $\n",
    "\n",
    "$$\n",
    "V = \\sum_{t=0}^{\\infty} \\beta^t c = \\frac{c}{1-\\beta}\n",
    "$$\n",
    "\n",
    "Can reformulate recursively (as “Bellman equation” without choice)\n",
    "\n",
    "$$\n",
    "V = c + \\beta ( c + \\beta c + \\beta^2 c + \\dots ) = c + \\beta V\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Contraction!\n",
    "\n",
    "$$\n",
    "T(V) = c + \\beta V\n",
    "$$\n",
    "\n",
    "$$\n",
    "|T(V_1) - T(V_2)| = |(c + \\beta V_1) - (c + \\beta V_2)| = \\beta | V_1 -  V_2 |\n",
    "$$\n",
    "\n",
    "- contraction mapping under Euclidean norm  \n",
    "- modulus $ \\beta $  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Successive approximations\n",
    "\n",
    "1. Start with a guess $ V_0 $  \n",
    "1. Insert into the “Bellman equation”  \n",
    "\n",
    "\n",
    "$$\n",
    "V_{i+1} = c + \\beta V_i\n",
    "$$\n",
    "\n",
    "1. Repeat until convergence  \n",
    "\n",
    "\n",
    "$$\n",
    "||V_{i}-V_{i-1}|| \\le \\varepsilon \\text{ (small number)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "class annuity():\n",
    "\n",
    "    def __init__(self,c=1,beta=.9):\n",
    "        self.c = c           # Annual payment\n",
    "        self.beta = beta     # Discount factor\n",
    "        self.analytic = c/(1-beta)  # compute analytic solution right away\n",
    "\n",
    "    def bellman(self,V):\n",
    "        '''Bellman equation'''\n",
    "        return self.c + self.beta*V\n",
    "\n",
    "    def solve(self, maxiter = 1000, tol=1e-4, verbose=False):\n",
    "        '''Solves the model using successive approximations'''\n",
    "        if verbose: print('{:<4} {:>15} {:>15}'.format('Iter','Value','Error'))\n",
    "        V0=0\n",
    "        for i in range(maxiter):\n",
    "            V1=self.bellman(V0)\n",
    "            if verbose: print('{:<4d} {:>15.8f} {:>15.8f}'.format(i,V1,V1-self.analytic))\n",
    "            if abs(V1-V0) < tol:\n",
    "                break\n",
    "            V0=V1\n",
    "        else:  # when i went up to maxiter\n",
    "            print('No convergence: maximum number of iterations achieved!')\n",
    "        return V1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Analytic solution is 217.3913043478259\n",
      "Numeric solution is  217.38928066546833\n"
     ]
    }
   ],
   "source": [
    "a = annuity(c=10,beta=0.954)\n",
    "print('Analytic solution is',a.analytic)\n",
    "print('Numeric solution is ',a.solve())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iter           Value           Error\n",
      "0        10.00000000   -207.39130435\n",
      "1        19.54000000   -197.85130435\n",
      "2        28.64116000   -188.75014435\n",
      "3        37.32366664   -180.06763771\n",
      "4        45.60677797   -171.78452637\n",
      "5        53.50886619   -163.88243816\n",
      "6        61.04745834   -156.34384600\n",
      "7        68.23927526   -149.15202909\n",
      "8        75.10026860   -142.29103575\n",
      "9        81.64565624   -135.74564811\n",
      "10       87.88995605   -129.50134829\n",
      "11       93.84701808   -123.54428627\n",
      "12       99.53005524   -117.86124910\n",
      "13      104.95167270   -112.43963164\n",
      "14      110.12389576   -107.26740859\n",
      "15      115.05819655   -102.33310779\n",
      "16      119.76551951    -97.62578484\n",
      "17      124.25630562    -93.13499873\n",
      "18      128.54051556    -88.85078879\n",
      "19      132.62765184    -84.76365251\n",
      "20      136.52677986    -80.86452449\n",
      "21      140.24654798    -77.14475636\n",
      "22      143.79520678    -73.59609757\n",
      "23      147.18062726    -70.21067708\n",
      "24      150.41031841    -66.98098594\n",
      "25      153.49144376    -63.89986058\n",
      "26      156.43083735    -60.96046700\n",
      "27      159.23501883    -58.15628552\n",
      "28      161.91020797    -55.48109638\n",
      "29      164.46233840    -52.92896595\n",
      "30      166.89707083    -50.49423351\n",
      "31      169.21980557    -48.17149877\n",
      "32      171.43569452    -45.95560983\n",
      "33      173.54965257    -43.84165178\n",
      "34      175.56636855    -41.82493580\n",
      "35      177.49031560    -39.90098875\n",
      "36      179.32576108    -38.06554327\n",
      "37      181.07677607    -36.31452828\n",
      "38      182.74724437    -34.64405998\n",
      "39      184.34087113    -33.05043322\n",
      "40      185.86119106    -31.53011329\n",
      "41      187.31157627    -30.07972808\n",
      "42      188.69524376    -28.69606059\n",
      "43      190.01526255    -27.37604180\n",
      "44      191.27456047    -26.11674388\n",
      "45      192.47593069    -24.91537366\n",
      "46      193.62203788    -23.76926647\n",
      "47      194.71542414    -22.67588021\n",
      "48      195.75851463    -21.63278972\n",
      "49      196.75362295    -20.63768140\n",
      "50      197.70295630    -19.68834805\n",
      "51      198.60862031    -18.78268404\n",
      "52      199.47262377    -17.91868057\n",
      "53      200.29688308    -17.09442127\n",
      "54      201.08322646    -16.30807789\n",
      "55      201.83339804    -15.55790631\n",
      "56      202.54906173    -14.84224262\n",
      "57      203.23180489    -14.15949946\n",
      "58      203.88314187    -13.50816248\n",
      "59      204.50451734    -12.88678701\n",
      "60      205.09730954    -12.29399481\n",
      "61      205.66283330    -11.72847104\n",
      "62      206.20234297    -11.18896138\n",
      "63      206.71703520    -10.67426915\n",
      "64      207.20805158    -10.18325277\n",
      "65      207.67648120     -9.71482314\n",
      "66      208.12336307     -9.26794128\n",
      "67      208.54968837     -8.84161598\n",
      "68      208.95640270     -8.43490165\n",
      "69      209.34440818     -8.04689617\n",
      "70      209.71456540     -7.67673895\n",
      "71      210.06769539     -7.32360895\n",
      "72      210.40458141     -6.98672294\n",
      "73      210.72597066     -6.66533369\n",
      "74      211.03257601     -6.35872834\n",
      "75      211.32507751     -6.06622683\n",
      "76      211.60412395     -5.78718040\n",
      "77      211.87033425     -5.52097010\n",
      "78      212.12429887     -5.26700548\n",
      "79      212.36658112     -5.02472322\n",
      "80      212.59771839     -4.79358596\n",
      "81      212.81822335     -4.57308100\n",
      "82      213.02858507     -4.36271928\n",
      "83      213.22927016     -4.16203419\n",
      "84      213.42072373     -3.97058062\n",
      "85      213.60337044     -3.78793391\n",
      "86      213.77761540     -3.61368895\n",
      "87      213.94384509     -3.44745926\n",
      "88      214.10242822     -3.28887613\n",
      "89      214.25371652     -3.13758783\n",
      "90      214.39804556     -2.99325879\n",
      "91      214.53573546     -2.85556888\n",
      "92      214.66709163     -2.72421272\n",
      "93      214.79240542     -2.59889893\n",
      "94      214.91195477     -2.47934958\n",
      "95      215.02600485     -2.36529950\n",
      "96      215.13480863     -2.25649572\n",
      "97      215.23860743     -2.15269692\n",
      "98      215.33763149     -2.05367286\n",
      "99      215.43210044     -1.95920391\n",
      "100     215.52222382     -1.86908053\n",
      "101     215.60820152     -1.78310283\n",
      "102     215.69022425     -1.70108010\n",
      "103     215.76847394     -1.62283041\n",
      "104     215.84312414     -1.54818021\n",
      "105     215.91434043     -1.47696392\n",
      "106     215.98228077     -1.40902358\n",
      "107     216.04709585     -1.34420850\n",
      "108     216.10892944     -1.28237491\n",
      "109     216.16791869     -1.22338566\n",
      "110     216.22419443     -1.16710992\n",
      "111     216.27788148     -1.11342286\n",
      "112     216.32909894     -1.06220541\n",
      "113     216.37796038     -1.01334396\n",
      "114     216.42457421     -0.96673014\n",
      "115     216.46904379     -0.92226055\n",
      "116     216.51146778     -0.87983657\n",
      "117     216.55194026     -0.83936409\n",
      "118     216.59055101     -0.80075334\n",
      "119     216.62738566     -0.76391869\n",
      "120     216.66252592     -0.72877843\n",
      "121     216.69604973     -0.69525462\n",
      "122     216.72803144     -0.66327291\n",
      "123     216.75854200     -0.63276235\n",
      "124     216.78764906     -0.60365528\n",
      "125     216.81541721     -0.57588714\n",
      "126     216.84190802     -0.54939633\n",
      "127     216.86718025     -0.52412410\n",
      "128     216.89128996     -0.50001439\n",
      "129     216.91429062     -0.47701373\n",
      "130     216.93623325     -0.45507110\n",
      "131     216.95716652     -0.43413783\n",
      "132     216.97713686     -0.41416749\n",
      "133     216.99618856     -0.39511578\n",
      "134     217.01436389     -0.37694046\n",
      "135     217.03170315     -0.35960120\n",
      "136     217.04824481     -0.34305954\n",
      "137     217.06402555     -0.32727880\n",
      "138     217.07908037     -0.31222398\n",
      "139     217.09344267     -0.29786167\n",
      "140     217.10714431     -0.28416004\n",
      "141     217.12021567     -0.27108868\n",
      "142     217.13268575     -0.25861860\n",
      "143     217.14458221     -0.24672214\n",
      "144     217.15593142     -0.23537292\n",
      "145     217.16675858     -0.22454577\n",
      "146     217.17708768     -0.21421666\n",
      "147     217.18694165     -0.20436270\n",
      "148     217.19634234     -0.19496201\n",
      "149     217.20531059     -0.18599376\n",
      "150     217.21386630     -0.17743805\n",
      "151     217.22202845     -0.16927590\n",
      "152     217.22981514     -0.16148921\n",
      "153     217.23724365     -0.15406070\n",
      "154     217.24433044     -0.14697391\n",
      "155     217.25109124     -0.14021311\n",
      "156     217.25754104     -0.13376331\n",
      "157     217.26369415     -0.12761019\n",
      "158     217.26956422     -0.12174013\n",
      "159     217.27516427     -0.11614008\n",
      "160     217.28050671     -0.11079764\n",
      "161     217.28560340     -0.10570095\n",
      "162     217.29046565     -0.10083870\n",
      "163     217.29510423     -0.09620012\n",
      "164     217.29952943     -0.09177492\n",
      "165     217.30375108     -0.08755327\n",
      "166     217.30777853     -0.08352582\n",
      "167     217.31162072     -0.07968363\n",
      "168     217.31528616     -0.07601818\n",
      "169     217.31878300     -0.07252135\n",
      "170     217.32211898     -0.06918537\n",
      "171     217.32530151     -0.06600284\n",
      "172     217.32833764     -0.06296671\n",
      "173     217.33123411     -0.06007024\n",
      "174     217.33399734     -0.05730701\n",
      "175     217.33663346     -0.05467089\n",
      "176     217.33914832     -0.05215603\n",
      "177     217.34154750     -0.04975685\n",
      "178     217.34383631     -0.04746803\n",
      "179     217.34601984     -0.04528450\n",
      "180     217.34810293     -0.04320142\n",
      "181     217.35009020     -0.04121415\n",
      "182     217.35198605     -0.03931830\n",
      "183     217.35379469     -0.03750966\n",
      "184     217.35552013     -0.03578421\n",
      "185     217.35716621     -0.03413814\n",
      "186     217.35873656     -0.03256779\n",
      "187     217.36023468     -0.03106967\n",
      "188     217.36166388     -0.02964046\n",
      "189     217.36302735     -0.02827700\n",
      "190     217.36432809     -0.02697626\n",
      "191     217.36556900     -0.02573535\n",
      "192     217.36675282     -0.02455153\n",
      "193     217.36788219     -0.02342216\n",
      "194     217.36895961     -0.02234474\n",
      "195     217.36998747     -0.02131688\n",
      "196     217.37096805     -0.02033630\n",
      "197     217.37190352     -0.01940083\n",
      "198     217.37279595     -0.01850839\n",
      "199     217.37364734     -0.01765701\n",
      "200     217.37445956     -0.01684479\n",
      "201     217.37523442     -0.01606993\n",
      "202     217.37597364     -0.01533071\n",
      "203     217.37667885     -0.01462550\n",
      "204     217.37735162     -0.01395272\n",
      "205     217.37799345     -0.01331090\n",
      "206     217.37860575     -0.01269860\n",
      "207     217.37918989     -0.01211446\n",
      "208     217.37974715     -0.01155720\n",
      "209     217.38027878     -0.01102557\n",
      "210     217.38078596     -0.01051839\n",
      "211     217.38126980     -0.01003454\n",
      "212     217.38173139     -0.00957295\n",
      "213     217.38217175     -0.00913260\n",
      "214     217.38259185     -0.00871250\n",
      "215     217.38299262     -0.00831172\n",
      "216     217.38337496     -0.00792938\n",
      "217     217.38373971     -0.00756463\n",
      "218     217.38408769     -0.00721666\n",
      "219     217.38441965     -0.00688469\n",
      "220     217.38473635     -0.00656800\n",
      "221     217.38503848     -0.00626587\n",
      "222     217.38532671     -0.00597764\n",
      "223     217.38560168     -0.00570267\n",
      "224     217.38586400     -0.00544035\n",
      "225     217.38611426     -0.00519009\n",
      "226     217.38635300     -0.00495135\n",
      "227     217.38658076     -0.00472358\n",
      "228     217.38679805     -0.00450630\n",
      "229     217.38700534     -0.00429901\n",
      "230     217.38720309     -0.00410125\n",
      "231     217.38739175     -0.00391260\n",
      "232     217.38757173     -0.00373262\n",
      "233     217.38774343     -0.00356092\n",
      "234     217.38790723     -0.00339711\n",
      "235     217.38806350     -0.00324085\n",
      "236     217.38821258     -0.00309177\n",
      "237     217.38835480     -0.00294955\n",
      "238     217.38849048     -0.00281387\n",
      "239     217.38861992     -0.00268443\n",
      "240     217.38874340     -0.00256095\n",
      "241     217.38886121     -0.00244314\n",
      "242     217.38897359     -0.00233076\n",
      "243     217.38908080     -0.00222354\n",
      "244     217.38918309     -0.00212126\n",
      "245     217.38928067     -0.00202368\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "217.38928066546833"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.solve(verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Banach contraction mapping theorem (fixed point theorem)\n",
    "\n",
    "Let $ (S,\\rho) $ be a complete metric space with a contraction mapping $ T: S \\rightarrow S $.\n",
    "Then\n",
    "\n",
    "1. $ T $ admits a unique fixed-point $ V^{\\star} \\in S $, i.e. $ T(V^{\\star}) = V^{\\star} $.  \n",
    "1. $ V^{\\star} $ can be found by repeated application of the operator $ T $, i.e. $ T^n(V) \\rightarrow V^{\\star} $ as $ n\\rightarrow \\infty $.  \n",
    "\n",
    "\n",
    "*In other words, the fixed point can be found by successive approximations from any starting point* $ \\rightarrow $ *VFI method follows*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### What about Bellman operator?\n",
    "\n",
    "$$\n",
    "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]\n",
    "$$\n",
    "\n",
    "- Bellman operator $ T: U \\rightarrow U $ from functional space $ U $ to itself  \n",
    "- metric space $ (U,d_{\\infty}) $ with uniform/infinity/sup norm (max abs distance between functions over their domain)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Blackwell sufficient conditions for contraction\n",
    "\n",
    "Let $ X \\subseteq \\mathbb{R}^n $ and $ B(x) $ be the space of bounded functions $ f: X \\rightarrow \\mathbb{R} $ defined on $ X $.\n",
    "Suppose that $ T: B(X) \\rightarrow B(X) $ is an operator satisfying the following conditions:\n",
    "\n",
    "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 $,  \n",
    "1. (discounting) There exists $ \\beta \\in (0,1) $ such that  \n",
    "\n",
    "\n",
    "$$\n",
    "T(f+a)(x) \\le T(f)(x) + \\beta a, \\text{ for all } f\\in B(X), a \\ge 0, x\\in X,\n",
    "$$\n",
    "\n",
    "Then $ T $ is a contraction mapping with modulus $ \\beta $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Bellman operator is contraction mapping by Blackwell condition\n",
    "\n",
    "- Monotonicity of Bellman equation follows trivially due to maximization in $ T(V)(x) $  \n",
    "- Discounting: satisfied by elementary argument when $ \\beta<1 $  \n",
    "\n",
    "\n",
    "Under additional boundedness conditions, **Bellman operator is a contraction mapping** by Blackwell sufficient conditions\n",
    "\n",
    "$ \\Rightarrow $\n",
    "\n",
    "- unique solution  \n",
    "- VFI algorithm is globally convergent  \n",
    "- does not depend on the numerical implementation of the Bellman operator  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Examples of other contraction mappings\n",
    "\n",
    "- All successive approximation examples (video 22)  \n",
    "- Markov chain stationary distributions  \n",
    "- Platform market equilibrium model  \n",
    "- Bellman operators in all infinite horizon models we have considered  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Why do we need other solution algorithms?\n",
    "\n",
    "Although VFI is guaranteed to find the solution, it may be very inefficient when modulus of contraction (discount factor $ \\beta $) is close to one.\n",
    "\n",
    "- Time iterations algorithm (sequentially solving F.O.C.) have the same linear convergence  \n",
    "- Newton-based method converge quadratically, but are not globally convergent, have to be initialized at their domain of attraction  \n",
    "\n",
    "\n",
    "Polyalgorithm would be a good idea!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Further learning resources\n",
    "\n",
    "- Banach spaces crash course [https://www.youtube.com/watch?v=yDdxFBcvSGw&list=PLBh2i93oe2qsGKDOsuVVw-OCAfprrnGfr&ab_channel=TheBrightSideOfMathematics](https://www.youtube.com/watch?v=yDdxFBcvSGw&list=PLBh2i93oe2qsGKDOsuVVw-OCAfprrnGfr&ab_channel=TheBrightSideOfMathematics)  \n",
    "- Fixed points around us [https://www.youtube.com/watch?v=csInNn6pfT4&ab_channel=Vsauce](https://www.youtube.com/watch?v=csInNn6pfT4&ab_channel=Vsauce)  "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "date": 1612589586.4162061,
  "download_nb": false,
  "filename": "37_dp_theory.rst",
  "filename_with_path": "37_dp_theory",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "title": "Foundations of Computational Economics #37"
 },
 "nbformat": 4,
 "nbformat_minor": 4
}