Session 1 - Intro to RL, MDPs, exact solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introduction to RL, MDPs, and exact solutions\n",
    "## Deep RL Bootcamp - Florida International University\n",
    "### Miguel Alonso Jr - Associate Professor of Computer Science\n",
    "October 2019"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Logistics\n",
    "\n",
    "* Laptop setup - see [Deep RL ](https://github.com/drmaj/Deep-RL-Docker-Setup)\n",
    "* Register on the [Moodle](https://moodle.cis.fiu.edu/v3.1/login/index.php) course\n",
    "* Register on [Jupyter Hub](https://drlbc.cs.fiu.edu)\n",
    "* Keep your laptops charged!\n",
    "* 2 - 2hr sessions per day - 5 days"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Goals\n",
    "\n",
    "After completing this course, students will be able to:\n",
    "1. Master fundamental concepts in Deep RL;\n",
    "2. Master problems to which Deep RL can be applied;\n",
    "3. Demonstrate various Deep RL solutions for Model-free and Model-based problems;\n",
    "4. Demonstrate state-of-the-art methods in Deep RL from scratch;\n",
    "5. Demonstrate the ability to solve machine learning problems in new domains using Deep RL."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Bootcamp Schedule\n",
    "\n",
    "| Day | Date       | Session |                             Description                             |                 Materials                 |\n",
    "|:---:|------------|:-------:|:-------------------------------------------------------------------:|:-----------------------------------------:|\n",
    "|  1  | 10/24/2019 |    1    |             Introduction to RL, MDPs and Exact Solutions            | S1 Jupyter Notebook, Deep RL Docker Setup |\n",
    "|     |            |    2    |                        Intro to Deep Learning                       |            S2 Jupyter Notebook            |\n",
    "|  2  | 10/31/2019 |    3    |      Model-free - Value-based methods - Deep Q-Learning and DQN     |            S3 Jupyter Notebook            |\n",
    "|     |            |    4    | Model-free - Policy Gradient methods - Proximal Policy Optimization |             S4 Jupter Notebook            |\n",
    "|  3  | 11/7/2019  |    5    |                  Model-based Methods - Deep Dyna-Q                  |            S5 Jupyter Notebook            |\n",
    "|     |            |    6    |         Deep RL in Online Settings - Deep Contextual Bandits        |            S6 Jupyter Notebook            |\n",
    "|  4  | 11/14/2019 |    7    |        Partially Observable MDPs - Deep Recurrent Q-Learning        |            S7 Juptyer Notebook            |\n",
    "|     |            |    8    |                              Inverse RL                             |            S8 Jupyter Notebook            |\n",
    "|  5  | 11/21/2019 |    9    |                           Case Study: TBD                           |            S9 Jupyter Notebook            |\n",
    "|     |            |    10   |                           Case Study: TBD                           |            S10 Jupyter Notebook           |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Markov Decision Processes\n",
    "\n",
    "![markov decision process](http://billy-inn.github.io/images/rl1.1.png)\n",
    "(Source: Sutton and Barto, Reinforcment Learing: An Introduction )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Formal Definition of MDP\n",
    "\n",
    "An MDP is a tuple $(S, A, {P_sa}, \\gamma, R)$, where:\n",
    "* $S$ is a set of states, $S \\in \\{s_0, s_1, \\dots s_m\\}$\n",
    "* $A$ is a set of actions, $A \\in \\{a_0, a_1, \\dots a_m\\}$\n",
    "* $P_{a}(s, s')$ are the state transition probabilities given an action $a$.\n",
    "* $\\gamma$  is called the discount factor, and controls the influence of future rewards in the present, and is on the interval $[0, 1]$\n",
    "* $R:S \\times A \\mapsto \\mathbb{R}$ is the **reward function**, which returns a real value every time the agent moves from one state to the other due to an action.\n",
    "* $H$ is the time horizon (can be finite or infinite)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# MDP Key Points\n",
    "\n",
    "* For each state $s \\in S$ and action $a \\in A$, $P_{sa}$ is a probability distribution over the state space. $P_{sa}$ gives the distribution over what states the system will transition to if action $a$ is taken when the system is in state $s$.\n",
    "*  $\\{\\gamma \\in \\mathbb{R} \\hspace{1mm}| \\hspace{1mm}0 \\leq \\gamma \\leq 1\\}$ \n",
    "* Sometimes the reward function is written as a function of the state only, $R:S \\mapsto \\mathbb{R}$\n",
    "* The reward function can be written as $R(s, a, s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Example MDP: Gridworld\n",
    "Simple gridworld from Artificial Intelligence: A modern approach - Russel and Norvig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 12)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import gym # import openai gym\n",
    "import gridworldsgym # import gridworldsgym - see: https://github.com/drmaj/gridworldsgym\n",
    "from gridworldsgym.envs import gridworld\n",
    "\n",
    "# make gridworld environment\n",
    "env = gym.make('GridWorld-v0')\n",
    "# print number of states and actions\n",
    "env.num_actions, env.num_states"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Example MDP: Gridworld"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAcEAAAFTCAYAAABBFbegAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAATp0lEQVR4nO3dfaykZX2H8etbQGzUVBCz2S7birpNg027ki2l0RhqowJtupgYs6ap1JCsaTHR1KYFTZQ2NalNldbUYtdCQasirRo2xrYiQuw/AruKvBbZCoTdLGytr60JFvj1j7lXxt1z9rzN7Dxz7uuTnJyZe545cz/c5+TaeeZhJlWFJEk9+olZT0CSpFkxgpKkbhlBSVK3jKAkqVtGUJLULSMoSerW1CKY5Lwk9yfZl+TSaT2OJEmrlWn8f4JJTgC+DrwK2A/cDryhqu6d+INJkrRK03omeDawr6q+UVU/BK4Dtk/psSRJWpUTp/RzNwGPjF3fD/zKYhsn8W1rJEmT8s2qev5yNpxWBJeUZCewc1aPL0latx5e7obTiuABYPPY9dPb2I9U1S5gF/hMUJI0G9N6TfB2YEuSM5I8A9gB7J7SY0mStCpTeSZYVU8keQvwb8AJwNVVdc80HkuSpNWayv8iseJJLHA4dAjz6lWSo8Zcj9lxPYbF9RiWhdYD2FtV25Zzf98xRpLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsITsHvvuvvZj0FSdIyGMEJM4CSND+M4JQYQ0kaPiM4QYZPkuaLEZwioyhJw2YEJ8TgSdL8MYJTZhwlabiM4AQYOkmaT0bwODCSkjRMRnCNDJwkzS8jeJwYS0kaHiO4BoZNkuabETyOjKYkDYsRXCWDJknzb00RTPJQkruS3JFkTxs7NcmNSR5o30+ZzFTXB+MpScMxiWeCv1ZVW6tqW7t+KXBTVW0BbmrX1xVDJknrwzQOh24Hrm2XrwUunMJjzDUjKknDsNYIFvD5JHuT7GxjG6rqYLv8KLBhjY8xKAZMktaPtUbw5VV1FnA+cEmSV4zfWFXFKJRHSbIzyZ7DryX2xphK0uytKYJVdaB9PwR8BjgbeCzJRoD2/dAi991VVdvGXkscPMMlSevLqiOY5FlJnnP4MvBq4G5gN3BR2+wi4Ia1TnK9MqqSNFsnruG+G4DPJDn8cz5eVf+a5Hbg+iQXAw8Dr1/7NGfPYEnS+pPRy3YznkRy1CSGMK9x04zgNX/65qn97NVo/7D5MUNbj564HsPiegzLQusB7F3uS22+Y8wy+CxQktYnIzgARlaSZsMILsFASdL6ZQQHwthK0vFnBI/BMEnS+mYEB8ToStLxZQQXYZAkaf0zggNjfCXp+DGCCzBEktQHIzhARliSjg8jeAQDJEn9MIIDZYwlafqM4BjDI0l9MYIDZpQlabqMYGNwJKk/RnDgjLMkTY8RxNBIUq+M4Bww0pI0Hd1H0MBIUr+6j+C8MNaSNHldR9CwSFLfuo7gvDHakjRZ3UbQoEiSuo3gvDLekjQ5XUbQkEiSoNMIzjsjLkmT0V0EDYgk6bBU1aznQJKjJjGEefUqyVFjrsfsuB7D4noMy0LrAeytqm3LuX93zwQlSTrMCEqSumUEJUndMoKSpG4ZQUlSt4ygJKlbRlCS1C0jKEnqlhGUJHXLCEqSumUEJUndMoKSpG4ZQUlSt5aMYJKrkxxKcvfY2KlJbkzyQPt+ShtPkg8k2ZfkziRnTXPykiStxXKeCV4DnHfE2KXATVW1BbipXQc4H9jSvnYCV05mmpIkTd6SEayqLwHfOmJ4O3Btu3wtcOHY+Edq5MvAc5NsnNRkJUmapBNXeb8NVXWwXX4U2NAubwIeGdtufxs7yAot8kGJmhHXY1hcj2FxPebXaiP4I1VVC30y/FKS7GR0yFSSpJlY7dmhjx0+zNm+H2rjB4DNY9ud3saOUlW7qmpbVW1b5RwkSVqT1UZwN3BRu3wRcMPY+BvbWaLnAN8dO2wqSdKgLHk4NMkngHOB05LsB94N/DlwfZKLgYeB17fNPwdcAOwDfgC8aQpzliRpIlK14pfzJj+JBV5THMK8enXki/znnnvubCYiAG655Zajxvz7mJ0j/z5cidla5JSkvct9qc13jJEkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdWvJCCa5OsmhJHePjV2e5ECSO9rXBWO3XZZkX5L7k7xmWhOXJGmtlvNM8BrgvAXGr6iqre3rcwBJzgR2AC9p9/nbJCdMarKSJE3SkhGsqi8B31rmz9sOXFdVj1fVg8A+4Ow1zE+SpKlZy2uCb0lyZztcekob2wQ8MrbN/jZ2lCQ7k+xJsmcNc5AkadVWG8ErgRcBW4GDwPtW+gOqaldVbauqbaucgyRJa7KqCFbVY1X1ZFU9BXyYpw95HgA2j216ehuTJGlwVhXBJBvHrr4WOHzm6G5gR5KTk5wBbAFuW9sUJUmajhOX2iDJJ4BzgdOS7AfeDZybZCtQwEPAmwGq6p4k1wP3Ak8Al1TVk9OZuiRJa7NkBKvqDQsMX3WM7d8DvGctk5Ik6XjwHWMkSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd1aMoJJNie5Ocm9Se5J8tY2fmqSG5M80L6f0saT5ANJ9iW5M8lZ094JSZJWYznPBJ8A3l5VZwLnAJckORO4FLipqrYAN7XrAOcDW9rXTuDKic9akqQJWDKCVXWwqr7SLn8fuA/YBGwHrm2bXQtc2C5vBz5SI18Gnptk48RnLknSGp24ko2TvAB4KXArsKGqDrabHgU2tMubgEfG7ra/jR0cGyPJTkbPFBd7rJVMTeqKfx/SZCw7gkmeDXwKeFtVfW/8j7CqKkmt5IGrahewq/3sFd1Xx9ctt9wy6ylIg+U/R+bbss4OTXISowB+rKo+3YYfO3yYs30/1MYPAJvH7n56G5MkaVCWc3ZogKuA+6rq/WM37QYuapcvAm4YG39jO0v0HOC7Y4dNJUkajFQd+0hkkpcD/w7cBTzVht/B6HXB64GfAR4GXl9V32rR/BvgPOAHwJuqas8Sj+HhUEnSpOytqm3L2XDJCB4PC0VwCPPq1UInXbges+N6DMtR6+FSzNbCL8ouO4K+Y4wkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtLRjDJ5iQ3J7k3yT1J3trGL09yIMkd7euCsftclmRfkvuTvGaaOyBJ0mqduIxtngDeXlVfSfIcYG+SG9ttV1TVX45vnORMYAfwEuCngS8k+bmqenKSE5ckaa2WfCZYVQer6ivt8veB+4BNx7jLduC6qnq8qh4E9gFnT2KykiRN0opeE0zyAuClwK1t6C1J7kxydZJT2tgm4JGxu+1ngWgm2ZlkT5I9K561JEkTsOwIJnk28CngbVX1PeBK4EXAVuAg8L6VPHBV7aqqbVW1bSX3kyRpUpYVwSQnMQrgx6rq0wBV9VhVPVlVTwEf5ulDngeAzWN3P72NSZI0KMs5OzTAVcB9VfX+sfGNY5u9Fri7Xd4N7EhycpIzgC3AbZObsiRJk7Gcs0NfBvwOcFeSO9rYO4A3JNkKFPAQ8GaAqronyfXAvYzOLL3EM0MlSUOUqpr1HEhy1CSGMK9ejZ78/zjXY3Zcj2E5aj1citk6+s8DYO9yzzfxHWMkSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdcsISpK6ZQQlSd1aMoJJnpnktiRfS3JPkj9p42ckuTXJviSfTPKMNn5yu76v3f6C6e6CJEmrs5xngo8Dr6yqXwK2AuclOQd4L3BFVb0Y+DZwcdv+YuDbbfyKtp0kSYOzZARr5H/a1ZPaVwGvBP65jV8LXNgub2/Xabf/epJMbMaSJE3IicvZKMkJwF7gxcAHgf8EvlNVT7RN9gOb2uVNwCMAVfVEku8CzwO+ecTP3AnsPMZjLn8vNHWux7C4HtJkLCuCVfUksDXJc4HPAD+/1geuql3ALoAktdafJ0kz4b9H5tqKzg6tqu8ANwO/Cjw3yeGIng4caJcPAJsB2u0/Bfz3RGYrSdIELefs0Oe3Z4Ak+UngVcB9jGL4urbZRcAN7fLudp12+xerymd6kqTBWc7h0I3Ate11wZ8Arq+qzya5F7guyZ8BXwWuattfBXw0yT7gW8COKcxbkqQ1yxCepCX5L+B/OeLkmTl1Gu7HkKyH/VgP+wDux9Cs5/342ap6/nLuPIgIAiTZU1XbZj2PtXI/hmU97Md62AdwP4bG/RjxbdMkSd0ygpKkbg0pgrtmPYEJcT+GZT3sx3rYB3A/hsb9YECvCUqSdLwN6ZmgJEnH1cwjmOS8JPe3j166dNbzWYkkDyW5K8kdSfa0sVOT3Jjkgfb9lFnP80hJrk5yKMndY2MLzjsjH2jrc2eSs2Y38x+3yH5cnuRAW5M7klwwdttlbT/uT/Ka2cz6aEk2J7k5yb3t48re2sbnak2OsR9ztSbr5ePjjrEf1yR5cGw9trbxQf5ewej9q5N8Ncln2/XJrUVVzewLOIHRm3G/EHgG8DXgzFnOaYXzfwg47YixvwAubZcvBd4763kuMO9XAGcBdy81b+AC4F8YvUPiOcCts57/EvtxOfCHC2x7Zvv9Ohk4o/3enTDrfWhz2wic1S4/B/h6m+9crckx9mOu1qT9d312u3wScGv773w9sKONfwj4vXb594EPtcs7gE/Oeh+W2I9rgNctsP0gf6/a3P4A+Djw2XZ9Ymsx62eCZwP7quobVfVD4DpGH8U0z8Y/Smr8I6YGo6q+xOjdfMYtNu/twEdq5MuM3jN24/GZ6bEtsh+L2Q5cV1WPV9WDwD5Gv38zV1UHq+or7fL3Gb0t4SbmbE2OsR+LGeSatP+uc//xccfYj8UM8vcqyenAbwB/366HCa7FrCP4o49dasY/kmkeFPD5JHsz+mgogA1VdbBdfhTYMJuprdhi857HNXpLO5xz9djh6LnYj3b45qWM/tU+t2tyxH7AnK1JO/x2B3AIuJEVfHwccPjj42buyP2oqsPr8Z62HlckObmNDXU9/gr4I+Cpdv15THAtZh3BeffyqjoLOB+4JMkrxm+s0XPyuTv9dl7n3VwJvAjYChwE3jfb6SxfkmcDnwLeVlXfG79tntZkgf2YuzWpqieraiujT8g5mwl8fNwsHLkfSX4BuIzR/vwycCrwxzOc4jEl+U3gUFXtndZjzDqCP/rYpWb8I5kGr6oOtO+HGH3O4tnAY4cPIbTvh2Y3wxVZbN5ztUZV9Vj7w38K+DBPH14b9H4kOYlROD5WVZ9uw3O3Jgvtx7yuCayfj48b24/z2mHrqqrHgX9g2OvxMuC3kjzE6OWyVwJ/zQTXYtYRvB3Y0s70eQajFzJ3z3hOy5LkWUmec/gy8Grgbn78o6TGP2Jq6Bab927gje3MsXOA744dohucI17DeC2jNYHRfuxoZ4+dAWwBbjve81tIe83iKuC+qnr/2E1ztSaL7ce8rUnWycfHLbIf/zH2D6swei1tfD0G9XtVVZdV1elV9QJGffhiVf02k1yLaZ/Vs9QXozOSvs7omPs7Zz2fFcz7hYzObPsacM/huTM6/nwT8ADwBeDUWc91gbl/gtFhqf9jdDz94sXmzehMsQ+29bkL2Dbr+S+xHx9t87yz/UFsHNv+nW0/7gfOn/X8x+b1ckaHOu8E7mhfF8zbmhxjP+ZqTYBfZPTxcHcyCsS72vgLGUV6H/BPwMlt/Jnt+r52+wtnvQ9L7McX23rcDfwjT59BOsjfq7H9OZenzw6d2Fr4jjGSpG7N+nCoJEkzYwQlSd0ygpKkbhlBSVK3jKAkqVtGUJLULSMoSeqWEZQkdev/AQKvw1oeIzutAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 522x522 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# we'll need these to display the gym's output\n",
    "%matplotlib inline\n",
    "from IPython import display\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt \n",
    "plt.rcParams['figure.figsize'] = [7.25, 7.25]\n",
    "state = env.reset()\n",
    "plt.imshow(env.render(mode='rgb_array'))\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "print(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Move to the right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAU8AAAD8CAYAAAD35CadAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAARH0lEQVR4nO3df6xkZX3H8fen/LIRUkHMZru7LaDbNNjoQraURmKoxgq06WJiyJK2oiFZ00KiqU0Lmig1MalNlda0RddCQasirRo2xrYiQuw/8mMRlwWKrPwIu1nYKoq0Jljg2z/mWZi73Lv33ufO3Jm9+34lkznnOWfmfO8zs599zjn3nJuqQpK0OD836QIk6VBkeEpSB8NTkjoYnpLUwfCUpA6GpyR1GFt4JjknyQNJdiW5bFzbkaRJyDh+zzPJEcD3gLcAu4E7gAur6r6Rb0ySJmBcI88zgF1V9VBV/Qy4Htg0pm1J0rI7ckzvuwZ4bGh+N/Abc62cxMucJE3SD6rqVYt5wbjCc15JtgBbJrV9SRry6GJfMK7w3AOsG5pf29peUFVbga3gyFPSoWdcxzzvANYnOTnJ0cBmYNuYtiVJy24sI8+qejbJpcB/AEcA11TVvYt4/TjKOiQlmTFv38w03D/2zUx+d+Z2YN90vcc0dOiBu+3TUNO08B/AwRmec/O7M7dZwnN7VW1czHt4hZEkdTA8JamD4SlJHQxPSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqYPhKUkdDE9J6mB4SlIHw1OSOhiektTB8JSkDoanJHUwPCWpg+F5mHnnBz/FOz/4qUmXIR3yDM/DlCEqLc24/m67DhHDAXrth989wUqkQ4sjT73Akai0cIanZnB3XloYw1OzMkSlgzM8dVCGqDQ7TxhpQTyxJM3kyFOL5khUWuLIM8kjwNPAc8CzVbUxyQnAF4GTgEeAC6rqR0srU9Nmf4A6CtXhahQjz9+qqg1VtbHNXwbcXFXrgZvbvFYoj4nqcDWO3fZNwHVt+jrg/DFsQ1PGENXhZqknjAr4epICPlVVW4FVVbW3LX8cWDXbC5NsAbYscfuaMp5Y0uFiqSPPs6rqdOBc4JIkbxxeWFXFIGBfoqq2VtXGod19rTCORLWSLSk8q2pPe94HfAU4A3giyWqA9rxvqUXq0OXuvFaq7vBM8vIkx+2fBn4b2AlsAy5qq10E3LjUInXoM0S10izlmOcq4CtJ9r/P56vq35PcAdyQ5GLgUeCCpZeplcJfcdJK0R2eVfUQ8PpZ2n8IvHkpRUnStPPyTC0rR5xaKbw8U8vG4NRK4shTY2VgaqVy5KmxMTi1kjny1EgZmDpcGJ4aCUNThxt327VkBqcOR4481cXA1OHOkacWzeCUHHlqgQxMaSbDUwdlaEqzc7ddczI4pbk58tQMBqa0MI489QKDU1o4R56HOQNT6mN4HqYMTWlp3G0/DBmc0tJl8AcuJ1zE4E8Xv2AaapoW7c+cvMC+mWm4f+ybmfzuzO3AvgG2L/Yv+TrylKQOhqckdTA8JamD4SlJHQxPSepgeEpSB8NTkjoYnpLUYd7wTHJNkn1Jdg61nZDkpiQPtufjW3uSfCLJriQ7kpw+zuIlaVIWMvK8FjjngLbLgJuraj1wc5sHOBdY3x5bgKtGU6YkTZd5w7OqvgU8eUDzJuC6Nn0dcP5Q+2dq4NvAK5KsHlWxkjQteu+qtKqq9rbpx4FVbXoN8NjQertb214WYZbrTtXYN3Ozbw7O/hmtJd+SrqrqwBt7LESSLQx27SXpkNN7tv2J/bvj7Xlfa98DrBtab21re4mq2lpVGxd7JxNJmga94bkNuKhNXwTcONT+jnbW/UzgqaHde0laMebdbU/yBeBs4MQku4EPAX8J3JDkYuBR4IK2+teA84BdwE+Bd/UU5X0HXzR8nOrss8+eXCFT6tZbb31h2u/NTDPudTrBOqbRKI7+zhueVXXhHIvePMu6BVyy1KIkadp5hZEkdTA8JamD4SlJHQxPSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqYPhKUkdDE9J6mB4SlIHw1OSOhiektTB8JSkDoanJHUwPCWpg+EpSR0MT0nqYHhKUgfDU5I6GJ6S1MHwlKQOhqckdTA8JamD4SlJHeYNzyTXJNmXZOdQ2xVJ9iS5uz3OG1p2eZJdSR5I8tZxFS5Jk7SQkee1wDmztF9ZVRva42sASU4FNgOvba/5hyRHjKpYSZoW84ZnVX0LeHKB77cJuL6qnqmqh4FdwBlLqE+SptJSjnlemmRH260/vrWtAR4bWmd3a5OkFaU3PK8CXg1sAPYCH1vsGyTZkuTOJHd21iBJE9MVnlX1RFU9V1XPA5/mxV3zPcC6oVXXtrbZ3mNrVW2sqo09NUjSJHWFZ5LVQ7NvA/afid8GbE5yTJKTgfXA7UsrUZKmz5HzrZDkC8DZwIlJdgMfAs5OsgEo4BHg3QBVdW+SG4D7gGeBS6rqufGULkmTM294VtWFszRffZD1PwJ8ZClFSdK08wojSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqYPhKUkdDE9J6mB4SlIHw1OSOhiektTB8JSkDoanJHUwPCWpg+EpSR0MT0nqYHhKUgfDU5I6GJ6S1MHwlKQOhqckdTA8JamD4SlJHQxPSepgeEpSB8NTkjrMG55J1iW5Jcl9Se5N8p7WfkKSm5I82J6Pb+1J8okku5LsSHL6uH8ISVpuCxl5Pgu8r6pOBc4ELklyKnAZcHNVrQdubvMA5wLr22MLcNXIq5akCZs3PKtqb1Xd1aafBu4H1gCbgOvaatcB57fpTcBnauDbwCuSrB555ZI0QUcuZuUkJwGnAbcBq6pqb1v0OLCqTa8BHht62e7WtneojSRbGIxMZ9vOYsqSAL83Wl4LDs8kxwJfAt5bVT8Z/qJWVSWpxWy4qrYCW9t7L+q1h6tbb7110iXoEOV/K6O3oLPtSY5iEJyfq6ovt+Yn9u+Ot+d9rX0PsG7o5WtbmyStGAs52x7gauD+qvr40KJtwEVt+iLgxqH2d7Sz7mcCTw3t3kvSipCqg+8xJzkL+E/gHuD51vx+Bsc9bwB+CXgUuKCqnmxh+3fAOcBPgXdV1Z3zbGNGEfPVdDg58DiefTPTAYePJljJ9Jnx3bFrZnrpcYztVbVxUW8xDV84w3NuhufBGZ5zMzwPYgTh6RVGktTB8JSkDoanJHUwPCWpg+EpSR0MT0nqYHhKUgfDU5I6GJ6S1MHwlKQOhqckdTA8JamD4SlJHQxPSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqYPhKUkdDE9J6mB4SlIHw1OSOhiektTB8JSkDvOGZ5J1SW5Jcl+Se5O8p7VfkWRPkrvb47yh11yeZFeSB5K8dZw/gCRNwpELWOdZ4H1VdVeS44DtSW5qy66sqr8eXjnJqcBm4LXALwLfSPIrVfXcKAuXpEmad+RZVXur6q42/TRwP7DmIC/ZBFxfVc9U1cPALuCMURQrSdNiUcc8k5wEnAbc1pouTbIjyTVJjm9ta4DHhl62m4OHrSQdchYcnkmOBb4EvLeqfgJcBbwa2ADsBT62mA0n2ZLkziR3LuZ1kjQNFhSeSY5iEJyfq6ovA1TVE1X1XFU9D3yaF3fN9wDrhl6+trXNUFVbq2pjVW1cyg8gSZOwkLPtAa4G7q+qjw+1rx5a7W3Azja9Ddic5JgkJwPrgdtHV7IkTd5Czra/AfhD4J4kd7e29wMXJtkAFPAI8G6Aqro3yQ3AfQzO1F/imXZJK02qatI1kGRGEdNQ07QYDPxfZN/MNNw/9s1MM747ds1MeUnL9sUeQvQKI0nqYHhKUgfDU5I6GJ6S1MHwlKQOhqckdTA8JamD4SlJHQxPSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqYPhKUkdDE9J6mB4SlIHw1OSOhiektTB8JSkDoanJHUwPCWpg+EpSR0MT0nqYHhKUgfDU5I6zBueSV6W5PYk301yb5K/aO0nJ7ktya4kX0xydGs/ps3vastPGu+PIEnLbyEjz2eAN1XV64ENwDlJzgQ+ClxZVa8BfgRc3Na/GPhRa7+yrSdJK8q84VkD/9Nmj2qPAt4E/Gtrvw44v01vavO05W9OkpFVLElT4MiFrJTkCGA78Brg74HvAz+uqmfbKruBNW16DfAYQFU9m+Qp4JXADxZalFk7N/tmbvaNltOCwrOqngM2JHkF8BXgV5e64SRbgC1LfR9JC+D/KyO3qLPtVfVj4BbgN4FXJNkfvmuBPW16D7AOoC3/BeCHs7zX1qraWFUbO2uXpIlZyNn2V7URJ0l+HngLcD+DEH17W+0i4MY2va3N05Z/s6pqlEVL0qRlvlxL8joGJ4COYBC2N1TVh5OcAlwPnAB8B/iDqnomycuAzwKnAU8Cm6vqoXm28d/A/7KI46JjdiLTUwtMVz3TVAtYz8FMUy0w3fX8clW9ajEvnjc8l0uSO6dlF36aaoHpqmeaagHrOZhpqgVWXj1eYSRJHQxPSeowTeG5ddIFDJmmWmC66pmmWsB6DmaaaoEVVs/UHPOUpEPJNI08JemQMfHwTHJOkgfaXZgum1ANjyS5J8ndSe5sbSckuSnJg+35+DFu/5ok+5LsHGqbdfsZ+ETrrx1JTl+GWq5Isqf1z91Jzhtadnmr5YEkbx1xLeuS3JLkvnZHr/e09kn1zVz1TKp/puaOZwep5dokDw/1zYbWPtbPaqiuI5J8J8lX2/zo+qaqJvZg8Luj3wdOAY4GvgucOoE6HgFOPKDtr4DL2vRlwEfHuP03AqcDO+fbPnAe8G8MLrg7E7htGWq5AvjTWdY9tX1mxwAnt8/yiBHWsho4vU0fB3yvbXNSfTNXPZPqnwDHtumjgNvaz30Dg9+vBvgk8Edt+o+BT7bpzcAXl6GWa4G3z7L+WD+roe38CfB54KttfmR9M+mR5xnArqp6qKp+xuCX7jdNuKb9hu8ONXzXqJGrqm8xuKBgIdvfBHymBr7N4DLZ1WOuZS6bgOur6pmqehjYxeAzHVUte6vqrjb9NIMr29Ywub6Zq565jLt/qqbkjmcHqWUuY/2sAJKsBX4H+Mc2H0bYN5MOzxfuwNQM351pORXw9STbM7hhCcCqqtrbph8HVi1zTXNtf1J9dmnbvbpm6BDGstXSdqNOYzCimXjfHFAPTKh/2m7p3cA+4CYWccczYP8dz8ZSS1Xt75uPtL65MskxB9YyS52j8jfAnwHPt/lXMsK+mXR4Touzqup04FzgkiRvHF5Yg7H8xH4tYdLbB64CXs3gZth7gY8t58aTHAt8CXhvVf1keNkk+maWeibWP1X1XFVtYHBznjMYwR3PRlVLkl8DLm81/TqDS7n/fDlqSfK7wL6q2j6ubUw6PF+4A1MzfHemZVNVe9rzPga33DsDeGL/bkR73rfMZc21/WXvs6p6ov3DeB74NC/ueo69liRHMQiqz1XVl1vzxPpmtnom2T/71QjveDbCWs5phzqqqp4B/onl65s3AL+X5BEGhwPfBPwtI+ybSYfnHcD6dgbsaAYHarctZwFJXp7kuP3TwG8DO5l5d6jhu0Ytl7m2vw14RztbeSbw1NAu7FgccCzqbQz6Z38tm9uZypOB9cDtI9xugKuB+6vq40OLJtI3c9Uzwf6ZmjuezVHLfw39JxcGxxeH+2Zsn1VVXV5Va6vqJAa58s2q+n1G2TfjOMO1mAeDs27fY3Cs5gMT2P4pDM6Ifhe4d38NDI533Aw8CHwDOGGMNXyBwe7e/zE4DnPxXNtncHZy/9387wE2LkMtn23b2tG+ZKuH1v9Aq+UB4NwR13IWg13yHcDd7XHeBPtmrnom1T+vY3BHsx0MQumDQ9/p2xmcoPoX4JjW/rI2v6stP2UZavlm65udwD/z4hn5sX5WB9R2Ni+ebR9Z33iFkSR1mPRuuyQdkgxPSepgeEpSB8NTkjoYnpLUwfCUpA6GpyR1MDwlqcP/AwsXNF97s37WAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "state, reward, done, info = env.step(gridworld.RIGHT)\n",
    "plt.imshow(env.render(mode='rgb_array'))\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, -0.04)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "state, reward"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# What's the point? Solving MDPs\n",
    "\n",
    "The goal when solving MDPs is to maximize the expected reward over time. In otherwords,\n",
    "\n",
    "$$\\max_{\\pi} \\mathrm{E}\\left[\\sum_{t=0}^{H} \\gamma^{t} R\\left(S_{t}, A_{t}, S_{t+1}\\right) | \\pi\\right]$$\n",
    "\n",
    "Thus, given and MPD $(S, A, P, R, \\gamma, H)$, our goal is to find the optimal policy $\\pi^*$\n",
    "\n",
    "- Exact Methods:\n",
    "    - **Value iteration**\n",
    "    - Policy iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Value function and $V^*$\n",
    "\n",
    "The value function:\n",
    "\n",
    "$$V(s)=\\mathbb{E}\\left[\\sum_{t=0}^{H} \\gamma^{t} R\\left(s_{t}, a_{t}, s_{t+1}\\right), s_{0}=s\\right]$$\n",
    "\n",
    "The optimal value function:\n",
    "\n",
    "$$V^{*}(s)=\\max _{\\pi} \\mathbb{E}\\left[\\sum_{t=0}^{H} \\gamma^{t} R\\left(s_{t}, a_{t}, s_{t+1}\\right) | \\pi, s_{0}=s\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Value function and $V^*$\n",
    "\n",
    "In plain english, the optimal value function is the expected value of accumulated rewards from starting in state $s$ and acting optimally from that point forward (and the optimal value function obey's the Bellman equations) Once we have that value function the optimal policy to follow given the agents current state, $\\pi^*(s)$, is simply that action that yields the maximum value for the next step. This is summarized below:\n",
    "\n",
    "$$V^*(s) = R(s) + \\gamma \\underset{a \\in A}{\\text{ max}} \\sum_{s'}P(s,a,s')V^*(s')$$\n",
    "\n",
    "$$\\pi^*(s) = \\underset{a \\in A}{\\text{argmax}}\\sum_{s'}P(s,a,s')V^*(s')$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Optimal Value Function $V^*$\n",
    "\n",
    "Let's assume that $\\gamma$=0.9 with $H=100$ and fully deterministic actions. Compute $V^*(s)$ for the simple gridworld example for each starting state. Note: each state has a reward of -0.04, the goal state has a reward of +1 and the terminal state has a reward of -1.\n",
    "\n",
    "- $s = (2, 2)$, $V^*(s) =$ ?\n",
    "- $s = (0, 1)$, $V^*(s) =$ ?\n",
    "- $s = (0, 3)$, $V^*(s) =$ ?\n",
    "- $s = (1, 2)$, $V^*(s) =$ ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- $s = (2, 2)$, $V^*(s) =$ ?\n",
    "- $s = (0, 1)$, $V^*(s) =$ ?\n",
    "- $s = (0, 3)$, $V^*(s) =$ ?\n",
    "- $s = (1, 2)$, $V^*(s) =$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAU8AAAD8CAYAAAD35CadAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dfZBV9Z3n8feXptteunkQENOCMcY0rkiMKAoprYQiZNIha5MUVsoUWUSDjbuGirUztYsz1uJOfBhnJrqyqFMaJcBmkmGT8FCpsDMZE3AXFQJG8YGIBOnYICCr3dI0tk3z3T/u6fbevrfvw6/vI3xe1q0+53fP95zv+d3f+XLuPedezd0REZHcDCt1AiIilUjFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCFKx4mlmTmb1hZvvMbFmhtiMiUgpWiPs8zawK2At8GWgDfgd8y91fz/vGRERKoFBnntcC+9x9v7t/BPwUmFegbYmIFN3wAq13IvB23HwbMGOwhc1MX3MSkVI65u7n5RJQqOKZkZm1AC2l2r6ISJzWXAMKVTwPAhfGzU+K2vq5+xPAE6AzTxGpPIX6zPN3QKOZXWxmNcBNwKYCbUtEpOgKcubp7qfM7LvAPwNVwNPu/loO8YVIqyKZWcK8+iZRfP+obxJp7AxuYN8EraMcOnTg2/ZyyKlc6ABIT8VzcBo7g0tRPHe5+/Rc1qFvGImIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJcNYUz66uLi677DJGjBjBeeedx7Zt2woeW11dzY033hiactF0dXWxfPny/v1rbm4ueOyOHTsqom8Ali9f3v/6Nzc35zR2QmJ37NhBdXX1UFIumrP6uHL34AdwAHgFeAnYGbWNBX4NvBn9PTeL9Xj8I9/a29t96tSpvmbNGj948KBv27bNq6qqfPXq1QWL7ezsdMDnz58/pNwL3Tfu7lOnTvX6+vr+/ZsxY0ZWfRMa29nZ6Y2NjUPuG3cveN+0t7d7fX19/+s/Y8YMr6qqKmhsY2NjXvZHx9XgBvZNX/3K5ZGP4jl+QNvfAsui6WXAg1msp6AvclVVldfV1SW0LV26NKtthcRu3LjRR48eXRHFc//+/V5XV+cnT55M2u5tt92W99i+vmlqair74rl//36vqqpK2r+lS5dm1TchsRs3bvSmpqaKKJ5n0nEVUjwL8bZ9HrA6ml4NfL0A28hJb28v06ZNS2ibPXs2AKdPn85r7OHDh1m8eDGPPvroUFIumg0bNjBt2jRqa2uTnlu/fn3eY/v65qKLLgpLuIg2bNhAb29v0v7Nnj2b9evXpx07IbF9Y6cS+gZ0XA21eDrwL2a2y8xaorbz3f2daPowcH6qQDNrMbOdZrZziDlk5brrrkuYnzNnDgAbN27Ma+w111zD3r17WbBgQWiqRbVq1aqk/etz7NixvMauXLmy4vomlTlz5nDs2LG0YyfX2JUrV/aPnUpyNh9XQy2e17v7VcBXgTvM7AvxT8adHidx9yfcfbq7Tx9iDlmpr69Pmh82bBhHjx7NW+yePXtYvXo1Y8aMGXrCRXLkyJGk/QMYNizz0Mglds+ePSxbtqzi+iaVvn1ON3ZyjV22bFnFjR04u4+r4UMJdveD0d+jZrYeuBY4YmYN7v6OmTUAmXuxCGpqalK2nThxIi+xPT09LFiwgBdffHFoiRZZV1fXoPv34Ycf5i12wYIF3H777UNLtsi6urrSPp9u7OQS29PTw+23397/trWSnM3HVXDxNLM6YJi7H4+m/wz4a2ATcDPwN9HfzOfvRdDd3Z2ybeTIkXmJHTNmDNu3bx9akiVQV1c36P7lK3br1q2sWbOGqVOnhidaAnV1dXR2dg76fLqxk23s1q1bmTt3blbFphydzcfVUM48zwfWm1nfev7R3f+3mf0OWGdm3wFagW8OPc3MojwS9PT0MHx4bBePHz+e8Fx7ezvuzoQJEzKuO1NsR0cH9957b9kWh3R909DQkLR/QN9dEGllE9vR0cHChQtpbW3NMeviGax/GhoaUr79bm9vB0g7drKNXbhwIffee29Q3sWg4yqNXC/PF+JBHm6p6OnpSXrE35Ywc+bMhOXXrVvngPf29qZdbzaxDzzwQKpbHxIe7777btB+FbpvVqxYkbR/fdsdP3582vVmE1vIvunb1lD6xn3w/lmxYkXK9a5bt87Hjx+fduxkG5upb8p57JxJxxXFvs8zX498vMjpVFVVeW1tbUJbS0tL1vejhcZSAfd5tra2em1trXd2diZtd/HixQWLXbJkSdnf59na2upVVVVJ+9fS0pJV34TGLlmypGLu8zxTjisVz0EsWrQoab2jRo3ympqahLbm5mavr68Pik2lEopn3zYee+yx/vkjR454TU2N7927t7+tp6fH6+vr/f777885NpVKKJ7usdd/4P6NGjUqqW+am5uT+iab2FQqpXieScdVSPE8K77bvmrVKjo7O5k8eTK1tbVMmDCBzZs3J31g7R8X85xjK1lnZydtbW39+9fS0kJ3dzeNjY0Jy7l70g3M2cZWqlWrVtHW1tb/+re0tLB58+as+ibb2Ep1th9XNnCnSpKEWUIS5ZBTuRj4gb36JlF8/6hvEmnsDC7FhbBdnuM952fFmaeISL6peIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISICMxdPMnjazo2b2alzbWDP7tZm9Gf09N2o3M1thZvvMbLeZXVXI5EVESiWbM88fAU0D2pYBz7h7I/BMNA/wVaAxerQAj+cnTRGR8pKxeLr7s8B7A5rnAauj6dXA1+Pa13jMC8AYM2vIV7IiIuVieGDc+e7+TjR9GDg/mp4IvB23XFvU9g45MLPAtM586pvBqW/SU//kV2jx7Ofubmaea5yZtRB7ay8iUnFCr7Yf6Xs7Hv09GrUfBC6MW25S1JbE3Z9w9+nuPj0wBxGRkgktnpuAm6Ppm4GNce0Lo6vuM4GOuLf3IiJnjIxv283sJ8AsYLyZtQHLgb8B1pnZd4BW4JvR4r8C5gL7gC7glpCk3HP+FOCMFf851axZs0qXSJnasmVL/7TGTaL4saOeSZSPT38zFk93/9YgT30pxbIO3DHUpEREyp2+YSQiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEiAjMXTzJ42s6Nm9mpc2z1mdtDMXooec+Oeu8vM9pnZG2b2lUIlnouOjg4++9nPsnbtWg4dOsRzzz3H8OHDWbNmTcFiT5w4gZlx44035ms3pAQ6OjoYOXJk/+s/c+ZMhg8fXtDYyZMnY2ZDTb2kmgGLHtnqAD4LrAUOAc8Bw4HMR2lpmLunX8DsC0AnsMbdp0Zt9wCd7v73A5adAvwEuBa4APhXYLK792bYRkISmXLK1cKFC1m7dm3CeseNG8eJEyf48MMPCxJ722238cMf/pD58+fzs5/9LDj3+INo1qxZwes5U23ZsqV/Ot/jBmKv/6xZs7j11lsBeO+992hsbGTHjh1ccsklBYnte82Huj/xYyf/PZNaL/A/gB8AbTlueyGxwhm//DjgBJD+KM1diqK+y92n57KOjGee7v4s8F6W65sH/NTdu939LWAfsUJaUmvXruX6669PaHvqqafo7u7m9OnTeY09fPgwEyZMUKE7Azz88MOsXbu2v/gBjB07lqeeeoqZM2emHTshsX1jZ8mSJfndkSKqAu4E3g6IXQtcP6DtKaAbSH+UlkZ27z9S+66ZLQR2An/u7u8DE4EX4pZpi9pKrrGxMWH+8ssvB+APf/gDU6ZMyVvsrbfeype+9CUWLFjAt7/97aGmXVAdHR3s27eP48ePM336dNra2nj//fc5deoUV1xxBaNHj05Y/qWXXuLkyZN89NFH1NbWMmHCBC6++GIAdu3aRWdnJ+7OVVddxaFDh3j33Xepq6vjkksuSVpXJdi2bVvK9ssvv5xjx46lHTshsX1j52zWOGD+8ujvH4D0R2nxhV4wehy4BLgSeIfYWXpOzKzFzHaa2c7AHHIyYcKEhPmGhgYA3njjjbzGvvLKKzz++OOhaRbV6NGjufrqqwHYu3cvw4YNY9y4cVRXV7N7924++uijhOXNjClTpvD5z3+eESNG0Nra2v/c1VdfTU1NDQAHDhxg2LBhVFdX88EHH7B79+7i7VQe7d27N2V7NmMn19iVK1dW1NgplAkD5huiv5mP0uILOvN09yN902b2JPDLaPYgcGHcopOitlTreAJ4IlpHwT+SGTt2bMJ8fX09tbW1vPXWW3mJ7enpYcaMGbz9dsgbltK76KKLGDduXP/8li1b+NOf/sRnPvOZ/rbPfe5z/dOTJ0/m+eef59SpU0kXQa644or+6ddff52jR48WMPPCGWxs1NfXp30+19ienh4OHDhQsWMnn8YOmK8HaoHMR2nxBZ15mllD3Ow3gL4r8ZuAm8zsHDO7mNhZ+I6hpZgfqT58d/esrmpmE3v33XfT25v2uljFyfR5MGS+qJHtlelylGlspHs+l9i7776b++67L7fkzlCpRpOT21X7Ysk4ss3sJ8AsYLyZtQHLgVlmdiWx/ToALAFw99fMbB3wOnAKuCPTlfZiGfgWtK+t70xgqLErV65k+/btQ0uyzL355pt0dHTQ3d1dkCvb5WbEiBEcP3580OfTjZ1sY7du3crKlSt58MEHwxM9gyQfabG2zEdp8WUsnu7+rRTNT6VZ/j6g6P+MpvqXvqenp//MZ9++fQnP7dmzB3dPupKeSqbYhx56iDFjxtDU1JQU+6tf/YpJkybxyiuvcO6552a9P+Vm165dXHDBBf0Xz7q7u3n++edLnFV+DDZ2vvjFL7Ju3bqk5/bs2QOQduxkGztr1iwuuOACJk2a1L9Me3s7QH9buY2dVGeBPQzt6nOffQPm9xA7Q8t8lBZf5b6nGqCnpyepLf4t48AP8F99NfZJw6WXXppx3ZliP/roIw4dOpQy9uTJkxw8eLCi39K7O52dnVmdpVeiwcbO9ddfn7IAvvrqq4wfPz7t2MkldrCxc/Bg7HJBuY2d5N7KXyEZeJmt7/PAzEdp8Z0xX88cPnx40qPPokWLeOGFFxKWX7x4MTU1NQwb9nEXzJs3j5EjRyYsl03ssmXLcPekB8D8+fNxd8aPH5/X/S0mM+Occ86ho6Ojvy2bz0MrxWBjZ+nSpSxatCjhCvjRo0dZvHgxzz33XP/rf+rUKebNm8cDDzzQv1y2sanGTd99nn3z5TZ2hqd45GoeMHJA2yIS73MEWAzUUJ6F6ow580znkUceYefOnaxdu5ampib279/PiRMnePLJJxOW27RpU3Dsme4Tn/gE+/fv58MPP6S7u5sPP/yw4r9CmI1HHnmEhoYG6uvraWpq4mtf+xonTpxIuPf3jTfeYNOmTTz33HPcddddOcWeqU5leD75SINHiN00vhZoAvYT+3ZRuR5p5VjQ827UqFG88MILfP/73+fCCy/khhtu4Nlnn+WWW25JWO6GG26grq4uKLYSdXR08OKLLwIffzTR1dXFyy+/DMCRI0c4dSp2GHzyk5+kurqaQ4cOUVdXx5VXXkltbS2///3vOXToEC+++GL/hbXXXnsNgJdffpkjR2J3te3evbt/XZVk1KhR3Hnnnf2v/8SJE3n22WcTlrn00ku54YYbuPPOO3OOPdP8HbGbv2vi2saQfIP7DUDdgLZRxM48v0/sfscbgGeBcj3SMn63vShJFPi77ZVM321Pr9Dfba9kpfhue6UoynfbRUQkmYqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEyFg8zexCM/utmb1uZq+Z2fei9rFm9mszezP6e27Ubma2wsz2mdluM7uq0DshIlJs2Zx5ngL+3N2nADOBO8xsCrAMeMbdG4FnonmArwKN0aMFeDzvWYuIlFjG4unu77j7i9H0cWAPMBGYB6yOFlsNfD2anges8ZgXgDFm1pD3zEVESmh4Lgub2aeAacB24Hx3fyd66jBwfjQ9EXg7Lqwtansnrg0zayF2ZppqO7mkJQJo3EhxZV08zawe+Dlwp7t/ED9Q3d3NzHPZsLs/ATwRrTun2LPVli1bSp2CVCj9s5J/WV1tN7NqYoXzx+7+i6j5SN/b8ejv0aj9IHBhXPikqE1E5IyRzdV2A54C9rj7Q3FPbQJujqZvBjbGtS+MrrrPBDri3t6LiJwRzD39O2Yzux74P8ArwOmo+S+Jfe65Dvgk0Ap8093fi4rtSqAJ6AJucfedGbaRkESmnM4mAz/HU98kGvDxUQkzKT8JY0ddkyj5c4xd7j49p1WUw4BT8Rycimd6Kp6DU/FMIw/FU98wEhEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhIgY/E0swvN7Ldm9rqZvWZm34va7zGzg2b2UvSYGxdzl5ntM7M3zOwrhdyBbHV1dXHZZZcxYsQIzjvvPLZt21bw2Orqam688cbQlIumq6uL5cuX9+9fc3NzwWN37NhREX0DsHz58v7Xv7m5OaexExK7Y8cOqqurh5Jy6fwCmJhjTBewHBgBnAdk372l5e5pH0ADcFU0PRLYC0wB7gH+IsXyU4CXgXOAi4E/AlUZtuHxj3xrb2/3qVOn+po1a/zgwYO+bds2r6qq8tWrVxcstrOz0wGfP3/+kHIvdN+4u0+dOtXr6+v792/GjBlZ9U1obGdnpzc2Ng65b9y94H3T3t7u9fX1/a//jBkzvKqqqqCxjY2NedmfhLFTjP/+FLC9dpypOPU4B3G24VThrC5wriQ9dnqGWjjwkdPCsdeDjcCX0xTPu4C74ub/Gfh8hnUW9CCoqqryurq6hLalS5dmta2Q2I0bN/ro0aMronju37/f6+rq/OTJk0nbve222/Ie29c3TU1NZV889+/f71VVVUn7t3Tp0qz6JiR248aN3tTUVFnF836cW3CeCdheFU4dzsm4tqXROm4rYM55KJ45feZpZp8CpgHbo6bvmtluM3vazM6N2iYCb8eFtZH7iXxe9fb2Mm3atIS22bNnA3D69Om8xh4+fJjFixfz6KOPDiXlotmwYQPTpk2jtrY26bn169fnPbavby666KKwhItow4YN9Pb2Ju3f7NmzWb9+fdqxExLbN3YqoW8S3AU8DcwOiO0lVlHiu6lvPemHX8llXTzNrB74OXCnu38APA5cAlwJvAP8IJcNm1mLme00s525xIW67rrrEubnzJkDwMaNG/Mae80117B3714WLFgQmmpRrVq1Kmn/+hw7diyvsStXrqy4vkllzpw5HDt2LO3YyTV25cqV/WPnrDNwCM2J/qYffiWXVfE0s2pihfPH7v4LAHc/4u697n4aeBK4Nlr8IHBhXPikqC2Buz/h7tPdffpQdiBb9fX1SfPDhg3j6NGjeYvds2cPq1evZsyYMUNPuEiOHDmStH8Aw4ZlHhq5xO7Zs4dly5ZVXN+k0rfP6cZOrrHLli2ruLGTNwOHUD0VcR9QNlfbDXgK2OPuD8W1N8Qt9g3g1Wh6E3CTmZ1jZhcDjcCO/KUcpqamJmXbiRMn8hLb09PDggUL+t/SV4qurq5B9y+fsQsWLOD2228PS7JEurq60j6fbuzkEtvT08Ptt99ecWMnb1INtczDr+SGZ7HMdcC/B14xs5eitr8EvmVmVxL7sPUAsATA3V8zs3XA68Ap4A5378134rnq7u5O2TZy5Mi8xI4ZM4bt27cnLVfu6urqBt2/fMVu3bqVNWvWMHXq1PBES6Curo7Ozs5Bn083drKN3bp1K3Pnzs3qH/EzVqqhlnn4lVzG4unu/xewFE/9Kk3MfcB9Q8grZ7ET5EQ9PT0MHx7bxePHjyc8197ejrszYcKEjOvOFNvR0cG9995btsUhXd80NDQk7R/QdxdEWtnEdnR0sHDhQlpbW3PMungG65+GhoaUb7/b29sB0o6dbGMXLlzIvffeG5T3GWPgEGondkpW7nK9PF+IB3m4HaenpyfpEX/LxsyZMxOWX7dunQPe29ubdr3ZxD7wwAOpbn1IeLz77rtB+1XovlmxYkXS/vVtd/z48WnXm01sIfumb1tD6Rv3wftnxYoVKde7bt06Hz9+fNqxk21spr7J29gp1n+5bg+cmQPa1kXt44uQZzHv8yzEIx8FIp2qqiqvra1NaGtpacn6Ps/QWCrgPs/W1lavra31zs7OpO0uXry4YLFLliwp+/s8W1tbvaqqKmn/Wlpasuqb0NglS5ZU1n2eqYpStv9V4dTidMa1tUTrWFyEPFU801u0aFHSekeNGuU1NTUJbc3NzV5fXx8Um0olFM++bTz22GP980eOHPGamhrfu3dvf1tPT4/X19f7/fffn3NsKpVQPN1jr//A/Rs1alRS3zQ3Nyf1TTaxqZyxxbOZ2DeJ7o9rWxQt/1hc2yicGpy9RcizWDfJV6pVq1bR2dnJ5MmTqa2tZcKECWzevDnpwoZ/XMxzjq1knZ2dtLW19e9fS0sL3d3dNDY2Jizn7kk3d2cbW6lWrVpFW1tb/+vf0tLC5s2bs+qbbGMr3t8Ru9v7/Li2McS+qP2tuLa+MhXfTauATmJfpakFJgCbiV0wKvNusoHFoiRJmCUkUQ45lYuBFzPUN4ni+0d9kyhh7KhrEiVfI9zlOd5zflaceYqI5JuKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBMhYPM2s1sx2mNnLZvaamf23qP1iM9tuZvvM7J/MrCZqPyea3xc9/6nC7oKISPFlc+bZDcx2988R+1/bN5nZTOBB4GF3/wzwPvCdaPnvAO9H7Q9Hy4mInFEyFk+P6Yxmq6OHA7OBn0Xtq4GvR9Pzonmi579kZsn/i3kRkQo2PJuFzKwK2AV8BngU+CPQ7u6nokXagInR9ETgbQB3P2VmHcA44Fi2SanWDk59Mzj1jRRTVsXT3XuBK81sDLAe+LdD3bCZtQAtQ12PiGRB/67kXU5X2929Hfgt8HlgjJn1Fd9JwMFo+iBwIUD0/Gjg/6VY1xPuPt3dpwfmLiJSMtlcbT8vOuPEzP4N8GVgD7EiemO02M3Axmh6UzRP9Pxv3N3zmbSISKlZprpmZlcQuwBURazYrnP3vzazTwM/BcYCvwe+7e7dZlYLrAWmAe8BN7n7/gzbeBc4QQ6fixbYeMonFyivfMopF1A+6ZRTLlDe+Vzk7uflEpyxeBaLme0sl7fw5ZQLlFc+5ZQLKJ90yikXOPPy0TeMREQCqHiKiAQop+L5RKkTiFNOuUB55VNOuYDySaeccoEzLJ+y+cxTRKSSlNOZp4hIxSh58TSzJjN7I/oVpmUlyuGAmb1iZi+Z2c6obayZ/drM3oz+nlvA7T9tZkfN7NW4tpTbt5gVUX/tNrOripDLPWZ2MOqfl8xsbtxzd0W5vGFmX8lzLhea2W/N7PXoF72+F7WXqm8Gy6dU/VM2v3iWJpcfmdlbcX1zZdRe0NcqLq8qM/u9mf0yms9f37h7yR7E7h39I/BpoAZ4GZhSgjwOAOMHtP0tsCyaXgY8WMDtfwG4Cng10/aBucBmYl+4mwlsL0Iu9wB/kWLZKdFrdg5wcfRaVuUxlwbgqmh6JLA32map+mawfErVPwbUR9PVwPZov9cRu78a4B+A/xBN/0fgH6Lpm4B/KkIuPwJuTLF8QV+ruO38J+AfgV9G83nrm1KfeV4L7HP3/e7+EbGb7ueVOKc+8b8OFf+rUXnn7s8S+0JBNtufB6zxmBeIfU22ocC5DGYe8FN373b3t4B9xF7TfOXyjru/GE0fJ/bNtomUrm8Gy2cwhe4f9zL5xbM0uQymoK8VgJlNAr4G/DCaN/LYN6Uunv2/wBSJ/3WmYnLgX8xsl8V+sATgfHd/J5o+DJxf5JwG236p+uy70durp+M+wihaLtHbqGnEzmhK3jcD8oES9U/0tvQl4Cjwa3L4xTOg7xfPCpKLu/f1zX1R3zxsZucMzCVFnvny34H/DJyO5seRx74pdfEsF9e7+1XAV4E7zOwL8U967Fy+ZLcllHr7wOPAJcR+DPsd4AfF3LiZ1QM/B+509w/inytF36TIp2T94+697n4lsR/nuZY8/OJZvnIxs6nAXVFO1xD7Kvd/KUYuZvbvgKPuvqtQ2yh18ez/BaZI/K8zFY27H4z+HiX2k3vXAkf63kZEf48WOa3Btl/0PnP3I9GBcRp4ko/fehY8FzOrJlaofuzuv4iaS9Y3qfIpZf/08Tz+4lkec2mKPupwd+8GVlG8vrkOaDazA8Q+DpwNPEIe+6bUxfN3QGN0BayG2Ae1m4qZgJnVmdnIvmngz4BXSfx1qPhfjSqWwba/CVgYXa2cCXTEvYUtiAGfRX2DWP/05XJTdKXyYqAR2JHH7RrwFLDH3R+Ke6okfTNYPiXsn7L5xbNBcvWFnv4AAAD5SURBVPlD3D9yRuzzxfi+Kdhr5e53ufskd/8UsbryG3dfQD77phBXuHJ5ELvqtpfYZzV/VYLtf5rYFdGXgdf6ciD2ecczwJvAvwJjC5jDT4i93esh9jnMdwbbPrGrk32/5v8KML0IuayNtrU7GmQNccv/VZTLG8BX85zL9cTeku8GXooec0vYN4PlU6r+uYLYL5rtJlaU/mvcmN5B7ALV/wLOidpro/l90fOfLkIuv4n65lXgf/LxFfmCvlYDcpvFx1fb89Y3+oaRiEiAUr9tFxGpSCqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIgP8PrVO7h7deEkUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "state = env.reset()\n",
    "plt.imshow(env.render(mode='rgb_array', show_rewards=True))\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Optimal Value Function $V^*$\n",
    "\n",
    "Let's assume that $\\gamma$=0.9 with $H=100$ and slipper actions (there's an 80% chance that the desired action will result the desired move, and a 10% it will result in a slip to the left or to the right of the desired direction). Compute $V^*(s)$ for the simple gridworld example for each starting state. Note: each state has a reward of -0.04, the goal state has a reward of +1 and the terminal state has a reward of -1.\n",
    "\n",
    "- $s = (2, 2)$, $V^*(s) =$ ?\n",
    "- $s = (0, 1)$, $V^*(s) =$ ?\n",
    "- $s = (0, 3)$, $V^*(s) =$ ?\n",
    "- $s = (1, 2)$, $V^*(s) =$ ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- $s = (2, 2)$, $V^*(s) =$ ?\n",
    "- $s = (0, 1)$, $V^*(s) =$ ?\n",
    "- $s = (0, 3)$, $V^*(s) =$ ?\n",
    "- $s = (1, 2)$, $V^*(s) =$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAU8AAAD8CAYAAAD35CadAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dfZBV9Z3n8feXptteunkQENOCMcY0rkiMKAoprYQiZNIha5MUVsoUWUSDjbuGirUztYsz1uJOfBhnJrqyqFMaJcBmkmGT8FCpsDMZE3AXFQJG8YGIBOnYICCr3dI0tk3z3T/u6fbevrfvw6/vI3xe1q0+53fP95zv+d3f+XLuPedezd0REZHcDCt1AiIilUjFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCFKx4mlmTmb1hZvvMbFmhtiMiUgpWiPs8zawK2At8GWgDfgd8y91fz/vGRERKoFBnntcC+9x9v7t/BPwUmFegbYmIFN3wAq13IvB23HwbMGOwhc1MX3MSkVI65u7n5RJQqOKZkZm1AC2l2r6ISJzWXAMKVTwPAhfGzU+K2vq5+xPAE6AzTxGpPIX6zPN3QKOZXWxmNcBNwKYCbUtEpOgKcubp7qfM7LvAPwNVwNPu/loO8YVIqyKZWcK8+iZRfP+obxJp7AxuYN8EraMcOnTg2/ZyyKlc6ABIT8VzcBo7g0tRPHe5+/Rc1qFvGImIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJcNYUz66uLi677DJGjBjBeeedx7Zt2woeW11dzY033hiactF0dXWxfPny/v1rbm4ueOyOHTsqom8Ali9f3v/6Nzc35zR2QmJ37NhBdXX1UFIumrP6uHL34AdwAHgFeAnYGbWNBX4NvBn9PTeL9Xj8I9/a29t96tSpvmbNGj948KBv27bNq6qqfPXq1QWL7ezsdMDnz58/pNwL3Tfu7lOnTvX6+vr+/ZsxY0ZWfRMa29nZ6Y2NjUPuG3cveN+0t7d7fX19/+s/Y8YMr6qqKmhsY2NjXvZHx9XgBvZNX/3K5ZGP4jl+QNvfAsui6WXAg1msp6AvclVVldfV1SW0LV26NKtthcRu3LjRR48eXRHFc//+/V5XV+cnT55M2u5tt92W99i+vmlqair74rl//36vqqpK2r+lS5dm1TchsRs3bvSmpqaKKJ5n0nEVUjwL8bZ9HrA6ml4NfL0A28hJb28v06ZNS2ibPXs2AKdPn85r7OHDh1m8eDGPPvroUFIumg0bNjBt2jRqa2uTnlu/fn3eY/v65qKLLgpLuIg2bNhAb29v0v7Nnj2b9evXpx07IbF9Y6cS+gZ0XA21eDrwL2a2y8xaorbz3f2daPowcH6qQDNrMbOdZrZziDlk5brrrkuYnzNnDgAbN27Ma+w111zD3r17WbBgQWiqRbVq1aqk/etz7NixvMauXLmy4vomlTlz5nDs2LG0YyfX2JUrV/aPnUpyNh9XQy2e17v7VcBXgTvM7AvxT8adHidx9yfcfbq7Tx9iDlmpr69Pmh82bBhHjx7NW+yePXtYvXo1Y8aMGXrCRXLkyJGk/QMYNizz0Mglds+ePSxbtqzi+iaVvn1ON3ZyjV22bFnFjR04u4+r4UMJdveD0d+jZrYeuBY4YmYN7v6OmTUAmXuxCGpqalK2nThxIi+xPT09LFiwgBdffHFoiRZZV1fXoPv34Ycf5i12wYIF3H777UNLtsi6urrSPp9u7OQS29PTw+23397/trWSnM3HVXDxNLM6YJi7H4+m/wz4a2ATcDPwN9HfzOfvRdDd3Z2ybeTIkXmJHTNmDNu3bx9akiVQV1c36P7lK3br1q2sWbOGqVOnhidaAnV1dXR2dg76fLqxk23s1q1bmTt3blbFphydzcfVUM48zwfWm1nfev7R3f+3mf0OWGdm3wFagW8OPc3MojwS9PT0MHx4bBePHz+e8Fx7ezvuzoQJEzKuO1NsR0cH9957b9kWh3R909DQkLR/QN9dEGllE9vR0cHChQtpbW3NMeviGax/GhoaUr79bm9vB0g7drKNXbhwIffee29Q3sWg4yqNXC/PF+JBHm6p6OnpSXrE35Ywc+bMhOXXrVvngPf29qZdbzaxDzzwQKpbHxIe7777btB+FbpvVqxYkbR/fdsdP3582vVmE1vIvunb1lD6xn3w/lmxYkXK9a5bt87Hjx+fduxkG5upb8p57JxJxxXFvs8zX498vMjpVFVVeW1tbUJbS0tL1vejhcZSAfd5tra2em1trXd2diZtd/HixQWLXbJkSdnf59na2upVVVVJ+9fS0pJV34TGLlmypGLu8zxTjisVz0EsWrQoab2jRo3ympqahLbm5mavr68Pik2lEopn3zYee+yx/vkjR454TU2N7927t7+tp6fH6+vr/f777885NpVKKJ7usdd/4P6NGjUqqW+am5uT+iab2FQqpXieScdVSPE8K77bvmrVKjo7O5k8eTK1tbVMmDCBzZs3J31g7R8X85xjK1lnZydtbW39+9fS0kJ3dzeNjY0Jy7l70g3M2cZWqlWrVtHW1tb/+re0tLB58+as+ibb2Ep1th9XNnCnSpKEWUIS5ZBTuRj4gb36JlF8/6hvEmnsDC7FhbBdnuM952fFmaeISL6peIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISICMxdPMnjazo2b2alzbWDP7tZm9Gf09N2o3M1thZvvMbLeZXVXI5EVESiWbM88fAU0D2pYBz7h7I/BMNA/wVaAxerQAj+cnTRGR8pKxeLr7s8B7A5rnAauj6dXA1+Pa13jMC8AYM2vIV7IiIuVieGDc+e7+TjR9GDg/mp4IvB23XFvU9g45MLPAtM586pvBqW/SU//kV2jx7Ofubmaea5yZtRB7ay8iUnFCr7Yf6Xs7Hv09GrUfBC6MW25S1JbE3Z9w9+nuPj0wBxGRkgktnpuAm6Ppm4GNce0Lo6vuM4GOuLf3IiJnjIxv283sJ8AsYLyZtQHLgb8B1pnZd4BW4JvR4r8C5gL7gC7glpCk3HP+FOCMFf851axZs0qXSJnasmVL/7TGTaL4saOeSZSPT38zFk93/9YgT30pxbIO3DHUpEREyp2+YSQiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEiAjMXTzJ42s6Nm9mpc2z1mdtDMXooec+Oeu8vM9pnZG2b2lUIlnouOjg4++9nPsnbtWg4dOsRzzz3H8OHDWbNmTcFiT5w4gZlx44035ms3pAQ6OjoYOXJk/+s/c+ZMhg8fXtDYyZMnY2ZDTb2kmgGLHtnqAD4LrAUOAc8Bw4HMR2lpmLunX8DsC0AnsMbdp0Zt9wCd7v73A5adAvwEuBa4APhXYLK792bYRkISmXLK1cKFC1m7dm3CeseNG8eJEyf48MMPCxJ722238cMf/pD58+fzs5/9LDj3+INo1qxZwes5U23ZsqV/Ot/jBmKv/6xZs7j11lsBeO+992hsbGTHjh1ccsklBYnte82Huj/xYyf/PZNaL/A/gB8AbTlueyGxwhm//DjgBJD+KM1diqK+y92n57KOjGee7v4s8F6W65sH/NTdu939LWAfsUJaUmvXruX6669PaHvqqafo7u7m9OnTeY09fPgwEyZMUKE7Azz88MOsXbu2v/gBjB07lqeeeoqZM2emHTshsX1jZ8mSJfndkSKqAu4E3g6IXQtcP6DtKaAbSH+UlkZ27z9S+66ZLQR2An/u7u8DE4EX4pZpi9pKrrGxMWH+8ssvB+APf/gDU6ZMyVvsrbfeype+9CUWLFjAt7/97aGmXVAdHR3s27eP48ePM336dNra2nj//fc5deoUV1xxBaNHj05Y/qWXXuLkyZN89NFH1NbWMmHCBC6++GIAdu3aRWdnJ+7OVVddxaFDh3j33Xepq6vjkksuSVpXJdi2bVvK9ssvv5xjx46lHTshsX1j52zWOGD+8ujvH4D0R2nxhV4wehy4BLgSeIfYWXpOzKzFzHaa2c7AHHIyYcKEhPmGhgYA3njjjbzGvvLKKzz++OOhaRbV6NGjufrqqwHYu3cvw4YNY9y4cVRXV7N7924++uijhOXNjClTpvD5z3+eESNG0Nra2v/c1VdfTU1NDQAHDhxg2LBhVFdX88EHH7B79+7i7VQe7d27N2V7NmMn19iVK1dW1NgplAkD5huiv5mP0uILOvN09yN902b2JPDLaPYgcGHcopOitlTreAJ4IlpHwT+SGTt2bMJ8fX09tbW1vPXWW3mJ7enpYcaMGbz9dsgbltK76KKLGDduXP/8li1b+NOf/sRnPvOZ/rbPfe5z/dOTJ0/m+eef59SpU0kXQa644or+6ddff52jR48WMPPCGWxs1NfXp30+19ienh4OHDhQsWMnn8YOmK8HaoHMR2nxBZ15mllD3Ow3gL4r8ZuAm8zsHDO7mNhZ+I6hpZgfqT58d/esrmpmE3v33XfT25v2uljFyfR5MGS+qJHtlelylGlspHs+l9i7776b++67L7fkzlCpRpOT21X7Ysk4ss3sJ8AsYLyZtQHLgVlmdiWx/ToALAFw99fMbB3wOnAKuCPTlfZiGfgWtK+t70xgqLErV65k+/btQ0uyzL355pt0dHTQ3d1dkCvb5WbEiBEcP3580OfTjZ1sY7du3crKlSt58MEHwxM9gyQfabG2zEdp8WUsnu7+rRTNT6VZ/j6g6P+MpvqXvqenp//MZ9++fQnP7dmzB3dPupKeSqbYhx56iDFjxtDU1JQU+6tf/YpJkybxyiuvcO6552a9P+Vm165dXHDBBf0Xz7q7u3n++edLnFV+DDZ2vvjFL7Ju3bqk5/bs2QOQduxkGztr1iwuuOACJk2a1L9Me3s7QH9buY2dVGeBPQzt6nOffQPm9xA7Q8t8lBZf5b6nGqCnpyepLf4t48AP8F99NfZJw6WXXppx3ZliP/roIw4dOpQy9uTJkxw8eLCi39K7O52dnVmdpVeiwcbO9ddfn7IAvvrqq4wfPz7t2MkldrCxc/Bg7HJBuY2d5N7KXyEZeJmt7/PAzEdp8Z0xX88cPnx40qPPokWLeOGFFxKWX7x4MTU1NQwb9nEXzJs3j5EjRyYsl03ssmXLcPekB8D8+fNxd8aPH5/X/S0mM+Occ86ho6Ojvy2bz0MrxWBjZ+nSpSxatCjhCvjRo0dZvHgxzz33XP/rf+rUKebNm8cDDzzQv1y2sanGTd99nn3z5TZ2hqd45GoeMHJA2yIS73MEWAzUUJ6F6ow580znkUceYefOnaxdu5ampib279/PiRMnePLJJxOW27RpU3Dsme4Tn/gE+/fv58MPP6S7u5sPP/yw4r9CmI1HHnmEhoYG6uvraWpq4mtf+xonTpxIuPf3jTfeYNOmTTz33HPcddddOcWeqU5leD75SINHiN00vhZoAvYT+3ZRuR5p5VjQ827UqFG88MILfP/73+fCCy/khhtu4Nlnn+WWW25JWO6GG26grq4uKLYSdXR08OKLLwIffzTR1dXFyy+/DMCRI0c4dSp2GHzyk5+kurqaQ4cOUVdXx5VXXkltbS2///3vOXToEC+++GL/hbXXXnsNgJdffpkjR2J3te3evbt/XZVk1KhR3Hnnnf2v/8SJE3n22WcTlrn00ku54YYbuPPOO3OOPdP8HbGbv2vi2saQfIP7DUDdgLZRxM48v0/sfscbgGeBcj3SMn63vShJFPi77ZVM321Pr9Dfba9kpfhue6UoynfbRUQkmYqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEyFg8zexCM/utmb1uZq+Z2fei9rFm9mszezP6e27Ubma2wsz2mdluM7uq0DshIlJs2Zx5ngL+3N2nADOBO8xsCrAMeMbdG4FnonmArwKN0aMFeDzvWYuIlFjG4unu77j7i9H0cWAPMBGYB6yOFlsNfD2anges8ZgXgDFm1pD3zEVESmh4Lgub2aeAacB24Hx3fyd66jBwfjQ9EXg7Lqwtansnrg0zayF2ZppqO7mkJQJo3EhxZV08zawe+Dlwp7t/ED9Q3d3NzHPZsLs/ATwRrTun2LPVli1bSp2CVCj9s5J/WV1tN7NqYoXzx+7+i6j5SN/b8ejv0aj9IHBhXPikqE1E5IyRzdV2A54C9rj7Q3FPbQJujqZvBjbGtS+MrrrPBDri3t6LiJwRzD39O2Yzux74P8ArwOmo+S+Jfe65Dvgk0Ap8093fi4rtSqAJ6AJucfedGbaRkESmnM4mAz/HU98kGvDxUQkzKT8JY0ddkyj5c4xd7j49p1WUw4BT8Rycimd6Kp6DU/FMIw/FU98wEhEJoOIpIhJAxVNEJICKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhIgY/E0swvN7Ldm9rqZvWZm34va7zGzg2b2UvSYGxdzl5ntM7M3zOwrhdyBbHV1dXHZZZcxYsQIzjvvPLZt21bw2Orqam688cbQlIumq6uL5cuX9+9fc3NzwWN37NhREX0DsHz58v7Xv7m5OaexExK7Y8cOqqurh5Jy6fwCmJhjTBewHBgBnAdk372l5e5pH0ADcFU0PRLYC0wB7gH+IsXyU4CXgXOAi4E/AlUZtuHxj3xrb2/3qVOn+po1a/zgwYO+bds2r6qq8tWrVxcstrOz0wGfP3/+kHIvdN+4u0+dOtXr6+v792/GjBlZ9U1obGdnpzc2Ng65b9y94H3T3t7u9fX1/a//jBkzvKqqqqCxjY2NedmfhLFTjP/+FLC9dpypOPU4B3G24VThrC5wriQ9dnqGWjjwkdPCsdeDjcCX0xTPu4C74ub/Gfh8hnUW9CCoqqryurq6hLalS5dmta2Q2I0bN/ro0aMronju37/f6+rq/OTJk0nbve222/Ie29c3TU1NZV889+/f71VVVUn7t3Tp0qz6JiR248aN3tTUVFnF836cW3CeCdheFU4dzsm4tqXROm4rYM55KJ45feZpZp8CpgHbo6bvmtluM3vazM6N2iYCb8eFtZH7iXxe9fb2Mm3atIS22bNnA3D69Om8xh4+fJjFixfz6KOPDiXlotmwYQPTpk2jtrY26bn169fnPbavby666KKwhItow4YN9Pb2Ju3f7NmzWb9+fdqxExLbN3YqoW8S3AU8DcwOiO0lVlHiu6lvPemHX8llXTzNrB74OXCnu38APA5cAlwJvAP8IJcNm1mLme00s525xIW67rrrEubnzJkDwMaNG/Mae80117B3714WLFgQmmpRrVq1Kmn/+hw7diyvsStXrqy4vkllzpw5HDt2LO3YyTV25cqV/WPnrDNwCM2J/qYffiWXVfE0s2pihfPH7v4LAHc/4u697n4aeBK4Nlr8IHBhXPikqC2Buz/h7tPdffpQdiBb9fX1SfPDhg3j6NGjeYvds2cPq1evZsyYMUNPuEiOHDmStH8Aw4ZlHhq5xO7Zs4dly5ZVXN+k0rfP6cZOrrHLli2ruLGTNwOHUD0VcR9QNlfbDXgK2OPuD8W1N8Qt9g3g1Wh6E3CTmZ1jZhcDjcCO/KUcpqamJmXbiRMn8hLb09PDggUL+t/SV4qurq5B9y+fsQsWLOD2228PS7JEurq60j6fbuzkEtvT08Ptt99ecWMnb1INtczDr+SGZ7HMdcC/B14xs5eitr8EvmVmVxL7sPUAsATA3V8zs3XA68Ap4A5378134rnq7u5O2TZy5Mi8xI4ZM4bt27cnLVfu6urqBt2/fMVu3bqVNWvWMHXq1PBES6Curo7Ozs5Bn083drKN3bp1K3Pnzs3qH/EzVqqhlnn4lVzG4unu/xewFE/9Kk3MfcB9Q8grZ7ET5EQ9PT0MHx7bxePHjyc8197ejrszYcKEjOvOFNvR0cG9995btsUhXd80NDQk7R/QdxdEWtnEdnR0sHDhQlpbW3PMungG65+GhoaUb7/b29sB0o6dbGMXLlzIvffeG5T3GWPgEGondkpW7nK9PF+IB3m4HaenpyfpEX/LxsyZMxOWX7dunQPe29ubdr3ZxD7wwAOpbn1IeLz77rtB+1XovlmxYkXS/vVtd/z48WnXm01sIfumb1tD6Rv3wftnxYoVKde7bt06Hz9+fNqxk21spr7J29gp1n+5bg+cmQPa1kXt44uQZzHv8yzEIx8FIp2qqiqvra1NaGtpacn6Ps/QWCrgPs/W1lavra31zs7OpO0uXry4YLFLliwp+/s8W1tbvaqqKmn/Wlpasuqb0NglS5ZU1n2eqYpStv9V4dTidMa1tUTrWFyEPFU801u0aFHSekeNGuU1NTUJbc3NzV5fXx8Um0olFM++bTz22GP980eOHPGamhrfu3dvf1tPT4/X19f7/fffn3NsKpVQPN1jr//A/Rs1alRS3zQ3Nyf1TTaxqZyxxbOZ2DeJ7o9rWxQt/1hc2yicGpy9RcizWDfJV6pVq1bR2dnJ5MmTqa2tZcKECWzevDnpwoZ/XMxzjq1knZ2dtLW19e9fS0sL3d3dNDY2Jizn7kk3d2cbW6lWrVpFW1tb/+vf0tLC5s2bs+qbbGMr3t8Ru9v7/Li2McS+qP2tuLa+MhXfTauATmJfpakFJgCbiV0wKvNusoHFoiRJmCUkUQ45lYuBFzPUN4ni+0d9kyhh7KhrEiVfI9zlOd5zflaceYqI5JuKp4hIABVPEZEAKp4iIgFUPEVEAqh4iogEUPEUEQmg4ikiEkDFU0QkgIqniEgAFU8RkQAqniIiAVQ8RUQCqHiKiARQ8RQRCaDiKSISQMVTRCSAiqeISAAVTxGRACqeIiIBVDxFRAKoeIqIBMhYPM2s1sx2mNnLZvaamf23qP1iM9tuZvvM7J/MrCZqPyea3xc9/6nC7oKISPFlc+bZDcx2988R+1/bN5nZTOBB4GF3/wzwPvCdaPnvAO9H7Q9Hy4mInFEyFk+P6Yxmq6OHA7OBn0Xtq4GvR9Pzonmi579kZsn/i3kRkQo2PJuFzKwK2AV8BngU+CPQ7u6nokXagInR9ETgbQB3P2VmHcA44Fi2SanWDk59Mzj1jRRTVsXT3XuBK81sDLAe+LdD3bCZtQAtQ12PiGRB/67kXU5X2929Hfgt8HlgjJn1Fd9JwMFo+iBwIUD0/Gjg/6VY1xPuPt3dpwfmLiJSMtlcbT8vOuPEzP4N8GVgD7EiemO02M3Axmh6UzRP9Pxv3N3zmbSISKlZprpmZlcQuwBURazYrnP3vzazTwM/BcYCvwe+7e7dZlYLrAWmAe8BN7n7/gzbeBc4QQ6fixbYeMonFyivfMopF1A+6ZRTLlDe+Vzk7uflEpyxeBaLme0sl7fw5ZQLlFc+5ZQLKJ90yikXOPPy0TeMREQCqHiKiAQop+L5RKkTiFNOuUB55VNOuYDySaeccoEzLJ+y+cxTRKSSlNOZp4hIxSh58TSzJjN7I/oVpmUlyuGAmb1iZi+Z2c6obayZ/drM3oz+nlvA7T9tZkfN7NW4tpTbt5gVUX/tNrOripDLPWZ2MOqfl8xsbtxzd0W5vGFmX8lzLhea2W/N7PXoF72+F7WXqm8Gy6dU/VM2v3iWJpcfmdlbcX1zZdRe0NcqLq8qM/u9mf0yms9f37h7yR7E7h39I/BpoAZ4GZhSgjwOAOMHtP0tsCyaXgY8WMDtfwG4Cng10/aBucBmYl+4mwlsL0Iu9wB/kWLZKdFrdg5wcfRaVuUxlwbgqmh6JLA32map+mawfErVPwbUR9PVwPZov9cRu78a4B+A/xBN/0fgH6Lpm4B/KkIuPwJuTLF8QV+ruO38J+AfgV9G83nrm1KfeV4L7HP3/e7+EbGb7ueVOKc+8b8OFf+rUXnn7s8S+0JBNtufB6zxmBeIfU22ocC5DGYe8FN373b3t4B9xF7TfOXyjru/GE0fJ/bNtomUrm8Gy2cwhe4f9zL5xbM0uQymoK8VgJlNAr4G/DCaN/LYN6Uunv2/wBSJ/3WmYnLgX8xsl8V+sATgfHd/J5o+DJxf5JwG236p+uy70durp+M+wihaLtHbqGnEzmhK3jcD8oES9U/0tvQl4Cjwa3L4xTOg7xfPCpKLu/f1zX1R3zxsZucMzCVFnvny34H/DJyO5seRx74pdfEsF9e7+1XAV4E7zOwL8U967Fy+ZLcllHr7wOPAJcR+DPsd4AfF3LiZ1QM/B+509w/inytF36TIp2T94+697n4lsR/nuZY8/OJZvnIxs6nAXVFO1xD7Kvd/KUYuZvbvgKPuvqtQ2yh18ez/BaZI/K8zFY27H4z+HiX2k3vXAkf63kZEf48WOa3Btl/0PnP3I9GBcRp4ko/fehY8FzOrJlaofuzuv4iaS9Y3qfIpZf/08Tz+4lkec2mKPupwd+8GVlG8vrkOaDazA8Q+DpwNPEIe+6bUxfN3QGN0BayG2Ae1m4qZgJnVmdnIvmngz4BXSfx1qPhfjSqWwba/CVgYXa2cCXTEvYUtiAGfRX2DWP/05XJTdKXyYqAR2JHH7RrwFLDH3R+Ke6okfTNYPiXsn7L5xbNBcvWFnv4AAAD5SURBVPlD3D9yRuzzxfi+Kdhr5e53ufskd/8UsbryG3dfQD77phBXuHJ5ELvqtpfYZzV/VYLtf5rYFdGXgdf6ciD2ecczwJvAvwJjC5jDT4i93esh9jnMdwbbPrGrk32/5v8KML0IuayNtrU7GmQNccv/VZTLG8BX85zL9cTeku8GXooec0vYN4PlU6r+uYLYL5rtJlaU/mvcmN5B7ALV/wLOidpro/l90fOfLkIuv4n65lXgf/LxFfmCvlYDcpvFx1fb89Y3+oaRiEiAUr9tFxGpSCqeIiIBVDxFRAKoeIqIBFDxFBEJoOIpIhJAxVNEJICKp4hIgP8PrVO7h7deEkUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "state = env.reset()\n",
    "plt.imshow(env.render(mode='rgb_array', show_rewards=True))\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Value Iteration\n",
    "\n",
    "**function** Value-Iteration($mdp, \\epsilon$) **returns** a value function<br>\n",
    "&emsp; **inputs**: $mdp$, an MDP with states $S$, actions $A$, transition model $P_a(s, s')$, rewards $R(s,a,s')$, discount $\\gamma$<br>\n",
    "&emsp;&emsp;&emsp;&emsp;&emsp;$\\epsilon$, the maximum error allowed in the value function of any state<br>\n",
    "&emsp;**local variables**: $V$, $V'$, vectors of value function for states in $S$, initially zero<br>\n",
    "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;$\\delta$, the maximum change in the value function of any state in an iteration<br>\n",
    "&emsp;**repeat**<br>\n",
    "&emsp;&emsp;$V \\leftarrow V'; \\delta \\leftarrow 0$<br>\n",
    "&emsp;&emsp;**for each** state $s$ **in** S **do**<br>\n",
    "&emsp;&emsp;&emsp;$V'[s] \\leftarrow R(s) + \\gamma \\underset{a \\in A}{\\text{ max }} \\sum_{s'}P(s, s',a)V[s']$$ $<br>\n",
    "&emsp;&emsp;&emsp;**if** $|V'[s]-V[s]| > \\delta$<br>\n",
    "&emsp;&emsp;&emsp;&emsp;**then** $\\delta \\leftarrow |V'[s]-V[s]|$<br>\n",
    "&emsp;**until** $\\delta < \\epsilon(1 - \\gamma)/\\gamma$<br>\n",
    "&emsp;**return** V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Let's see this in action!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "GAMMA = 0.999\n",
    "\n",
    "def value_iteration(env, epsilon=0.001, show_values=False):\n",
    "    states = [s for s in range(env.num_states)]\n",
    "    actions = [a for a in range(env.num_actions)]\n",
    "    V1 = {s: 0.0 for s in states}\n",
    "    R, P = env.R, env.P\n",
    "    \n",
    "    if show_values:\n",
    "        img = plt.imshow(env.render(mode='rgb_array', values=V1)) # call this only once\n",
    "    \n",
    "    while True:\n",
    "        V = V1.copy()\n",
    "        if show_values:\n",
    "            img.set_data(env.render(mode='rgb_array', values=V))\n",
    "            display.display(plt.gcf())\n",
    "            display.clear_output(wait=True)\n",
    "            time.sleep(0.5)\n",
    "        delta = 0\n",
    "        for s in states:\n",
    "            V1[s] = R(s) + GAMMA * max(sum(p * V1[s_prime] for (p, s_prime, done) in P(s, a)) for a in actions)\n",
    "            delta = max(delta, abs(V1[s] - V[s]))\n",
    "\n",
    "        if delta <= epsilon * (1 - GAMMA) / GAMMA:\n",
    "            return V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAU8AAAD8CAYAAAD35CadAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3de3SU9bX/8fdOIEQSEBGiKFQpQgsFqggVjy6lXo63SvDg0XZpKQJiL7rE2v6KVGtbj5eqR+3pBS9FTqA3tQi4bD3HK1qpYgEBBRVzqMjNgAqREIgQ9u+PeWaYyWQymSczmQn9vFizMs93vt959ux8Z+e5zWDujoiIZKYo3wGIiHREKp4iIiGoeIqIhKDiKSISgoqniEgIKp4iIiHkrHia2blm9o6ZVZvZ9FytR0QkHywX13maWTGwFjgb2Aj8Hfiau6/J+spERPIgV1ueXwKq3X2du38K/BGozNG6RETaXaccPe/RwIa45Y3ASak6m5k+5iQi+fShu/fOZECuimdaZjYVmJqv9YuIxFmf6YBcFc9NQL+45b5BW4y7Pwg8CNryFJGOJ1fHPP8ODDSz/mZWAnwVeCJH6xIRaXc52fJ0931mdjXwv0Ax8LC7r85gfC7C6pDMLGFZuUkUnx/lJpHmTmpNcxPqOQohoU132wshpkKhN0DLVDxT09xJrZniuczdR2byHPqEkYhICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIhqHiKiISg4ikiEoKKp4hICCqeIiIh/NMVz/r6em6++Wa6du1K7969Wbx4cavHLlmyhEsvvZSSkhK6devGHXfcwZ49e3IYbe5E8zB48GB69+7N2LFjWz02mod+/frRrVs3TjzxxFbl4bXXXuPiiy9uS9jtpr6+nsGDB9O1a1fGjh2b8Tzp168fJSUlnHjiiSnnSWv7FZp8vIc6d+5ceHPH3UPfgPeAN4AVwNKgrSfwDPBu8POwVjyPx99yZceOHT506FAvLy/3TZs2+eLFi724uNirqqrSjq2qqvKioiLv06ePb9iwwZcuXeqAjxw50nfu3JmzmHOVm2ge5syZ44sXL/aTTjqpVXlw91geHnvsMV+6dKmPHz8+bR7q6up84MCBPn78+Gy9BHf3nOQmOk/mzJnjmzZt8pNOOinjefLYY4/5hg0bfPz48bF5EqZfW+Ri7uTjPVRXV+dAVudO09xE61cmt2wUz15N2u4Epgf3pwM/a8XztEvxLC4u9rKyMt+9e3es7ZprrnHAr7zyyhbHAl5UVOR79uyJtU2bNs0BHz58eM5izkVu1q1bl5SH6LrS5WHevHlJeYiObSkPhx56qJ977rkFXzzXrVsXmyfxovOkJfPmzYvNk3jReZJpv7bKxdxp7/fQwoUL/dBDDy3I4pmL3fZKoCq4XwWMy8E6QmlsbOSEE06gtLQ01nbGGWcAMH/+/LTjy8rK6NKlS2z5yCOPBOCDDz7IcqS5tWDBgqQ8RM2fP5/9+/enHFtTU5OUh6hUefjggw/41a9+xTHHHBM+6HayYMGC2DyJF50n6XIDkXkSLzpPMu1XiNr7PTRlyhR+9atftSXk3Mm02sbfgH8Ay4FlwNSgbUfc4xa/3GTsVGBpcGuXLU/Af/CDHyS07dy5s1Xr7dmzpwP+8ssvx9pGjhzpgN9yyy05idc9N1sPw4YNS8pD/Loef/zxlGOj+YrPQ3Rsc3n4xS9+4X379nV396uuuqrgtzyHDRvW4jxJl5voPIkXnSeZ9murXMyd9nwP/eIXv/Dt27fH1nuwbXme6u4jgPOA75jZaU0KczSwJO7+oLuPdPeRbYwhI+Xl5UnLRUXp01BVVUXnzp2ZPHkyu3btYv369SxdupTTTjuN66+/Plfh5kRNTU1SHoBYHrZu3ZpybHl5eSwPL774IuvXr2fatGnN5uGtt95i+vTpVFVVpXi2whPdKkw1T9LlJjpPXnzxRXbt2sW0adNi8yTTfoWqPd5D0bnTo0ePrMaeTZ3aMtjdNwU/t5rZfOBLQI2Z9XH3LWbWB0g92/KgpKSk2bZ0Z/y+8pWvMH/+fCorK2OT58tf/jJPPfVUs7uwhay+vr7FPOzatavF8dE8jBkzJta2Z8+epDxcdtllfPOb34zt1nUE9fX1QOp5ki430XkSn5voPAnTrxDl+j20d+/e2NwpZKG3PM2szMy6Re8D/wq8CTwBfCPo9g1gYVuDzKaGhoZWtTVVVFTE1VdfTV1dXWyz/eyzz6a0tJSzzjorF6HmTFlZWYt56NatW8qxzz//fFIe3D0pDy+++CJz5szh7rvvzv4LyKHocchU+UmXm+g8ic9NdJ5k2q9Q5fo91KNHjw4xd9qy234E8LKZrQReA/7s7v8D3AGcbWbvAmcFywVj586dCcs7duyIHoNtkbtz0UUXJUzuKVOmAPDcc89lN8gc69OnT1IegFgeKioqUo696667kvIQ9dxzz7Fs2TJqa2uZMGECQ4cOzV7Q7aRPnz5A6nmSLjfReRIvOk+WLVuWUb9Clcv3UG1tLf/xH//RIeZO6OLp7uvc/YvB7QvufmvQ/pG7n+nuA939LHf/OHvhtt1f//rXhOVnnnkGgF69eqUd279//4Tl3r17c9hhh2UvuHYyadKkpDxE9erViwsvvDDl2FdffTUpD0AsDy+//DIzZ87k/fffx8wSbg888ADz5s2LLReiSZMmAannSbrcQOp58vLLL2fUr1Dl8j00c+ZMvvvd7ybNHSA2dz788MO2voSs+Kf6hFFxcTErVqxIOG717LPPAjBuXPorqjZv3pyw/Mknn7Bjx47sBtkOKisrk/IQNW7cuBYP/vfv3z8pD0AsDwMGDGD69OnNnp286qqrGD9+fPwVFwWnsrIyNk/iRedJutxA6nkyYMCAjPoVoly/h1LNHSA2d1pTpNtFpqfnc3GjnS5VmjhxogP+61//OtbWvXt3Lykp8bVr18baxo4d6+Xl5X7bbbfF2gAfNmyYNzY2xtoeeOABB7xXr145izlXuWmah5qamqQ87N27NykPt99+e1Ieos/Xq1cvr6urS7nOjnCpkvuBeRJVU1MTmydRe/fujc2TqNtvvz02T+JF50k0N63t11a5mDv5eg9xEF6q1KHMnj2buro6Nm7cSGlpKRUVFTz11FM0NDQwcODAWL9ocuIviN67dy/f/va3OfPMM+nUqRNlZWUsX76cNWvWsG3btny8nDaJ5mHQoEFUVFQwderUpDwASXmYPn16LA+HH344ZWVlDB48OJaHphd+d0TReTJo0CBKS0uZOnVqbJ7E8wN//IFIbqLz5PDDD6dTp04MHjw4Nk+iuWltv0Kk99ABFv/Lz1sQZglBFEJMhaLpsUHlJlF8fpSbRJo7qTVzzH2ZZ3jN+T/VlqeISLaoeIqIhKDiKSISgoqniEgIKp4iIiGoeIqIhKDiKSISgoqniEgIKp4iIiGoeIqIhKDiKSISgoqniEgIKp4iIiGoeIqIhKDiKSISgoqniEgIKp4iIiGoeIqIhKDiKSISgoqniEgIKp4iIiGoeIqIhJC2eJrZw2a21czejGvraWbPmNm7wc/DgnYzs/8ys2ozW2VmI3IZvIhIvrRmy/O/gXObtE0HnnP3gcBzwTLAecDA4DYVmJmdMEVECkva4unuLwEfN2muBKqC+1XAuLj2OR7xKtDDzPpkK1gRkULRKeS4I9x9S3D/A+CI4P7RwIa4fhuDti1kwMxChnXwU25SU25apvxkV9jiGePubmae6Tgzm0pk115EpMMJe7a9Jro7HvzcGrRvAvrF9esbtCVx9wfdfaS7jwwZg4hI3oQtnk8A3wjufwNYGNc+ITjrPhqojdu9FxE5aKTdbTezPwBjgF5mthG4GbgDeNTMJgPrgUuC7n8BzgeqgXrgijBBuWd8FOCgFX+casyYMfkLpEAtWrQodl/zJlH83FFmEmXj6G/a4unuX0vx0JnN9HXgO20NSkSk0OkTRiIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhJC2uJpZg+b2VYzezOu7cdmtsnMVgS38+Meu8HMqs3sHTM7J1eBp1NbW8uwYcPo1q0bmzdv5m9/+xudOnVizpw5acfOmTOH4uJijjrqKDZu3MiyZcswM0aNGkVdXV3Kcbt27cLMuPjii7P5UqSdRefO3Llz2bx5M6NHj2713PnmN7+JmfHiiy9SU1PDkCFDKCoqYubMmbE+r776KmbG+PHjeeutt/j73/9OeXk5RUVF3HXXXbl8ae1mLGDBrbVqgWHAXGAz8DegE5A+6/lh7t5yB7PTgDpgjrsPDdp+DNS5+91N+g4B/gB8CTgKeBYY5O6NadaREES6mFpjwoQJzJ07l1mzZjFp0iQADj/8cHbt2sXq1asZMGBAyrHdu3dn586d/OUvf+G8884DYODAgVRXV3PTTTfx05/+tNlxV155Jb/5zW8YP348f/rTn9r8GgDMDky/MWPGZOU5DyaLFi2K3c/GvIEDcyf6fB9//DEDBw5k165d7NmzJ+W4qqoqJk6cSO/evdm6dSsA7733Hp///OfZt28f+/btAyLF86yzzqK2tpbi4mIAfve733H55ZdjZuzfvz8rryN+7mQnM+k1Ar8A/hPYmOG6JxApnPH9Dwd2AamzHk4zRX2Zu4/M5DnSbnm6+0vAx618vkrgj+7e4O7/AKqJFNJ2N3fuXE499dRY4QSYNWsWDQ0NjB49usWxO3fupFu3brHCCTBlyhQAHnjggWbHVFRUqLgdBO69997Y3Inq2bNnbO60VNiicy1+6/HYY4/lvvvuo7GxMVaMR48eTV1dXaxwAlx22WUMGDAga38A8qUYmAZsCDF2LnBqk7ZZQAOQnT8n2dWpDWOvNrMJwFLgenffDhwNvBrXZ2PQlhcDBw5MWP7CF74AwIcffph27O7du9m3bx+dOnVKGNOnT59m+5955plcdtllXH755W0JuV3V1tZSXV3Nzp07GTlyJBs3bmT79u3s27eP4cOHc+ihhyb0X7FiBbt37+bTTz+ltLSUiooK+vfvD8CyZcuoq6vD3RkxYgSbN29m27ZtlJWVMWDAgKTnKlSLFy8GUs+dt99+myFDhjQ7NlpYe/TokdA+dOhQADZs2MBnPvOZlOtuaav2n8XAJstfCH6+DTSf9fwJe8JoJjAAOB7YQmQrPSNmNtXMlprZ0pAxpFVRUZGwnKrwNdWzZ0/27dvHkiVLYm3R3cPmjmf+8pe/TDim1VEceuihnHjiiQCsXbuWoqIiDj/8cDp37syqVav49NNPE/qbGUOGDOHkk0+ma9eurF+/PvbYiSeeSElJCRDZVS0qKqJz58588sknrFq1qv1eVButXbsWSD133nnnnbTP0bQIRsdWV1enHNPQ0MC2bdsyivVgVNFkOfqOTZ/19heqeLp7jbs3uvt+4CEO7JpvAvrFde0btDX3HA+6+8hMjzNkomfPngnL5eXllJaWph330Ucf8eSTT3L66adjZpgZ3bp1Y8+ePdx4442xfnv37mXEiBG89957SVsbHc0xxxzDoEGDGDRoEKNHj6axsZH3338/oc8Xv/hFDj30UEpKShg0aBBA7DhevOHDh8eep6KigsbGFg95F5R//OMfQOq5E328OTNmzADg+9//fkL7EUccAUS2PFO54oor+PTTTxPm1z+jnk2Wy4FSIHXW8ydU8TSz+E24i4DomfgngK+aWRcz609kK/y1toUYXnPHj1pzTOmhhx5i/PjxDBs2jGXLlvHUU0+xaNEiTj/9dD7++MDh3xtvvJHGxkZuvfXWrMZdKFpz4iJdPqOHPTqK6EmWVHMn/iRMUz/84Q8ZNWoUGzZs4K677mLBggVMnz49dvy0pVw8+uij/Mu//As/+tGP2vgKOrbmZpOT2Vn79pJ2ZpvZH4AxQC8z2wjcDIwxs+OJvK73gKsA3H21mT0KrAH2Ad9Jd6Y9l5rudqZqa+qqq67imGOO4ZVXXoltqd56663MmDGDSy65hGeffRaI7K4vWbKELl26ZDfwAvXuu+9SW1tLQ0NDhz+xkUrXrl3ZuXNnyrlTXl7e4thFixZx9913c9NNN1FcXMy1117LAw88wOjRo+nevXuz47Zu3cpxxx3H448/TufOnbP2Wjqi5t6dnxLZAi00aYunu3+tmeZZLfS/FSiITbGmx5jeeuutVr3p3Z3rrrsuYRf/hhtu4Gc/+xnPPfccAPfccw89evTg3HPPTRr/l7/8hb59+/LGG29w2GGHtfFVFIZly5Zx1FFHxU6kNDQ08Morr+Q5quw7/fTTefTRR1POnfiz8M3p2rUrP/rRjxK2IH//+98DNDtXoifm3n777SxE3z6a2wrcS9vOPkc1PSr8FpEttJaznh8da58qQ9GD/1Fvvhk5utCrV6+0Y5vbPSsqOnCU49NPP2Xz5s3Njt29ezebNm3qUMf6WuLu1NXVtbjVdbA49dRTefTRR1POnc997nMZP+fzzz8PkLRVWV1dzeDBg1t18X0h2dtMW7YKydomy9HjgZlnPfcO2o9nTpw4kVdffTXhLPiUKVMoKSnhb3/7W6ytsrKSbt26cfvttyeMf+ihhxKO+T344INs3749VninT5+OuyfdAMaPH4+7t6pIdwRmRpcuXaitrY21ZetC7kJzzTXXxOZO1NatW2NzJ/oHdN++fbG5E3XfffclXBsMMHnyZGbNmsUll1wSa1u0aBE9evTgscceo6qqCndnz549sVuh69TMLVOVQLcmbRNJvM4RYApQQmEWqkKMKSt+/vOfM3ToUL73ve+xbds2lixZwq5du7j//vsTruF74oknqKur45577om1jRkzhjfeeIPKykq2bt3KmjVrmDZtGiUlJcyalfKIxUHtyCOPZN26dVRXV7N69WrWrFnT4smTjiw6d+bOncu2bdu44IILYnMn6p133onNnXgvv/wyd999N+vXr2fRokU8/PDDnH/++VRVVcX6XHfdddTW1jJjxgwOOeSQpFtzVzB0NOlewRNEPrYY7+fAUCIXy28DlhD5dNH9FKaDtnh2796dV199lWnTptGvXz8uvPBCXnrpJa644oqEfhdeeCFlZWVMmzYt1vbMM88wc+ZM6urqOOqooxg1ahQTJkxgxYoVjB07tr1fSs7U1tayfPly4MAhjvr6elauXAlATU1N7I38mc98hs6dO7N582bKyso4/vjjKS0t5fXXX2fz5s0sX748dpJl9erVAKxcuZKamhoAVq1a1WGKQnTu3HLLLfTr14+jjz46ae587nOfi82dqFGjRnH22Wdz//33c9xxx3HppZfyyCOP8Oc//znh+PnBerIN4C4iF3+XxLX1IPkC9wuBsiZt3Ylsed5C5HrHC4GXgCsoTGk/294uQeTgs+0HC322vWW5+Gz7wSIfn23vKNrls+0iIpJMxVNEJAQVTxGREFQ8RURCUPEUEQlBxVNEJAQVTxGREFQ8RURCUPEUEQlBxVNEJAQVTxGREFQ8RURCUPEUEQlBxVNEJAQVTxGREFQ8RURCUPEUEQlBxVNEJAQVTxGREFQ8RURCUPEUEQlBxVNEJIS0xdPM+pnZC2a2xsxWm9m1QXtPM3vGzN4Nfh4WtJuZ/ZeZVZvZKjMbkesXISLS3lqz5bkPuN7dhwCjge+Y2RBgOvCcuw8EnguWAc4DBga3qcDMrEctIpJnaYunu29x9+XB/Z3AW8DRQCVQFXSrAsYF9yuBOR7xKtDDzPpkPXIRkTzqlElnMzsWOAFYAhzh7luChz4AjgjuHw1siBu2MWjbEteGmU0lsmXa3HoyCUsE0LyR9tXq4mlm5cA8YJq7fxI/Ud3dzcwzWbG7Pwg8GDx3RmP/WS1atCjfIUgHpT8r2deqs+1m1plI4fyduz8eNNdEd8eDn1uD9k1Av7jhfYM2EZGDRmvOthswC3jL3e+Je+gJ4BvB/W8AC+PaJwRn3UcDtXG79yIiBwVzb3mP2cxOBf4KvAHsD5pnEDnu+SjwGWA9cIm7fxwU218C5wL1wBXuvjTNOhKCSBfTP5Omx/GUm0RNDh/lMZLCkzB3lJpEyccxlrn7yIyeohAmnIpnaiqeLVPxTE3FswVZKJ76hJGISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIaQtnmbWz8xeMLM1ZrbazK4N2n9sZpvMbEVwOz9uzA1mVm1m75jZObl8AS2pr6/n5ptvpmvXrvTu3ZvFixe3euySJUu49NJLKSkpoVu3btxxxx3s2bMndL9CE83N4MGD6d27N2PHjm312IULF3LBBRdQUVHBkUceyUUXXZTU54MPPuD000+nb9++lJaWMmDAAL7+9a9n8yXkVH19PYMHD6Zr166MHTs2o7mzcOFCKioqKCkp4aKLLuKll15K2fe73/0ugwYNomvXrhx55JGcfPLJ2Qg/fx4Hjs5wTD1wM9AV6A20PtX55e4t3oA+wIjgfjdgLTAE+DHwvWb6DwFWAl2A/sD/AcVp1uHxt2zYsWOHDx061MvLy33Tpk2+ePFiLy4u9qqqqrRjq6qqvKioyPv06eMbNmzwpUuXOuAjR470nTt3ZtyvLXKRG3eP5WbOnDm+ePFiP+mkk1qVm2hMo0aN8kWLFvnzzz/vgwcP9l//+tcJfV555RX/t3/7N583b56vWbPG77zzTi8rK/M777wza68hGku2cxOdO3PmzPFNmzb5SSed1Oq5c9VVVzngixYt8g8++MAHDx7sZpaUH3f35cuXe58+fXz27Nn++uuv+x/+8Af//Oc/n7XXkTB32uPf+yHWtwNnKE45ziacxTjFOFU5jpWk21JPUwub3jLqHPl9sBA4u4XieQNwQ9zy/wInp3nOrL8JiouLvayszHfv3h1ru+aaaxzwK6+8ssWxgBcVFfmePXtibdOmTXPAhw8fnnG/tshFbtatW5eUm+i60uVmxIgRfu211zYb5+TJk2PLr7zySlKfxsZGB3z69OkhI0+Wi9xE50686NxpyYgRIxxIys+///u/J42dMGFCVgt+c9qteN6GcwXOcyHWV4xThrM7ru2a4DmuzGHMWSieGR3zNLNjgROAJUHT1Wa2ysweNrPDgrajgQ1xwzaS+YZ8mzU2NnLCCSdQWloaazvjjDMAmD9/ftrxZWVldOnSJbZ85JFHApHd0TD9CsmCBQuSchM1f/589u/f3+y43bt3s2LFCk444YRmH3/yySejfwwZPXp00uNFRZHp9v7774cNPecWLFgQmzvxonMnVW4AVqxYAZBybDQ3W7Zs4be//W3WYs67G4CHgTNCjG0kUlHip2L0edK/TfOq1cXTzMqBecA0d/8EmAkMAI4HtgD/mcmKzWyqmS01s6WZjMvEKaeckrB81llnAfDhhx+2OK5nz57s3Lkz4TjXn/70JwCuueaajPsVmtmzZyflJurDDz9k4cKFzT7W0NDA/v37my26ADU1Nbzwwgsp19vQ0ADA6aefnmHE7Wf27NlA6rmTKjdwoLA2zc/ZZ58NEMvNjBkz2L9/P+eck7fTAYWl6VQ8K/jZ8ts071pVPM2sM5HC+Tt3fxzA3WvcvdHd9wMPAV8Kum8C+sUN7xu0JXD3B919pLuPbMsLaEl5eXnScnTrpyVVVVV07tyZyZMns2vXLtavX8/SpUs57bTTuP766zPuV2hqamqScgMHtgy3bt3a7LgePXrQt29f3nzzzZTP/fHHH6d8bMmSJRxyyCGMGzcuw4jbT01NDZB67qTKDUDfvn0BkvJz2GGRnbJobjZv3gxA7969mThxIgMHDqS8vJyTTjqJWbNmZeeFdCRNp2I5HeI6oNacbTdgFvCWu98T194nrttFQHTGPAF81cy6mFl/YCDwWvZCbr2SkpJWtTX1la98hfnz51NdXU15eTnHHnssX/7yl3n66ac55JBDMu5XaOrr61vMza5du1KOnTBhAlVVVWzfvr3Zx1sae//993P99ddTUVGRYcTtp76+Hkg9d9LlBiJ/VJuOgwO5ie75/PnPf2bw4MH89Kc/5frrr2flypVMmTKl7S+io2nuLZn+bZp3ranvpwBfB85oclnSnWb2hpmtAr4MXAfg7quBR4E1wP8A33H3xtyE37LobmK6tqaKioq4+uqrqaurix0cPvvssyktLY3tvmXSr9CUlZW1mJtu3bqlHHvrrbcyZcoUTjnlFEpLSznhhBOYMWNG7PGePXs2O+7YY49l+fLl3HLLLW2MPrfKysqA1HMnXW527drFlClTKC0tpaysjBkzZrB69WrgQG6ixfSCCy7gBz/4AV/72tf4yU9+Qn19PT169OCmm27K9ssqbM29JdO/TfMv0zNMubiRgzPKgH//+99PaNu+fXur1gH4ddddl9C2devWpLGt7dcWucjN8ccfn5Sb+HUtWLAg4+eMjl25cmXSYx999JEPHTrUt2zZEire1qw3m7lpae6Eyc3rr7+ekJuLLrrIAT/vvPOS+p544ol+6aWXhgu+iYS5017/Ml0fON9v0ra9HeJu77PtHc1f//rXhOVnnnkGgF69eqUd279//4Tl3r17x45dhelXSCZNmpSUm6hevXpx4YUXhnrecePGMXz48NhydXU1AwYM4Fvf+hZvvPFG7EqEQjZp0iQg9dwJk5tf/vKXALHcRE8mPv3000l99+/fX/DzJ+uaTsVngp/p36Z5ddAWz+LiYlasWJFwjOrZZ58FaNUJi+hB/ahPPvmEHTt2hPK9VR0AAAjHSURBVO5XSCorK5NyEzVu3LgWT6rdd999SW21tbUAfOtb30poP+WUU6isrOSPf/xjGyNuP5WVlbG5Ey86d9Ll5sYbb0xoq62tZd68eQltp512Gv369aOxMfFo1v79+1m3bl2zl3kdtIqBFUD8VHw2+Fm45xUjMt1UzcWNHOyaTpw40YGET3Z0797dS0pKfO3atbG2sWPHenl5ud92222xNsCHDRvmjY2NsbYHHnjAAe/Vq1fG/doiF7mJPm98bmpqapJys3fv3qTc3HvvvUnPNWnSJL/kkksS2l544QW/7bbbfPfu3c3esvk6sp2b6NyJqqmpic2dqL1798bmTtS9997r5557bsJzTZo0yYGk/MydO9cB37dvX6zt6aefdsDr6uqy8joS5k57/WtpfWOJfJLotri2iUH/X8e1dccpwVnbDnFqtz3Z7NmzqaurY+PGjZSWllJRUcFTTz1FQ0MDAwcOjPWLJiL+4ue9e/fy7W9/mzPPPJNOnTpRVlbG8uXLWbNmDdu2bcu4XyGK5mbQoEFUVFQwderUpNwASbkZNWoUxx13HD169KBz585ccMEFnHPOOTzyyCMJ46ZNm8aMGTM45JBDmr3t27evXV5nGNG5M2jQIEpLS5k6dWps7sTzA3/8gUhuDjnkEI477jg6d+7MEUccwTnnnIO7J+Xn8ssvx9254IIL6NWrF/369WPu3LmsXr06dtKqw7iLyNXeR8S19SDyQe2vxbVFy1T85wxmA3VEPkpTClQATxE5YZQ4FQuOxf/y8xaEWUIQhRBToYhcKXaAcpMoPj/KTaKEuaPUJLKklmWe4TXnB+2Wp4hILql4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEoOIpIhKCiqeISAgqniIiIah4ioiEkLZ4mlmpmb1mZivNbLWZ/SRo729mS8ys2sweMbOSoL1LsFwdPH5sbl+CiEj7a82WZwNwhrt/kch/bX+umY0Gfgbc6+7HAduByUH/ycD2oP3eoJ+IyEElbfH0iLpgsXNwc+AM4E9BexUwLrhfGSwTPH6mmSX/F/MiIh1Yp9Z0MrNiYBlwHPAr4P+AHe6+L+iyETg6uH80sAHA3feZWS1wOPBha4NSrU1NuUlNuZH21Kri6e6NwPFm1gOYD3y+rSs2s6nA1LY+j4i0gv6uZF1GZ9vdfQfwAnAy0MPMosW3L7ApuL8J6AcQPH4o8FEzz/Wgu49095EhYxcRyZvWnG3vHWxxYmaHAGcDbxEpohcH3b4BLAzuPxEsEzz+vLt7NoMWEck3S1fXzGw4kRNAxUSK7aPu/lMz+yzwR6An8Dpwubs3mFkpMBc4AfgY+Kq7r0uzjm3ALjI4LppjvSicWKCw4imkWEDxtKSQYoHCjucYd++dyeC0xbO9mNnSQtmFL6RYoLDiKaRYQPG0pJBigYMvHn3CSEQkBBVPEZEQCql4PpjvAOIUUixQWPEUUiygeFpSSLHAQRZPwRzzFBHpSAppy1NEpMPIe/E0s3PN7J3gW5im5ymG98zsDTNbYWZLg7aeZvaMmb0b/Dwsh+t/2My2mtmbcW3Nrt8i/ivI1yozG9EOsfzYzDYF+VlhZufHPXZDEMs7ZnZOlmPpZ2YvmNma4Bu9rg3a85WbVPHkKz8F841nLcTy32b2j7jcHB+05/R3FRdXsZm9bmZPBsvZy4275+1G5NrR/wM+C5QAK4EheYjjPaBXk7Y7genB/enAz3K4/tOAEcCb6dYPnA88ReQDd6OBJe0Qy4+B7zXTd0jwO+sC9A9+l8VZjKUPMCK43w1YG6wzX7lJFU++8mNAeXC/M7AkeN2PErm+GuB+4FvB/W8D9wf3vwo80g6x/DdwcTP9c/q7ilvPd4HfA08Gy1nLTb63PL8EVLv7Onf/lMhF95V5jikq/tuh4r81Kuvc/SUiHyhozforgTke8SqRj8n2yXEsqVQCf3T3Bnf/B1BN5HearVi2uPvy4P5OIp9sO5r85SZVPKnkOj/uBfKNZy3EkkpOf1cAZtYXuAD4TbBsZDE3+S6esW9gCsR/O1N7cuBpM1tmkS8sATjC3bcE9z8AjmjnmFKtP185uzrYvXo47hBGu8US7EadQGSLJu+5aRIP5Ck/wW7pCmAr8AwZfOMZEP3Gs5zE4u7R3Nwa5OZeM+vSNJZm4syW+4D/B+wPlg8ni7nJd/EsFKe6+wjgPOA7ZnZa/IMe2ZbP22UJ+V4/MBMYQOTLsLcA/9meKzezcmAeMM3dP4l/LB+5aSaevOXH3Rvd/XgiX87zJbLwjWfZisXMhgI3BDGNIvJR7h+0Ryxm9hVgq7svy9U68l08Y9/AFIj/dqZ24+6bgp9biXzl3peAmuhuRPBzazuHlWr97Z4zd68J3hj7gYc4sOuZ81jMrDORQvU7d388aM5bbpqLJ5/5ifIsfuNZFmM5NzjU4e7eAMym/XJzCjDWzN4jcjjwDODnZDE3+S6efwcGBmfASogcqH2iPQMwszIz6xa9D/wr8CaJ3w4V/61R7SXV+p8AJgRnK0cDtXG7sDnR5FjURUTyE43lq8GZyv7AQOC1LK7XgFnAW+5+T9xDeclNqnjymJ+C+cazFLG8HfdHzogcX4zPTc5+V+5+g7v3dfdjidSV5939MrKZm1yc4crkRuSs21oix2p+mIf1f5bIGdGVwOpoDESOdzwHvAs8C/TMYQx/ILK7t5fIcZjJqdZP5Oxk9Nv83wBGtkMsc4N1rQomWZ+4/j8MYnkHOC/LsZxKZJd8FbAiuJ2fx9ykiidf+RlO5BvNVhEpSj+Km9OvETlB9RjQJWgvDZarg8c/2w6xPB/k5k3gtxw4I5/T31WT2MZw4Gx71nKjTxiJiISQ7912EZEOScVTRCQEFU8RkRBUPEVEQlDxFBEJQcVTRCQEFU8RkRBUPEVEQvj/E/sXLPyTdEQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "value_iteration(env, show_values=True)\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Q-Values\n",
    "\n",
    "There's another way to solve MDPs. Instead of simply learning a value (or utility) function, we can learn an expected utility for an agent that starts in state $s$ and takes an action $a$, and thereafter acts optimally. This is called a Q-value or an action-utility, $Q(s,a)$, and must also satisfy the following Bellman equation:\n",
    "\n",
    "$$Q^*(s,a)= R(s) + \\gamma \\sum_{s'}P(s,a,s') \\underset{a' \\in A}{\\text{ max }} Q^*(s',a')$$\n",
    "\n",
    "with Q-Values directly related to utility values as follows:\n",
    "\n",
    "$$V(s) = \\underset{a \\in A}{\\text{ max }}Q(s,a)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Q-Value Iteration\n",
    "\n",
    "So what would Q-Value Iteration look like?\n",
    "\n",
    "$$Q'[s,a] \\leftarrow R(s) + \\gamma \\sum_{s'}P(s, s',a)\\underset{a' \\in A}{\\text{ max }}Q[s', a']$$ \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "def q_value_iteration(env, epsilon=0.001):\n",
    "    states = [s for s in range(env.num_states)]\n",
    "    actions = [a for a in range(env.num_actions)]\n",
    "    Q1 = {s: {a: 0.0 for a in actions} for s in states}\n",
    "    R, P = env.R, env.P\n",
    "\n",
    "    while True:\n",
    "        Q = copy.deepcopy(Q1)\n",
    "        delta = 0\n",
    "        for s in states:\n",
    "            for a in actions:\n",
    "                # Q1[s] = R(s) + GAMMA * max(sum(p * V1[s_prime] for (p, s_prime, done) in P(s, a)) for a in actions)\n",
    "                Q1[s][a] = R(s) + GAMMA * sum(p*max(Q1[s_prime][a_prime] for a_prime in actions) for (p, s_prime, done) in P(s,a))\n",
    "                delta = max(delta, abs(Q1[s][a] - Q[s][a]))\n",
    "\n",
    "        if delta <= epsilon * (1 - GAMMA) / GAMMA:\n",
    "            return Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0.8362458360409998,\n",
       " 1: -1.039,\n",
       " 2: 0.9180409999999999,\n",
       " 3: 0.8771229589999998}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q_value_iteration(env)[6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9180409999999999"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value_iteration(env)[6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# What's the point? Solving MDPs\n",
    "\n",
    "The goal when solving MDPs is to maximize the expected reward over time. In otherwords,\n",
    "\n",
    "$$\\max_{\\pi} \\mathrm{E}\\left[\\sum_{t=0}^{H} \\gamma^{t} R\\left(S_{t}, A_{t}, S_{t+1}\\right) | \\pi\\right]$$\n",
    "\n",
    "Thus, given and MPD $(S, A, P, R, \\gamma, H)$, our goal is to find the optimal policy $\\pi^*$\n",
    "\n",
    "- Exact Methods:\n",
    "    - Value iteration\n",
    "    - **Policy iteration**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Policy Iteration\n",
    "\n",
    "Aside from value iteration, there is a second commonly used algorithm for finding an optimal policy. It calculates both the optimal policy and the value function for all states simultaneously. The **policy iteration** algorithm alternates between **policy evaluation** (given a policy $\\pi_i$ for iteration $i$, calculate the value function $V_i = V^{\\pi_i}$ : the value function of each state if policy $\\pi_i$ were to be executed) and **policy improvement** (calculate a new maximum expected value function policy $\\pi_{i+1}$ using one-step look ahead based on $V_i$.\n",
    "\n",
    "The algorithm is as follows:\n",
    "\n",
    "**function** Policy-Iteration($mdp$) **returns** a policy<br>\n",
    "&emsp; **inputs**: $mdp$, and MDP with states $S$, actions $A$, transition model $P(s,a,s')$, rewards $R(s)$, discount $\\gamma$<br>\n",
    "&emsp;**local variables**: $V$, a vector of value function values for states in $S$, initially zero<br>\n",
    "&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;$\\pi$, a policy vector indexed by state, intially random<br>\n",
    "&emsp;**repeat**<br>\n",
    "&emsp;&emsp;$V \\leftarrow \\text{Policy-Evaluation}(\\pi, V, mdp)$<br>\n",
    "&emsp;&emsp;$unchanged? \\leftarrow \\text{true}$<br>\n",
    "&emsp;&emsp;**for each** state $s$ **in** S **do**<br>\n",
    "&emsp;&emsp;&emsp;**if** $\\underset{a \\in A}{\\text{ max}} \\sum_{s'}P(s,a,s')V[s'] > \\sum_{s'}P(s,\\pi(s),s')V[s']$ **then do**<br>\n",
    "&emsp;&emsp;&emsp;&emsp;$\\pi[s] \\leftarrow \\underset{a \\in A}{\\text{argmax}}\\sum_{s'}P(s,a,s')V(s')$<br>\n",
    "&emsp;&emsp;&emsp;&emsp;$unchanged? \\leftarrow \\text{false}$<br>\n",
    "&emsp;**until** $unchanged?$<br>\n",
    "&emsp;**return** $\\pi$\n",
    "\n",
    "Note: that the policy evaluation step can be done via solving a simplified version of the Bellman equations directly. The intuition is as follows: this is much simpler because the action at each state is fixed by the policy. At the $i$-th iteration, the policy $\\pi_i$ specifies the action $\\pi_i(s)$ in state $s$. Therefore, the simplified Bellman equation for the value function is:\n",
    "\n",
    "$$V_i(s)=R(s)+ \\gamma \\sum_{s'}P(s,\\pi_i(s),s')V_i(s')$$\n",
    "\n",
    "This insight allows us to write a system of linear equations. Thus for $n$ states we will have $n$ linear equations with $n$ unknowns, which can be solved using standard linear algebra methods.\n",
    "\n",
    "For small state spaces, policy evaluation is often very fast and typically converges with very few iterations. However, for MDPs with large state spaces, value iteration will be preferred, since solving a large system of linear equations is difficult. Thus, in practice, value iteration is typically preferred.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lab 1 - Implementation of Policy Iteration on Gridworlds\n",
    "\n",
    "Congratulations! You've made is to the end of the first session. Your task now is to implement Policy iteration for the GridWorld environments used in the examples in today's session."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.6.8"
  },
  "rise": {
   "enable_chalkboard": true,
   "footer": "<h4>Florida International University - School of Computing and Information Sciences</h4>",
   "header": "<h2>Deep RL Bootcamp - 2019</h2>",
   "theme": "simple"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}