reinforcement_learning/reinforcement_learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introduction to Reinforcement Learning\n",
    "### London Self-Driving/Autonomous Car Technology Meetup\n",
    "\n",
    "Sander van Dijk @ Parkopedia\n",
    "\n",
    "27 February 2017"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:33.804936Z",
     "start_time": "2018-05-02T09:03:33.513006Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from __future__ import unicode_literals\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from skimage.io import imread\n",
    "import time\n",
    "from IPython import display\n",
    "\n",
    "%matplotlib inline\n",
    "%config NotebookBackend.figure_format = 'retina'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Horrible Histories\n",
    "## Reinforcing Rats\n",
    "\n",
    "<table style=\"border: 0px;\"><tr style=\"border: 0px;\">\n",
    "    <td style=\"border: 0px; padding: 40px;\"><img src=\"figs/skinner.jpg\" alt=\"Skinner\" style=\"width: 200px;\"/></td>\n",
    "    <td style=\"border: 0px; padding: 40px\"><img src=\"figs/skinnerbox.jpeg\" alt=\"Skinner Box\" style=\"width: 600px;\"/></td>\n",
    "</tr></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "In the 40s, B.F. Skinner put animals into his 'Skinner Box': on pressing a lever, a rat would either get food, or an electric shock through its feet. This tested Skinner's 'Operant Conditioning' theory: changing of behavior by the use of reinforcement which is given after the desired response. Rats getting food learned to press the lever often, those getting shocks learned to stay away from it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Horrible Histories\n",
    "## Rodent Junkies and Self-Pleasuring\n",
    "\n",
    "<table style=\"border: 0px;\"><tr style=\"border: 0px;\">\n",
    "    <td style=\"border: 0px; padding: 40px;\"><img src=\"figs/selfadmin.jpg\" alt=\"Rat self-administering drugs\" style=\"width: 400px\"></td>\n",
    "    <td style=\"border: 0px; padding: 40px\"><img src=\"figs/ratimplant.jpeg\" alt=\"Rat with brain implant\" style=\"width: 400px\"></td>\n",
    "</tr></table>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Scientists then turned it up a notch, and did the same experiments that didn't give out food, but where rodents could self administer drug injections such as cocaine or emphatamine, or could even directly give electrical stimulation to their brain's pleasure centres. The drugged rats would choose cocaine over food, prepared to starve themselves. This result is often cited in anti-drug campaigns, though later research showed that if the rodents were given the option to do other activities besides boring lever pressing, they used much less cocaine. The directly self-pleasuring rats however would ignore food, water, and mates in heat and just press the lever 1000s of times per hour."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Learning Problems\n",
    "\n",
    "* **Supervised Learning** - _Learn from labelled examples_<br>\n",
    "    Image classification, parking availability prediction, behaviour cloning, ...\n",
    "\n",
    "\n",
    "* **Unsupervised Learning** - _Find new structure in unlabelled data_<br>\n",
    "    Clustering, anomaly detection, self-organising maps, ...\n",
    "\n",
    "\n",
    "* **Reinforcement Learning** - _Learn from sparse, delayed reward_<br>\n",
    "    Lever pressing, football, video games, ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center><img src=\"figs/rlloop.png\" alt=\"Sensorimotor Loop\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Reinforcement problems are modeled by a sense-action loop: the agent (animal/robot) is positioned in some environment. The agent observes the state of the environment with its senses. It processes these observations and in return performs a certain action, which affects the state of the environment. Additionally, the environment sometimes offers rewards to the agent when a series of chosen actions had a positive outcome (or negative reinforcement on a bad outcome)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Formally: Markov Decision Process\n",
    "\n",
    "* **State** of environment<br>$s$, $s'$\n",
    "\n",
    "* **Action** chosen by agent<br>$a$, $a'$\n",
    "\n",
    "* **Transition** model: how actions transform state<br>$T_{s, a}^{s'} = Pr(s'|s, a)$\n",
    "\n",
    "* Agent's **policy**: how agent choses actions<br>$\\pi(s, a) = Pr(a|s)$\n",
    "\n",
    "* **Reward** function<br>$r_{s,a}^{s'} = R(s, a, s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Goal: Maximise Expected Reward!\n",
    "\n",
    "How much reward will the agent likely get from now until end of time?\n",
    "\n",
    "Total reward of one episode:\n",
    "\n",
    "<center>$ R^\\infty = r_1 + r_2 + r_3 + \\ldots + r_\\infty $</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Based on a policy and transition model as defined above, you can calculate what the upfront expected total reward is, given that the world is in a specific state. In other words, this is the _value_ that that state has to an agent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "_Value function_ - total expected reward:\n",
    "\n",
    "<center>$ V(s) = E[R^\\infty | s] \\\\ ~ \\\\\n",
    "~ = \\sum_a \\pi(s, a) \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + \\sum_{a'} \\ldots \\\\ ~ \\\\\n",
    "~ = \\sum_a \\pi(s, a) \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + V(s') ]$</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To find the optimal states to be in, the agent is interested in the optimal value function:\n",
    "\n",
    "<center>$V^*(s) = max_a \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + V^*(s') ]$</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This is a recursive function, that is infinitely dependent on itself, how could this be solved?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Solution: Value Iteration\n",
    "\n",
    "1. Start with random estimate of value function, $V_0(s)$\n",
    "2. Iterate until convergence\n",
    "\n",
    "\n",
    "<center>$V_{k+1}(s) = max_a \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + V_k(s') ]$</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Value iteration is guaranteed to converge onto the optimal value function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Example: Coco's Pizza Hunt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Coco the pug finds him self in a simple maze. He can smell his favourite food somewhere, pizza! He doesn't really know how to get there though, and he is only capable of moving in fixed sized steps parallel to the walls: up, down, left, or right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:33.811317Z",
     "start_time": "2018-05-02T09:03:33.806551Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def coco_world():\n",
    "    \"\"\"Creates a matrix representing the grid world\"\"\"\n",
    "    world_mat = np.zeros((8, 13))\n",
    "    world_mat[1:-1, 1:-1] = 1\n",
    "    world_mat[1:4, 4] = 0\n",
    "    world_mat[4:8, 8] = 0\n",
    "    return world_mat\n",
    "\n",
    "def draw_world(world_mat, coco_pos=None, goal_pos=None, fig=None):\n",
    "    \"\"\"Draw the grid world with agent and goal if given\n",
    "    \n",
    "    This uses the EmojiOne Color font: https://github.com/eosrei/emojione-color-font,\n",
    "    change the characters below if you don't want to install it.\"\"\"\n",
    "    if fig is None:\n",
    "        fig = plt.figure(figsize=tuple(reversed(np.array(world.shape) * 0.66)))\n",
    "\n",
    "    plt.clf()\n",
    "    plt.imshow(world_mat, cmap='bone')\n",
    "    if coco_pos is not None:\n",
    "        plt.text(*reversed(coco_pos), 'O', fontname='EmojiOne Color', fontsize=40,\n",
    "                 horizontalalignment='center', verticalalignment='center', color='brown')\n",
    "    if goal_pos is not None:\n",
    "        plt.text(*reversed(goal_pos), 'X', fontname='EmojiOne Color', fontsize=40,\n",
    "                horizontalalignment='center', verticalalignment='center', color='red')\n",
    "    plt.axis('off')\n",
    "    display.display(plt.gcf())\n",
    "    display.clear_output(wait=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:34.105353Z",
     "start_time": "2018-05-02T09:03:33.812828Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfEAAAFBCAYAAABn+JYIAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAD4hJREFUeJzt3X2MVfWZwPHnMsObqKOMiOIuRVEbEDBGKrqu2VTrS1qsNq0tJG3/0BoSMWilido/qglNbWjapKXF2JiYtKS2pi++pNS6ssmuuysm7ZZlfYmlIuqGdwQEBpwZ5u4fd8v1DNBhZu7MPc/4+SRGz+HOj4fkzPlyjnfOrVSr1QAA8hnV7AEAgIERcQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSah2KRSuVisfAAcAgVKvVSl+vcSUOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJNXa7AGGQ7VabfYI9EOlUmn2CAWOH/hwKNu550S4EgeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSam32AJy49zZtij1//nN0bN0a3R0dMaq1Nca0tcUpH/lITLzoohg9YUKzRwRgGIl4yXVs3Rqvr1oVb/3ud9GxdetxX1dpbY3Jl10W53/uc/H3110XlUplGKcEoBkq1Wq18YtWKo1fdBCG4s841Hq6uuLlH/84Xn300ejp7OzX154+Y0bMW7YsJs6YMUTTDa2y/QUk4/ED9F8Jzz19DiTiJfT+nj3xwl13xfY//OGoXxvX3h6nTJsW4888M7o7OuLgtm2xZ8OGqB4+XHjdqDFjYt6yZXHu/PnDNXbDlPAbqdkjAMOghOeePgdyO71kug4ciH+5/fbY/eqrhf1nX3VVzLz11jhz7tyojCq+H/HQrl2xafXqeHnlyuh8772IiOjp7IwX77svolqNc2+8cdjmB2D4uBIvmRfvvz/efPrpI9uV1ta47MEHY/pnPtPn1x7csSP+42tfK1zBt4wbFzc88US0TZ8+JPMOhRL+bbjZIwDDoITnnj4H8iNmJfL2739fDPioUXHFQw+dUMAjIsZPmhT/tHJltM+efWTf4UOH4j/vvTd6uroaPi8AzSXiJdHT3R3/tXx5Yd8FCxfGtE9+sl/rjJ4wIf7xe9+L1vHjj+zb/dprsfHJJxsyJwDlIeIl8c7zzxd+hGxce3tcvGTJgNaaMGVKXLRoUWHf66tWDWo+AMpHxEtiw+OPF7anf/azMfrkkwe83gULFkTL2LFHtvf+5S+x7aWXBrweAOUj4iXQ3dERO9atK+w796abBrXmmFNOib+7+urCvi0vvjioNQEoFxEvgZ3r10e1u/vI9klnnRWnTps26HUnX3558ff5058GvSYA5SHiJbBr/frC9sSZMxuybu91dr38clR7ehqyNgDNJ+Il0LFtW2H71Ab9THfb+ecXtg8fOnTkYTAA5CfiJdA7rGNOPbUh67aMGVN4c1tExPt79zZkbQCaT8RLoHfEB/Ou9N56r9Up4gAjhoiXQa/Hejb0wX8le4wgAI0j4iXQ+/Z55/79DVu7a9++4u/V1tawtQFoLhEvgd5hbdSbzw53dsbh998v/l4N+v/tADSfiJfA+EmTCtvvbdzYkHX3vvFGYbtl7FgRBxhBRLwEzrj44sL2u70+S3ygen8m+cRZs2JUS0tD1gag+US8BNrnzInKB+LasWVLvLdp06DX3bp2bWF70iWXDHpNAMpDxEtg9IQJR12Nv/nUU4Nas3PfvvjfNWsK+8664opBrQlAuYh4SVywcGFh+41f/Sq6BvEu9Q0//3nhTW1t06fHWb2epQ5AbiJeElOvuy7GT558ZPvQrl3x3ytWDGitA5s3xyuPPFLYd+EXvzio+QAoHxEviVGtrXHJ0qWFfRt+9rPYtHp1v9bpOnAg/n3p0ug+ePDIvtM++tE47+abGzInAOUh4iUy7VOfimnz5x/Zrvb0xIv33x8bf/ObE/r6gzt3xr8uXlz4VLSWsWPjH5Yvj5YxYxo+LwDNVan2euRnQxatVBq/6CAMxZ9xqHTt3x///OUvx57XXy/sP/uqq2LmbbfFmZdeGpVRxb97HXr33Xhr9er4nx/9qPigmEolLv/mN9NdhVdK9qjYTMcPMHAlPPf0OZCIl9Ch3bvj3+68M3auW3fUr41rb49Tzzsvxp9xRnR1dMTB7dtjz4YNUe3uLrxu1OjRcdmDD6YLeEQpv5GaPQIwDEp47hHxiJwn4cOdnfHyww/Ha489Fj1dXf362tMuvDDmLVsW7bNmDdF0Q6uE30jNHgEYBiU894h4RO6T8IEtW+L1VavirdWr4+D27cd9XaWlJc6cOzfOv+WWmHr99Ufdcs+khN9IzR4BGAYlPPeIeMTIOQnv3bgx9m7YEB1bt0b3wYNRaWmJsW1tcfLUqdE+e3aMnjCh2SM2RAm/kZo9AjAMSnjuEfEIJ+FsSviN1OwRgGFQwnNPnwPlvecKAB9yIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQVGuzB4DeqtVqs0cgqUql0uwRChzLDDVX4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4ACQl4gCQlIgDQFIiDgBJiTgAJCXiAJCUiANAUiIOAEmJOAAkJeIAkJSIA0BSIg4ASYk4wIfd+vURY8ZEVCq1fyZMiHjzzf6vs2VLxMSJ9XVaWiJeeqnx83KEiAN82M2ZE3HvvfXtjo6I22/v/zp33BGxe3d9++67I+bNG/x8HFelWq02ftFKpfGLDsJQ/BmB8qlUKs0eoSDVuaezM+KSSyJefbW+79FHI2677cS+/he/iFiwoL49fXrtCv+kkxo75xAq4fHT50AiDowYJTwJN3uE/lm7NuLKKyN6emrbp51Wi/rZZ//tr9u5M2LmzIgdO2rblUrEmjURH//40M7bYCU8fvocyO10AGouvzxiyZL69p49EYsX9/11S5bUAx4R8ZWvpAt4Vq7EgRGjhFdSzR6h/zo6ImbNKr6x7YknIm655divf+aZiE9/ur59zjkRr7wS0dY2tHMOgRIeP26nRyT9RgL6rYQn4WaPMDBr1kR84hP17cmTa7fVJ04svm7v3tpt9M2b6/ueeSZi/vzhmbPBSnj8uJ0OQD9dc03xDW3btkV89atHv27p0mLAFy5MG/CsXIkDI0YJr6SaPcLAHesq+9lnI66/vvbfzz8fce219V8744yI116r/TupEh4/rsQBGIC2toiVK4v7Fi2K2L8/4sCBo3+O/Ac/SB3wrFyJAyNGCa+kmj3C4C1YUPsZ8L+6887aj5CtWFHfd+ONEU8/PfyzNVgJjx9vbIsYId9IQJ9KeBJu9giDt2NHxIwZEbt21bZH/f8N3L/+LHlbW+3d6Oec05z5GqiEx4/b6QAMwqRJEd//fn27p6ce8IiI73xnRAQ8K1fiwIhRwiupZo/QOPPnR/z2t8V9V19d+3G0EaKEx48rcQAaoKvr6H0n8jQ3hpSIA/C3PfZYxHPPHb3/G9+ofXAKTSPiABzf1q21h7ocyyuvRDz00PDOQ4GIA3B8ixcXPyP8C1+IGDeuvv2tb9Ue8kJTiDgAx/bLX0b8+tf17enTa7fWH3igvq+zs/apZR98xzrDxrvTgRGjhO8ubvYIA/fuu7XHrm7bVtv+4GeEd3dHfOxjEevW1V+/YkXtQTCJlfD48e50AAbg7rvrAY8ofkZ4a2vEo49GtLTUf/3rX494553hnRERB6CXZ5+N+OlP69tTptQe6vJBl15a/GSzffsi7rhjeObjCLfTgRGjhLdDmz1C/+3bFzFrVsTbb9f3PflkxE03Hf3agwcjZs+OeOON+r7HH689bz2hEh4/bqcD0A/33VcM+Oc/f+yAR0SMHx/xyCPFfXfdVfv/6QwLEQeg5oUXIh5+uL7d3l78tLJjueaaiFtvrW9v3x5xzz1DMx9HcTsdGDFKeDu02SOcuEOHIubMidiwob7vJz+J+NKX+v7a3btrn3T2wTfCPfdcxLXXNn7OIVTC48ftdABOwAMPFAN+ww0nFvCIiNNPj/jhD4v7Fi2K6Oho3HwckytxYMQo4ZVUs0c4MX/8Y8S8eRGHD9e2Tz659kjVqVP7t87NN0c89VR9+557Ir773cbNOcRKePz0OZCIAyNGCU/CzR6hb11dEXPnRqxfX9830Ae3bN5ce0DM3r217ZaWiLVra+snUMLjx+10AP6Gb3+7GPArrxz4R4xOmRKxfHl9+/Dh2kNiursHNyPH5UocGDFKeCXV7BHohxIeP67EAWCkEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJJqbfYAw6FSqTR7BOBDyLmHoeZKHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgqUq1Wm32DADAALgSB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBISsQBICkRB4CkRBwAkhJxAEhKxAEgKREHgKREHACSEnEASErEASApEQeApEQcAJIScQBI6v8A2FC2WITT4kUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 617.76x380.16 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "world = coco_world()\n",
    "draw_world(world, coco_pos=(2, 2), goal_pos=(5, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Initially he has no idea how to navigate in this world, so all he can do is just walk around randomly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:34.110357Z",
     "start_time": "2018-05-02T09:03:34.107080Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def action_target_coord(state_coord, action):\n",
    "    \"\"\"Function that determines which state an action would lead too if unobstructed\"\"\"\n",
    "    if action == 0:\n",
    "        return [state_coord[0] + 1, state_coord[1]]\n",
    "    elif action == 1:\n",
    "        return [state_coord[0], state_coord[1] + 1]\n",
    "    elif action == 2:\n",
    "        return [state_coord[0] - 1, state_coord[1]]\n",
    "    elif action == 3:\n",
    "        return [state_coord[0], state_coord[1] - 1]\n",
    "\n",
    "def state_index(state_coords, state_coord):\n",
    "    \"\"\"Map an x,y coordinate to an index\"\"\"\n",
    "    return np.where((state_coords == state_coord).all(axis=1))[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:34.126032Z",
     "start_time": "2018-05-02T09:03:34.111668Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def random_policy():\n",
    "    \"\"\"Policy that picks each action with equal probability\"\"\"\n",
    "    return lambda s: [0.25, 0.25, 0.25, 0.25]\n",
    "\n",
    "def step_policy(world_mat, coco_pos, policy):\n",
    "    \"\"\"Choose a single action according to the given policy and update the world state accordingly\"\"\"\n",
    "    states = world_mat != 0\n",
    "    state_coords = np.argwhere(states)\n",
    "    state = state_index(state_coords, coco_pos)\n",
    "    action = np.random.choice(4, p=policy(state))\n",
    "    target_coord = action_target_coord(coco_pos, action)\n",
    "    if world_mat[tuple(target_coord)] == 0:\n",
    "        target_coord = coco_pos\n",
    "    return target_coord\n",
    "\n",
    "def run_policy(world, coco_pos, goal_pos, policy, n_steps):\n",
    "    \"\"\"Run policy for a number of steps, drawing the world state at each iteration\"\"\"\n",
    "    fig = plt.figure(figsize=tuple(reversed(world.shape)))\n",
    "    draw_world(world, coco_pos, goal_pos, fig)\n",
    "\n",
    "    for i in range(0, n_steps):\n",
    "        coco_pos = step_policy(world, coco_pos, policy)\n",
    "        draw_world(world, coco_pos, goal_pos, fig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:40.565151Z",
     "start_time": "2018-05-02T09:03:34.127695Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAuEAAAHVCAYAAABfQyW0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAFBtJREFUeJzt3X+M3HWdx/H3dJfSWmCx5Td3iBY1xYIhIOBx5ALIj2gRjKIlUf/gR0go4acJ4B9CghGD0URRCIaERIko8Qc/YkUOLrnz7oBET64HJVj5oV6gBUpbSrdld9u5P+boOC223e7sa3dnH4+E0M+3M5/97CYz8+xnvzPfRrPZLAAAIGfGRC8AAACmGxEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAICw/vGYtNFouAwnAADTUrPZbOzsNnbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADC+id6AVNJs9mc6CVAVVU1Go2JXsK48TgDmD56+fVsZ+yEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAIT1T/QCaHvjxRdr7R/+UIMrV9bI4GDN6O+vmQMDtfd73lNzP/Sh2mPOnIleIgAAXSDCJ9jgypX17N13159+9asaXLnyb96u0d9fBx5/fB3xmc/U359xRjUajeAqAQDopkaz2ez+pI1G9yedBLr5s9oyPFxPff/7tfzOO2vL0NCo7vvuBQvqhJtuqrkLFnRtPUwtvfyPsPF4TgJgcurV17Nms7nTb0yEj0K3flZvrV1bv7niinrlt7/d7u9mzZtXex9+eM0+4IAaGRysjatW1doVK6q5eXPH7WbMnFkn3HRTvXfRoq6siamlV5+0qkQ4wHTSq69nuxLhTkcJG96wof7l4otrzfLlHccPPvnkOvKCC+qA446rxozO98tuWr26Xly6tJ667bYaeuONqqraMjRUj113XVWzWe89++zY+gEAGDs74aPQjZ/VY9dfXy888MDWcaO/v46/8caa/6lP7fS+G199tf7jS1/q2EHvmzWrzrr33hqYP3/Ma2Pq6NWdgyo74QDTSa++nu3KTriPKAz6869/3RngM2bUR2++eZcCvKpq9v771z/ddlvNO+qorcc2b9pU/3nttbVleLjr6wUAYHyI8JAtIyP1X7fc0nHs/eefX4d//OOjmmePOXPqH7/1reqfPXvrsTXPPFPP33dfV9YJAMD4E+Ehf3nkkY6PIJw1b159+PLLd2uuOYccUh+65JKOY8/effeY1gcAQI4ID1lxzz0d4/mf/nTtsddeuz3f+xcvrr4999w6XvfHP9aqJ57Y7fkAAMgR4QEjg4P16pNPdhx77znnjGnOmXvvXX936qkdx15+7LExzQkAQIYID3ht2bJqjoxsHb/roINqn8MPH/O8B554YufX+f3vxzwnAADjT4QHrF62rGM898gjuzLvtvOsfuqpam7Z0pW5AQAYPyI8YHDVqo7xPl36TO+BI47oGG/etGnrxXwAAJi8RHjAtmE8c599ujJv38yZHW/OrKp6a926rswNAMD4EeEB20b4WD4VZVvbzjUkwgEAJj0RnrDNZbi7eoHWHr3cKwBALxPhAduefjL05ptdm3t4/frOrzUw0LW5AQAYHyI8YNsw7tabJzcPDdXmt97q/FpdOt8cAIDxI8IDZu+/f8f4jeef78q86557rmPct+eeIhwAYAoQ4QH7ffjDHePXly/vyrxrtpln7sKFNaOvrytzAwAwfkR4wLyjj67GX8Xx4Msv1xsvvjjmeVc+/njHeP9jjhnznAAAjD8RHrDHnDnb7Ya/cP/9Y5pzaP36+t9HH+04dtBHPzqmOQEAyBDhIe8///yO8XM/+1kNj+FTUlb8+Mcdb8ocmD+/DjrxxN2eDwCAHBEectgZZ9TsAw/cOt60enX996237tZcG156qZ6+446OYx/4/OfHtD4AAHJEeMiM/v465pprOo6t+NGP6sWlS0c1z/CGDfXv11xTIxs3bj227wc/WO8799yurBMAgPEnwoMO/8Qn6vBFi7aOm1u21GPXX1/P/+IXu3T/ja+9Vv+6ZEmtXrZs67G+Pfesf7jlluqbObPr6wUAYHw0mttcUr0rkzYa3Z90EujGz2r4zTfrn7/4xVr77LMdxw8++eQ68sIL64Bjj63GjM5/G216/fX609Kl9T/f+17nhX4ajTrxq1+1Cz4NNRqNiV7CuBmP5yQAJqdefT1rNps7/cZE+Ch062e1ac2a+rfLLqvXnnxyu7+bNW9e7fO+99Xs/far4cHB2vjKK7V2xYpqjox03G7GHnvU8TfeKMCnqV590qoS4QDTSa++nonwLuvmz2rz0FA9dfvt9cxdd9WW4eFR3XffD3ygTrjpppq3cGHX1sPU0qtPWlUiHGA66dXXMxHeZePxs9rw8sv17N1315+WLq2Nr7zyN2/X6OurA447ro4477w67MwztztlhemlV5+0qkQ4wHTSq69nIrzLxjsO1j3/fK1bsaIGV66skY0bq9HXV3sODNRehx1W8446qvaYM2dcvz5TR68+aVWJcIDppFdfz0R4l4kDJotefdKq8jgDmE569fVsVyLcOQ0AABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAsP6JXgAwes1mc6KXAD2v0WhM9BLGhecPmBzshAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQCWLauaObOq0Wj9N2dO1QsvjH6el1+umju3PU9fX9UTT3R/vUx5IhwA4Oijq669tj0eHKy6+OLRz3PppVVr1rTHV15ZdcIJY18fPafRbDa7P2mj0f1JJ4Hx+FkBMDk1Go2JXsK48Fq2A0NDVcccU7V8efvYnXdWXXjhrt3/Jz+pWry4PZ4/v7XD/q53dXedPaSHH2c7/cZE+Ch44gKYPno4DiZ6CZPb449XnXRS1ZYtrfG++7ai/OCDd3y/116rOvLIqldfbY0bjapHH6065ZTxXe8U18OPs51+Y05HAQB424knVl1+eXu8dm3VkiU7v9/ll7cDvKrqoosEODtkJ3wU7B4ATB89vEM30UuY/AYHqxYu7Hxj5r33Vp133jvf/sEHqz75yfb40EOrnn66amBgfNfZA3r4ceZ0lG7yxAUwffRwHEz0EqaGRx+t+tjH2uMDD2ydljJ3buft1q1rnYby0kvtYw8+WLVoUWadU1wPP86cjgIAMGqnndb5hsxVq6quumr7211zTWeAn3++AGeX2AkfBbsHANNHD+/QTfQSpo532uV+6KGqM89s/fmRR6pOP739d/vtV/XMM63/s0t6+HFmJxwAYLcMDFTddlvnsUsuqXrzzaoNG7b/HPHvfEeAs8vshI+C3QOA6aOHd+gmeglTz+LFrc8Af9tll7U+gvDWW9vHzj676oEH8mub4nr4ceaNmd3kiQtg+ujhOJjoJUw9r75atWBB1erVrfGM/z+R4O3PEh8YaH0ayqGHTsz6prAefpw5HQUAYEz237/q299uj7dsaQd4VdU3viHAGTU74aNg9wBg+ujhHbqJXsLUtWhR1S9/2Xns1FNbH2fIbunhx5mdcACArhge3v7YrlxNE96BCAcA2Jm77qp6+OHtj3/lK1VDQ/n1MOWJcACAHVm5snVRnnfy9NNVN9+cXQ89QYQDAOzIkiVVa9a0x5/7XNWsWe3x177WukgPjIIIBwD4W37606qf/7w9nj+/dWrKDTe0jw0NVV10UecnpsBO+HSUUfCOcoDpo4c/tWGilzB1vP5667L1q1a1xo1G65NQTjmlamSk6iMfqXryyfbtb721dSEfdlkPP858OgoAwG658sp2gFe1drtPOaX15/7+qjvvrOrra//9l79c9Ze/ZNfIlCXCAQC29dBDVT/8YXt8yCGti/L8tWOPrbrqqvZ4/fqqSy/NrI8pz+koo+BXeADTRw//mnyilzD5rV9ftXBh1Z//3D52331V55yz/W03bqw66qiq555rH7vnnqrFi8d/nT2ghx9nTkcBABiV667rDPDPfvadA7yqavbsqjvu6Dx2xRWt88lhB0Q4AMDbfvObqttvb4/nzWu94XJHTjut6oIL2uNXXqm6+urxWR89w+koo+BXeADTRw//mnyilzB5bdpUdfTRVStWtI/94AdVX/jCzu+7Zk3VggWdb+R8+OGq00/v/jp7SA8/zpyOAgCwS264oTPAzzpr1wK8qurd76767nc7j11ySdXgYPfWR0+xEz4Kdg8Apo8e3qGb6CVMTr/7XdUJJ1Rt3twa77VX65L0hx02unnOPbfq/vvb46uvrvrmN7u3zh7Tw4+znX5jInwUPHEBTB89HAcTvYTJZ3i46rjjqpYtax/b3QvvvPRS6wI/69a1xn19VY8/3pqf7fTw48zpKAAAO/T1r3cG+EknVS1ZsntzHXJI1S23tMebN7cu8jMyMrY10nPshI+C3QOA6aOHd+gmegmwVQ8/zuyEAwDAZCPCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGH9E72AqaTRaEz0EgBgTLyWweRgJxwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIKzRbDYneg0AADCt2AkHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIOz/AKm3t4CbdQjTAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 936x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "policy = random_policy()\n",
    "coco_pos = (2, 2)\n",
    "goal_pos = (5, 10)\n",
    "run_policy(world, coco_pos, goal_pos, policy, 30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Example: Value Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Now we can perform value iteration to have Coco informed about the actual value of being in each state, i.e. how likely it is that he would make it to the pizza for each state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:40.572735Z",
     "start_time": "2018-05-02T09:03:40.567002Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def create_transition_model(world_mat, noise=0):\n",
    "    \"\"\"Build a 3D array that represents the world's transition model\n",
    "    \n",
    "    Indexing the model at [s, a, s'] gives the probability that performing action `a` in state `s`\n",
    "    results in the new state `s'`. The noise level controls the accuracy of actions: e.g. with a level of 0.1,\n",
    "    when Coco tries to move right, he has a probility of 0.1 to actually move up, 0.1 to move down, 0.1 to move left,\n",
    "    and 0.7 of actually moving to the right.\n",
    "    \"\"\"\n",
    "    states = world_mat != 0\n",
    "    state_coords = np.argwhere(states)\n",
    "    n_states = len(state_coords)\n",
    "    model = np.zeros((n_states, 4, n_states))\n",
    "    for state in range(0, n_states):\n",
    "        state_coord = state_coords[state]\n",
    "        for action in range(0, 4):\n",
    "            for actual_action in range(0, 4):\n",
    "                target_coord = action_target_coord(state_coord, actual_action)\n",
    "                if world_mat[tuple(target_coord)] == 0:\n",
    "                    target_coord = state_coord\n",
    "                next_state = state_index(state_coords, target_coord)\n",
    "                model[state, action, next_state] = 1 - 3 * noise if action == actual_action else noise\n",
    "    return model\n",
    "\n",
    "def create_reward_function(world_mat, goal_pos, trap_pos=None):\n",
    "    \"\"\"Build an array that represents the world's reward function\n",
    "    \n",
    "    In this example the reward is only based on the state the agent gets into, so the function is a 1D vector.\n",
    "    \"\"\"\n",
    "    states = world_mat != 0\n",
    "    state_coords = np.argwhere(states)\n",
    "    n_states = len(state_coords)\n",
    "    \n",
    "    reward_function = np.zeros(n_states)\n",
    "    reward_function[state_index(state_coords, goal_pos)] = 1\n",
    "    if trap_pos is not None:\n",
    "        reward_function[state_index(state_coords, trap_pos)] = -1\n",
    "\n",
    "    return reward_function\n",
    "\n",
    "def create_random_value_function(world_mat):\n",
    "    states = world_mat != 0\n",
    "    state_coords = np.argwhere(states)\n",
    "    n_states = len(state_coords)\n",
    "\n",
    "    return np.random.rand(n_states)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:40.587236Z",
     "start_time": "2018-05-02T09:03:40.574264Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def draw_value_function(world_mat, value_function, fig=None):\n",
    "    if fig is None:\n",
    "        fig = plt.figure(figsize=tuple(reversed(np.array(world.shape) * 0.66)))\n",
    "\n",
    "    plt.clf()\n",
    "    value_function_mat = world_mat.copy()\n",
    "    states = world_mat != 0\n",
    "    state_coords = np.argwhere(states)\n",
    "\n",
    "    for state_coord, value in zip(state_coords, value_function):\n",
    "        value_function_mat[tuple(state_coord)] = value\n",
    "    plt.imshow(value_function_mat, cmap='hot')\n",
    "    plt.axis('off')\n",
    "    display.display(plt.gcf())\n",
    "    display.clear_output(wait=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:40.602885Z",
     "start_time": "2018-05-02T09:03:40.588933Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def value_iteration(value_function, reward_function, transition_model, gamma=0.9):\n",
    "    \"\"\"Performs a single iteration of the value iteration algorithm to update the value function towards the optimal\n",
    "    \n",
    "    `gamma` is a discount factor used here so that the infinite sum of reward does not explode\n",
    "    \"\"\"\n",
    "    next_state_values = reward_function + gamma * value_function\n",
    "    new_value_function = np.zeros_like(value_function)\n",
    "    for state in range(0, len(value_function)):\n",
    "        max_value = -1e6\n",
    "        for action in range(0, 4):\n",
    "            transition_probs = transition_model[state, action, :]\n",
    "            expected_value = (transition_probs * next_state_values).sum()\n",
    "            if expected_value > max_value:\n",
    "                max_value = expected_value\n",
    "        new_value_function[state] = max_value\n",
    "        \n",
    "    return new_value_function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:40.805682Z",
     "start_time": "2018-05-02T09:03:40.604866Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfEAAAFBCAYAAABn+JYIAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAABzBJREFUeJzt3D3LpVcZhmEfHWy2QlKn1ESCBKxsxCLED2xkYmsjOATy0Qj+AyvBUkwRC7ETRcE/YERikVKCQkIKi6QNKTaICMsumfU0r2Ze586Jx1E/LK5qn9zNPtZanwAAej45PQAA+GhEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAou78Lx69HIe/gQOAB3Bd67jpG5c4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AETdmR7wMLw2PeDkS3+YXnByd3rA7vL+9ILddf1kesKHXvnh9ILNC89NL9j97I3pBSdfmB5w8o/pASefWdMLNpfjmJ7wX3OJA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANA1J3pAQ/DZ6cHnDzy9PSC3dvTAz723p8e8IHHnptesHvnN9MLTr4xPWD3uXenF+ze/vL0gt2914/pCXkucQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiBJxAIgScQCIEnEAiDrWWrf+6OU4bv/RB3Bdf5uesHnveHJ6wuaP0wNOvjs94OSR6QH3eWd9enrC7s1/Ti/YfWp6wO7Nz08v2D2xfj49YfP4cW96wubd6QEn17WOm75xiQNAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQNSd6QEPxY+fnF6weXQ9Pz1hc/cHL09P2Fwfn16w++2L0wvu98z0gN0Tf59esLkcf52esHl1esDZd+5NL9i8td6anrC5HB+zH5//gEscAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACijrXWrT96OY7bf/QB/Gh6wMk3pwecfPHZ6QW7X/1uesHuhekB9/nL9ICTx9afpidsLsdXpydsruu96Qm7px6dXrD5+hvTC3Z/nh5wcl3ruOkblzgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AEQda61bf/RyHLf/6AO4vji94ORr0wNO7v50esHuXy9NL9h9f3rAh1775fSC3Vd+P71gd/n29ILdr6cHnHxresDJsX4xPWFzOb43PWFzXeu46RuXOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARIk4AESJOABEiTgARB1rrVt/9HIct/8oAPwfua513PSNSxwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKJEHACiRBwAokQcAKKOtdb0BgDgI3CJA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANAlIgDQJSIA0CUiANA1L8BTBppgPa0WDUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 617.76x380.16 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "transition_model = create_transition_model(world)\n",
    "reward_function = create_reward_function(world, goal_pos=(5, 10))\n",
    "value_function = create_random_value_function(world)\n",
    "draw_value_function(world, value_function)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:51.909828Z",
     "start_time": "2018-05-02T09:03:40.807114Z"
    },
    "scrolled": false,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAuEAAAHVCAYAAABfQyW0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAACpZJREFUeJzt3TFuFQcUhtG86HXuMMI0NEhu3Lgyq2ANFGmdDWQhbIosISuIRErXQ5EoLULiflfPPqcejX5pmk+3mdNxHL8AAACdX7cHAADASyPCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACB2nnjp1enkN5wAALxIT8dx+t4zLuEAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEDtvD7gkf2wPGPRqe8CQ6+0BQ37bHjDo6fX2giHvtwcMut0eMORue8CQ++0Bgx62Bwz5c3vAnKuP2wv2uIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBA7Lw94JK82h4w6Hp7wJCb7QH8uPfbA4bcbg8YdLc9YMj99oAhD9sDBr35sL1gxsOX7QUMcAkHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgNh5e8Alud4eMOhme8CQt9sD+HG32wOG3G0PGHS/PWDIw/aAIW8+bC8Y9Gl7wIw32wMmfdkesMYlHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABi5+0Bl+Rme8Cgt9sDhrzbHjDk6fX2gkF/bQ+Af1193F4w4+n4tD1h0OP2AH7Yl+0Ba1zCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAIHbeHnBJ/t4eAP9593V7wZyr7QHw7D1uDxj0eXvAkOf8zX7fHrDGJRwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYuftAZfkn+0B8AK8+7q9YMbV9gD43+ftAYMetwcMec7f7OVyCQcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAICYCAcAgJgIBwCAmAgHAIDY6TiOn/7Sq9Pp578UAAAuwNNxnL73jEs4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMROx3FsbwAAgBfFJRwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYt8AfPIrAHK0ACsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 936x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = plt.figure(figsize=tuple(reversed(world.shape)))\n",
    "for i in range(0, 25):\n",
    "    value_function = value_iteration(value_function, reward_function, transition_model)\n",
    "    draw_value_function(world, value_function, fig)\n",
    "    time.sleep(0.25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Optimal Policy\n",
    "\n",
    "Once optimal value function is found, finding optimal policy is trivial:\n",
    "\n",
    "<center>$ \\pi^*(s, a) = 1 : a = \\underset{a}{\\operatorname{argmax}} \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + V^*(s') ] $</center>\n",
    "\n",
    "_Pick action leading to maximum value_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:51.918153Z",
     "start_time": "2018-05-02T09:03:51.912589Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def determine_optimal_policy(world_mat, reward_function, value_function, gamma=0.9):\n",
    "    \"\"\"Creates a policy that picks actions that lead to states with the highest expected reward\"\"\"\n",
    "    next_state_values = reward_function + gamma * value_function\n",
    "    policy_mat = np.zeros((len(reward_function), 4))\n",
    "    for state in range(0, len(policy_mat)):\n",
    "        max_value = -1e6\n",
    "        best_action = -1\n",
    "        for action in range(0, 4):\n",
    "            transition_probs = transition_model[state, action, :]\n",
    "            expected_value = (transition_probs * next_state_values).sum()\n",
    "            if expected_value > max_value:\n",
    "                max_value = expected_value\n",
    "                best_action = action\n",
    "        policy_mat[state, best_action] = 1\n",
    "    \n",
    "    return lambda s: policy_mat[s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:56.356715Z",
     "start_time": "2018-05-02T09:03:51.920138Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAuEAAAHVCAYAAABfQyW0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEY5JREFUeJzt3WuMXWW9x/H/7kxb2lKmUEoLHqG0cCSoXAQt6jnHI+SQGJCaaCSoL0zF1Igm4CUNvqgJJphUeAEkNd5igk3EeMEbEgzkmGC4BD14GhShFstFmFba0pZOy3TafV4MzJ7dljY9TH8zs/fnkzSZZ82z1jy76Z75dmXNWo1ms1kAAEDOlPFeAAAAdBsRDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAsN6jcdBGo+ExnAAAdKVms9k43BxnwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwnrHewGTSbPZHO8lQFVVNRqN8V7CUeN9BtA9Ovnn2eE4Ew4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJ6x3sBwJFrNpvjvQToeI1GY7yXcFT4/gETgzPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGG9470AAICJbvuGDfXSk0/WQH9/DQ0M1JTe3prW11ezTzutTnjrW2vqrFnjvUQmGREOAHAQA/399cSaNfX03XfXQH//685r9PbW/He9q874yEfqzZdeWo1GI7hKJqtGs9kc+4M2GmN/0AngaPxdATAxdWpI+Vn2Otaurbrwwqo9e6qqat+0aXXX4sW14wj/HSxYuLD+8/e/rynbtw9vmDKl6oEHqpYsGesVd4QOfp8d9oW5JhwA4JxzqlasGBlOGRysdz7zTNuUY+bOrXkXXFCnfuADdcr73lfHn3VWNXp62uacef/9rQCvqrr2WgHOQTkTfgScPQDoHh18hm68lzBh7dm6tXYvXFizR0X0QyefXLuuuKLOXrasTrrwwmpMaT9/uXvz5trwm9/UY6tX14Jnn61/+8c/WsdbsKCmrl9fNXNm7DVMNh38PjvsCxPhR8A3LoDu0cFxMN5LmLAevP762n7HHfVfGzaMXCqwd9as6lm3rurkkw+5766//rV6zj+/pu3eXVVVzar63Zln1jvuvrv6Fi8+ugufxDr4feZyFACAw3nmnnvq77/8ZW2eObOePOGEke09O3dWXXPNYfefccMNIwFeVbV+zpx6YerUemDFitr36nXmMJoIBwC62r6hofqfVatGxv970kn1yvHHtybceWfVj3/8+gf41a+qfvjDkeHA1Kn16Pz5VVW19fHH66mf/3zM18zkJ8IBgK727L33tt2CcOq8edVz++3tkz7/+aotWw7cedu2qs98pm3TP5cvrz2jfmHziTVrxnS9dAYRDgB0tXWjzmJXVS3+8Ier9/LLqz71qdbGjRurrrvuwJ2/+MWq559vja+6qk6+8cbqmT59ZNO2v/2tNj788Fgvm0lOhAMAXWtoYKD++ac/tW07fenS4Q9uvrnqlFNan7j99qp77mmN77236nvfa41PPLHq1ltr2uzZ9S8XX9x2zBcefHCsl84kJ8IBgK714tq11RwaGhnPXLCgjlu4cHjQ11e1enX7DsuXV738ctXOnVWf/nT75269dTjEq2r+RRe1f51HHx3rpTPJeWw9ANC1Nq9d2zY+4eyz2ycsXVp15ZVVP/rR8Pjpp6uuv76q0ajasKE174MfrLrqqtc9zubHHqvmvn0H3Gec7iXCAYCuNbBxY9v4uIPd0/u224YvPdm8eXi8/9nxvr6qb36zfdMZZ7SN9+7eXYPbt9f0OXPe8JrpDP47BgB0rcHRj5ivqmnHHXfgpHnzqm65pTXet2/4z2u+8Y2qN72pbZeeadPafjmzquqVbdve8HrpHCIcAOha+0f41GOPPfjEj3+86rLLDtx+8cUHXhv+OscaFOGMIsIBgO7VbLYND/ms8YM9+fJQT9Ps0EeyMzZEOADQtfa//GTw5ZcPPvH736/67W8P3L5yZdXg4EF32bNjR/vX6uv7f62RziTCAYCutX8Y7395SlVV9fcPP5TnYP7856qvf/2AzXsHB2vvK6+0f62DXW9O1xLhAEDXmjFvXtt4+1NPHTjpmmuqtm5tja+8suqYY1rjG2+sevzxtl22rV/fNu6ZPl2E00aEAwBd68Rzz20bb/nLX9on/OQnVT/7WWu8ePHwpSlf/Wpr2+Bg1dVXt90xZet+xznhbW+rKT09Y7ZuJj8RDgB0rbnnnFONUXE88MILtf21h/Bs2VL1uc+1JjcaVd/5TtWMGVVf+lLVeee1PvfAA233D+9/6KG2rzPv/POPxvKZxEQ4ANC1ps6adcDZ8L//4hfDH1x7bdXoh/lcfXXV+98//HFvb9V3v1s1+uz2V75S9eyzNbhjRz13331tx1zw7ncfjeUziYlwAKCrnTnqcfNVVet/+tMauvPOqh/8oLXxlFOGH8oz2gUXVF13XWu8Y0fVZz9b6+64o+2XMvsWL64FF110NJbOJCbCAYCuduqll9aM+fNHxkObNtXeZcvaJ61ePfx4+v3dcMPwdeKv+fWva/t+d0v51098YiyXS4cQ4QBAV5vS21vnj7oF4XmbNtX0l15qTfjoR6uWLj34zjNmVH3rW22bznvmmZq2d29VVc15y1tq0Yc+NOZrZvIT4QBA11t42WW18PLLa97OnXXmqNsR7p09u+q22w698yWX1NDHPjYynLF3b72jv796pk+v96xaVT3Tph2tZTOJiXAAgKp655e/XO958cW2R9c/PHt2/ffKlbXxkUeqOeoWhK/ZvWVLPbFmTd315JO1a9QvaS7atq3+44oras4ZZwRWzmTUaDabY3/QRmPsDzoBHI2/KwAmpkajcfhJk5CfZYewYkXVqlUjw+dnzarfnXbayPiYuXPruEWLasaJJ9aegYHatWlTvbRuXTWHhqqq6s3bt9e/P/dc63inn1712GNVM2fGXsJk08Hvs8O+MBF+BHzjAugeHRwH472EiemPf6xasqTq1Wu5906fXnctWlQvH+G/g4u3bKkF/f2tDV/4QtXNN4/lSjtKB7/PDvvCXI4CAHS3PXuqli0bCfCqqp6bbqpL7ruvzvrkJ2vGSScdcvdGT0/NX7Kk3nvTTTX/kUfa76Jyyy1Vf/jD0Vo5k5gz4UfA2QOA7tHBZ+jGewkTz9e+VrVyZWv83vdW3X//8BMyX7Xtqadq27p1NdDfX0O7dlWjp6em9/XVsaeeWnPf/vaaOmtWa/9vf7tq+fLW+Nxzh0O8tzfwYiaXDn6fuRxlLPnGBdA9OjgOxnsJMKKD32cuRwEAgIlGhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCesd7AZNJo9EY7yUAwBviZxlMDM6EAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACEiXAAAAgT4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACENZrN5nivAQAAuooz4QAAECbCAQAgTIQDAECYCAcAgDARDgAAYSIcAADCRDgAAISJcAAACBPhAAAQJsIBACBMhAMAQJgIBwCAMBEOAABhIhwAAMJEOAAAhIlwAAAIE+EAABAmwgEAIEyEAwBAmAgHAIAwEQ4AAGEiHAAAwkQ4AACE/R+/SGSkzr5gyQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 936x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "policy = determine_optimal_policy(world, reward_function, value_function)\n",
    "coco_pos = [np.random.choice(np.arange(1, 6)), np.random.choice(np.arange(1, 3))]\n",
    "run_policy(world, coco_pos, goal_pos, policy, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "# Adding Negative Reinforcement and Noise\n",
    "The reward function can have more complex designs, and with noise negative reward is spread to surrounding states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:03:56.369280Z",
     "start_time": "2018-05-02T09:03:56.358091Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "transition_model = create_transition_model(world, noise=0.15)\n",
    "reward_function = create_reward_function(world, goal_pos=(5, 10), trap_pos=(2, 6))\n",
    "value_function = create_random_value_function(world)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:04:07.435036Z",
     "start_time": "2018-05-02T09:03:56.370929Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAuEAAAHVCAYAAABfQyW0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAACsxJREFUeJzt3TGKXmUYhuE5ZiKYwUJRtEkvirUIQrDILmxs3IELcQFpXIJ2bsPKHSgWFmFQFHPsbENg3vvNzFxXffh4fmbgv8/X/Md5nhcAAEDnje0BAABw34hwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIhdThx6dRx+hhMAgHvp+jyPlz3jJhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYpfbA26Tq+0Bg7yN3S7PtwcM+nB7wJAPtgcM+mp7wJAn2wOGfPJoe8Ggx9sDZvz5y/aCOe9tD1ikvQAAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACB2uT3gNnm4PYBX5i3z9vl1e8CQz7cHDPpre8CQj7YHTPlye8CgT7cHzHjr9+0Fg55tD9ijUQAAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgdrk9gNfDw+0BQx5sD+CVfbY9YMhd/l98sj1gyIMvthcM+Xp7wKCn2wOG/Lw9YNCz7QF73IQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQEyEAwBATIQDAEBMhAMAQOw4z/PGD706jps/9DXw7vaAQW9uDxjyaHvAkLe3Bwx6f3vAkMfbAwZ9vD1gyLfbA4Zcn0+3Jwz6fnvAkG+2B4y5On7cnjDi+jyPlz3jJhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABiIhwAAGIiHAAAYiIcAABil9sDYNKL7QFD/tkeMOj59oAhv20PgP/9tD1g0HfbA4b8sD1g0LE9YI2bcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIiXAAAIiJcAAAiIlwAACIXW4PuE1ebA8Y9O/2gCF/bw8Ycpffnh9sDxhyVz/XxcXFxfX2AF7NH8f2gjnvPN9eMOMu/83usbv8XQ4AAK8lEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAMREOAAAxEQ4AADERDgAAseM8zxs/9Oo4bv5QAAC4Ba7P83jZM27CAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACAmwgEAICbCAQAgJsIBACB2nOe5vQEAAO4VN+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEBPhAAAQE+EAABAT4QAAEPsP+Ek4bfxkevAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 936x576 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = plt.figure(figsize=tuple(reversed(world.shape)))\n",
    "for i in range(0, 25):\n",
    "    value_function = value_iteration(value_function, reward_function, transition_model)\n",
    "    draw_value_function(world, value_function, fig)\n",
    "    time.sleep(0.25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Solved! Or..?\n",
    "* Infinite sum of reward - 'discount' factor $0 \\le \\gamma \\le 1$ tradiing off long term and short term reward\n",
    "\n",
    "    <center>$ \\sum_a \\pi(s, a) \\sum_{s'} [ T_{s, a}^{s'} \\cdot r_{s,a}^{s'} + \\color{red}{\\gamma} V(s') ]$ </center>\n",
    "    \n",
    "\n",
    "* Reward function design - narrow sighted greed, unwanted effects\n",
    "\n",
    "\n",
    "* **This is not Reinforcement Learning!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Real Reinforcement Learning\n",
    "\n",
    "Coco knows too much!\n",
    "\n",
    "* Do you always know the consequences of your actions? $T_{s,a}^{s'}$ unknown!\n",
    "* What are the good outcomes? $R(s, a, s')$ unknown\n",
    "\n",
    "Options:\n",
    "1. Learn models from experience at the same time\n",
    "2. Model free learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Reinforcement learning models learn through trial and error: the agent performs an action and gains a single sample of 'experience' $<s, a, s' r>$. Such samples give sparse bits of information about the transition model and reward function, that the agent can use to learn how to maximise his expected reward."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Temporal Difference (TD) Learning: No More Models\n",
    "\n",
    "Idea: a single time step already gives some information about value.\n",
    "\n",
    "1. Start with random value function and some policy\n",
    "2. Observe current state $s$\n",
    "3. Perform action $a$ based on policy\n",
    "4. Observe new state $s$ and immediate reward $r$\n",
    "5. Update value of previous state: $V(s) \\leftarrow V(s) + \\alpha [r + \\gamma V(s') - V(s)]$\n",
    "6. Goto 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Problem: learns value of current policy, not optimal policy; '_On-Policy_'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Q-Learning: Off-Policy Learning\n",
    "\n",
    "Idea: assign value to state-action pair: $Q(s, a)$\n",
    "\n",
    "1. Start with random Q-value function\n",
    "2. Observe current state $s$\n",
    "3. Perform action $a$ based on policy _derived from Q_\n",
    "4. Observe new state $s$ and immediate reward $r$\n",
    "5. Update value of previous state-action: $Q(s, a) \\leftarrow Q(s, a) + \\alpha [r + \\gamma \\max_a' Q(s', a') - Q(s, a)]$\n",
    "6. Goto 2\n",
    "\n",
    "Can learn optimal value + policy, even when just acting randomly!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# State of the Art RL! ... in 1989\n",
    "\n",
    "Can't really deal with:\n",
    "* Huge spaces (camera feed, Atari screen, Go board, ...)\n",
    "* Continuous spaces (steering angles, joint motor angles, ...)\n",
    "\n",
    "Needed: _Function approximation_:\n",
    "* Learn parameters $\\theta$ of some function $f_\\theta(s, a)$ to approximate $Q(s,a)$\n",
    "* Linear regression, (deep) neural network, ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Everything so far assumed all values can be kept in nice tables. Very high dimensional spaces will make those blow up, and it will not be likely that all states will be visited. Continuous actions make it even impossible to use tables, and at least some sort of function approximation is needed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Continuous actions\n",
    "So, function approximation! But...\n",
    "\n",
    "* Not guaranteed to converge (but let's forget about that for now...)\n",
    "* Find best action? Search action space? Evaluate $Q(s,a)$ many times..\n",
    "\n",
    "Split learner into two parts:\n",
    "1. Critic - learns value function\n",
    "2. Actor - learns best actions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Actor-Critic Methods\n",
    "\n",
    "<center><img src=\"figs/actorcritic.png\" alt=\"Actor-Critic Model\"></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The critic learns a value function like before. The actor however learns the policy separately from this value function, based on the TD (value prediction) error: if an action turned out to be more valuable than initially thought, its probability should be increased. Having a separate actor prevents having to evaluate the value function continously, and you can ship the actor separate from the value function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Deep Q Learning\n",
    "\n",
    "\n",
    "<center><img src=\"figs/atarigames.png\" alt=\"Atari Games\" width=\"600\"></center>\n",
    "\n",
    "\n",
    "* DeepMind - [Nature, February 2015](http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html)\n",
    "* Learned to play Atari games purely from pixel input\n",
    "* Use CNN to learn Q-value\n",
    "* Limited amount of discreet actions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Catastrophic Forgetting\n",
    "\n",
    "Learning in one area can undo learning in another. Stability trick: _experience replay_\n",
    "\n",
    "<img src=\"figs/experiencememory.png\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "When an agent is activally learning, it will gather many samples in the same area of state space. Learning from these samples will make the value function and policy more adapt to this area, but doing so changes parameters of the functions that affect all areas. This could undo previously learned behaviour. Using experience replay, the agent stores all his experiences, and trains on random samples from this memory, rather than on the latest experience. This ensures more variance, and alleviates catastrophic forgetting and behaviour divergence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Learning to Drive?\n",
    "\n",
    "DeepMind - [ICLR 2016](https://arxiv.org/abs/1509.02971), Deep Actor-Critic Method\n",
    "\n",
    "<img src=\"figs/driving.png\" width=\"400\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This method uses a deep network both for value function and policy. This allows it to learn problems with continuous actions, such as pole balancing, bipedal walking, and: driving around a simulated race course."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Simulation is Cool, but...\n",
    "\n",
    "Results difficult to transfer to real world:\n",
    "* Use racing game policy in the City?\n",
    "* Simulation never perfect: overfitting\n",
    "* 'Crash into wall' reinforcement not useful in real car\n",
    "* Tesla, Uber, Nvidia, Google are on it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src=\"figs/crashed-model-s.jpg\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Overfitting can happen both on the similation artifacts, and the chosen reward function. Currently the main approach is to learn from example human behaviour: cloning a human policy, which boils down to supervised learning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Making it more Human: Hierarchy\n",
    "\n",
    "<table style=\"border: 0px;\"><tr style=\"border: 0px;\">\n",
    "    <td style=\"border: 0px; padding: 40px;\"><img src=\"figs/hierarchy.png\" alt=\"Hierarchy\" style=\"width: 500px;\"/></td>\n",
    "    <td style=\"border: 0px; padding: 40px\"><img src=\"figs/fmri.jpg\" alt=\"fMRI scan\" style=\"width: 300px;\"/></td>\n",
    "</tr></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Humans don't just think in basic actions like 'move joint to angle', we plan at different layers of abstraction. At each level we run policies that get finer moving down the hierarchy. In the field of RL there has been much work on 'Hierarchical Reinforcement Learning', most notibly using the 'Options' framework. In the last decade, Botvinick and Barto have mapped this theory to actual structures in the human brain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Making it more Human: Back to Models\n",
    "\n",
    "<img src=\"figs/modelbased.png\">\n",
    "\n",
    "[Cambridge + Google Brain + DeepMind, 2016](https://arxiv.org/pdf/1603.00748.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Resources\n",
    "\n",
    "* ['The Book'](https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html) - Reinforcement Learning, Sutton & Barto\n",
    "* [Demystifying Deep Reinforcement Learning](https://www.nervanasys.com/demystifying-deep-reinforcement-learning/)\n",
    "* [Berkeley Deep RL Course](http://rll.berkeley.edu/deeprlcourse/)\n",
    "* [Reinforcement Learning: Top 10 Breakthrough Technologies](https://www.technologyreview.com/s/603501/10-breakthrough-technologies-2017-reinforcement-learning/) - As judged by MIT Technology Review"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Deep Q-Network\n",
    "\n",
    "<img src=\"figs/deepqnetwork.png\" width=\"600\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The network used to approximae the Q-function is a CNN with two convolution layers and two fully connected layers, so not very deep.\n",
    "\n",
    "Also, there are no pooling layers. Pooling are useful to increase spatial invariance: if you want to recognise a cat it should not matter where in the image the cat is. In video games on the other hand the accurate location of objects on the screen is very important.\n",
    "\n",
    "Rather than using the state-action pair as input and calculating a single Q value as output, the network is trained to output the value of all actions given a state directly, so that only one feedforward pass is needed to find the best action."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Stability Trick 2: Fixed Target Q-Network\n",
    "\n",
    "* Fix old network with parameters $\\theta^-$ and calculate target with those:\n",
    "\n",
    "    $ r + \\max_{a'} Q_{\\color{red}{\\theta^-}}(s', a') - Q_{\\color{red}{\\theta}}(s, a)$\n",
    "\n",
    "\n",
    "* Periodically update: $\\theta^- \\leftarrow \\theta$\n",
    "\n",
    "\n",
    "* Breaks correlation network and target, avoids oscillations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stability Trick 3: Clip Reward/Value\n",
    "\n",
    "* Clip reward to $[-1, +1]$\n",
    "\n",
    "\n",
    "* Avoid huge overestimation of Q-value\n",
    "\n",
    "\n",
    "* Learning gradients well-conditioned\n",
    "\n",
    "\n",
    "* Problem: no difference small/large rewards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# RL Drifting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:04:07.438768Z",
     "start_time": "2018-05-02T09:04:07.436536Z"
    },
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-05-02T09:04:07.599727Z",
     "start_time": "2018-05-02T09:04:07.440637Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkzODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQEDEQH/xAAbAAABBQEBAAAAAAAAAAAAAAAAAQIDBAUGB//EAEcQAAIBAwICBQoEAggEBgMAAAABAgMEEQUhEjEGQVFhkhMWIjJTcYGR0dIUQlKhFUMXIzNUYoLB4Qckk7E0c6KywvE1RHL/xAAYAQEBAQEBAAAAAAAAAAAAAAAAAQIDBP/EACMRAQEAAwACAgIDAQEAAAAAAAABAhESITETQQNRIjJhQhT/2gAMAwEAAhEDEQA/APPwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHKDfWh3kZdqAjAnp2s6nKUfiWKWk1qrxGrRT72/oTa81QAv1NJr0+c6T9zf0Kztpp4zEpqoQLELOpPk4/MnhpFxPlOn839CbNVQA1P4Fde0o/N/QVaBdPlUo+J/QnUOaygNmPRq8ktqtv4n9Bk+j93T51KHwk/oOoc1kgXVplTyqpyrUYt9bbx/2L9HovdVcYu7SKfW5S/0iXZqsMDqqHQPUbiPFSvbCS/8AMn9ol10B1S1t51p3FnKMVl8M5Z/9pTVcsBq+b917Sh4n9B3m5evlKi/dJ/QnUNVkAa0ujt/HmofN/Qiei3cefAvn9BuGqzgNKGi3EudSlH38X0Nuj/w91etRhVjcWSU1lKU55/8AaNw05IDsP6ONY/vNj45/aH9HGsf3mx8c/tKjjwOnuegup2zSncWbb/TOX2lOp0XvaXrVbf4Sl9DPUi6rEA0paLcRe9Sj839AholzN7TpfN/QvUNVmgar0C6X8yj839BP4Dde0o/N/QnUNVlgbNPoze1FmNWh4n9CaPRHUJcqtt4pfQdQ1WABvPolfr+bbeKX0I5dGb6OfToPHZJ/QdQ1WKBpvQrtL1qT9zf0NKw6D6tf0/KU5W9OHVKpKSz7ti7hpzQHYf0cax/ebHxz+0P6ONY/vNj45/aVHHgdbV/4e6rRg5VLuwil1upP7TMn0Zu4Sa8vbPvUpb/sS2RdWsUDXfR27X82h4n9Bvm/dZ/tKPif0J1DmsoDYXRu9f8AMoeJ/QXzavPa0PE/oO8f2vNYwGs+j12udWh4n9CN6Jcp48pRfub+g7x/ZzWaBprQrp/npfN/QVaBdSeFOi3739B1E5rLA6e16B6zdR4l5ClF9dSUl/pks/0cax/ebHxz+01tHHgde/8Ahzq6WXc2P/Un9pnXfRW4tMqd/YzkuqnOT/8AiF0wQNWn0fvaj9F02u3L+hK+jF6udSh4n9DPUXmsUDXl0du486lDxP6DHoV0vz0fm/oOonNZYGn/AAK6/XS+b+gv8BuvaUfm/oOoc1lgX6uk1aXr1qCfZxP6Ea06s+Thj4/Qu4c0++0660+s6dzScH29TIIycTtaGqOrBW2sW8bmi9lUS3RlatoNOFOV1ptVVKGd4P1kbsb5/TDhW4ZKS+JcbksVab37DNksPlgu6fLjbpfm5x7znlPtv8dl/jksTuPKQz1lR88k9Wm1mUV70Q4Ta7BLtnPG43VTW63NOguRXt6UWlhmhRoNGcquMTRXo7oTgTfNr3EvC0uRG3hnNpLTjKOym37xKtOpKL9GL9z3GQqNPG3zLKqLh3TAwr2jKW86eV380RWlR0ZcUZyx2ZOidKlWi+KPxwQfwqDfoSx7zUzZ0hoXflZbtprrWzL8a9SNGUIVqnBJYlHOUyOlYqm/SSx2omdFLHDzJctrpHGimTwo4SHQTS3jhEsJLK2MU0EsBhPmkTcKYcHcRdG2lpTuLqEHBYzl7dR1iWEkcxRrSt6nHBJvvL9PWmtqlP4xZ1wyk9sZY79NkbKSjFt9RnfxqhjPBPPZgrXuqKtQcKSa4ueTpc4zMKqXlx5WtKedur3GTdPOS3J5yUbnkef35bZVZZY6jNRwhtZ8OWV41cSOmvA0XUjnkSxpqTTyUI1M4L9FtxRnQ0LantzLtOOFsynbZaLsDNWI6ieWVppvCWWy7NZIE5UqinHGV2oRWjY6DTnBVLuL3W0E8fM3KVNUqcacctRWFl5ZhU9elCH9bSy1+ljl0ig458lJPsO2PMc7ha3TK1rVlp9HNOcPK9UGs5M2vr9ecWoRUP3MK7n5WTnJuUnzbZbl+lmGvZb7Xa97PNVuKXKK5FN3LeN8tvkivVzyxsR0uOEnwSks88PCZnW/LTRhTqzlvGSXesFqlSjGHrRb7nkzoTUVicm+5cieNeOPW+COd2eVxyxtHdkNSe+M79iGRnKo8LZGla6NdXCUoUnwv80tiSLtlSUpc9kN4YxOlh0ZrynipVgo9q3J5dFrbycs16nFjZ7JI1xWeo5CVTBvdH9U02hHFZQp1l+eXX8Tm9UtqlpdzoSqKXC+aKsKMpM1jNeR6HW6VaZSlwxqSqPtjHYoXHS+U/RsrZt/qn9Dl6NrHnJNmjQpKMU8YRq5X6JjE1a61DUP/E3Eowf5I7IWjZ0ob8PE+1j4RLEKbZzt20ZjsEcG+ofUrUKPrzWexbshqXVRr+qoqEf11nj9uZFRzodbyUrirRo7TlFPqS3fyJavFX2nVq1f8NJcEfnzCjptxL+xoQpJ9aWX8y+EUKletP8As6DS/VUeP2IZcc9qteT/AMNNY/3N+noPXXm5PsLVPTaFFejTXxL1E05ijZzf9jb4/wAUiaOmVpb1J/BHSujFdQyVLJOhZ1bo3CpGpVspeTqvlD8rOTqz4MQuacqLktmuTPQ9QruhaVJwXpqL4U+t9RwHSyrGPkaEHlU4pZfPPWeqp9bZGo2eUqlNxku4zIuVKaktmnlE8a9Sn1vAScau/JmWGjxxrUo3EOvaa7GQVqPBipDeD5rsKcHUot8LfC+aNC3rJrti9mjlf43cevCz8uPOXtasoRqRWJcjVo0pLkYUnOxqxqw9Kk/+xvWlaFakqtOWYvn3Et35cebjdVJOL60QyRNUnhcyvKRnYcsN9RYSWF1FOMtybymy3INGzlCFam3uuJZydQrO1nHLoU8vr4UcVCry3O1sLiNe0pzTWXFZ95vCT7Yz9Ip6TaS5QcfcyCro9JLMZy+OGaokt4s3cJWJlXLulBNxa5MR0odTfzFvn5K8qR78kPlThZp3TKD6psXE1+ZfIhVbHWWtN/5i8jHqj6TCbQyUuxEfC+tHWcEcY4V8hjt6L50qfhR0+OsduXSS5ivh5Jm/e0banQlN0oLC6lgwNn1HPLHlqXZjSRSuFzL0op8tijcxwnuxCsa8e7M9P0y7dJ8Ty2U4x9I7Y+maswk1g07aT4UZce40bbPCjOTUa9tll2Oc8yjaZNCBzqwNFeoi3LkUripw52IqtUeMld1YoiuLpp4SKca7k9zQuyq55EE3JvqBcsvYjqVsLYIbNP8ANLPdggk+547AnXI4XFN1EqsuGPW0sm5KaPjGT2hHBv6Z0YvLnhqV8W9N77838Da0qvodnZwq0qtGLa3nOSci/V1vTqNPjld08PdcLzn5G5j+2LaWx0azsknCnxz/AFz3ZfzjmYNbpTa4xbU51Zd6witUu7m+inVlwQfKMeRdyJMbfbVvdbtLTMU3Vqfphv8Auc3qOtahd5jB/h6b6oc/mXIWGHum13EVe2jjCiYudrcxkYkLSLeZZk3zJVTjCeYQ+ZoKjCPNognOmtqa4n3Ikul9IIcSTSWE+4khVhBYnPPctyCanUeG/gtyzbaXWqerDhXayXIKrqWP6umkv1SFzVrPEpzn/hjsjUttFjHDrSbZp0bWjRWIQS+Bna6rCt9OuJr0IRpJ9i3+Zdo6JTT4q0nJ9+5rYFwF0rU7KhTXo01ntZLwJdRIINCCdMhnBItvdEM4kFSUSKSLMokckRmqV50psatOn5KtxNvO65HLarVhqFzKquszqlvCfq+iyL+vt32xPRf5eY6S8eM54PlCVPaUeKI128ZripS37CalcwqLEtmLKjvxUnhmerPa/HjfOPmKr46bxNbElKSUuKD96JVUT9CqsPtElarnTfPqNdT7Y+Ozzg0FdRq2XkZU098qXWitTq1tPn5Si8x649TIaaqU3ui1TrQltJYOerj69O3WP5ZrLxWpQvqF5T4qcsS/NB80EsY5kOn6Pa3jlJXsbaovVWOYSoVaVSVKrNOceUo8pDU+nnuNl1TuvmOctyrJTX5v3GqpNS5saGhGWGWaVxVpx9CpOPuk0ZsKrxvn5FiFZYINilrd7CKj5XiS65LJKtfvMYzTfwMPjiuti+Wp59b9i9U0vVripcVHUqNOT7BvG+wqqvFDvLp9vyM0T+UaNTRL22tpVHXnwyljGUYiqpvmDzzwJ4R3VK8t6yzTrQl7mP8AxFHOPKwyv8R585NEMqz4mdfkZ4jrdb1GlJRo0qkZb+lh8jLVZY2MmlUyy1CosHLK9XbSzKtUXUmZt5dVc4UYrt3LMqiSZmXUo5/3EVUrVHJ7kMX6QVZbbIhp8Up4jFt9iO0jFXqZo2q9FGbCNRNRdOal2YNOyp1ZJqNKbxzwuRjJY1LXmaMFyMu2bUsNYNKDOdWJ5LYoXcNmXuJcOStcbpkac3eZhLYoRq8MnvjvNa/pSeWk8dpj1LOpKe0ZPPcdYq1CvHG7+YN+Vko005SfKMVlsv6R0Xq3MlO8k6NPnwr15fT4na2Fla2FFUrakqa68Ld+9jmJbp5w7G7qV/IQtazqvfg4GngfHozqlRVJzoeRjBZcqslFHpdWtCjTc5NRS5tnIa7rlC5ozpwo1K7lsnJ4jH3I1tnbj405KWH1djyXaEORBCFRPeLRdto8i30zGvpVOKqbo6Wl5FQ5LK6jnLSMeJLiwb1pTpNJN5ZxrpEruKUF6P1RmXUq1aTVOGz60bPk4c+FfEc0scg05mNlXqPDjt38vkXaOkZS8rJ47FyNRxxIkS2G00q0rKlSXowRYjDHcPwKRQkKAFCgAFQCABAhHIkGyIqvKJHKJO+ZG0EebJjk1yfIzYXUo89yzTuYT68M6XCx3x/Njl4qWpZwqbw2fcQZrW7w94lmM+xj1JSeJR4sjr6qX8X3hUUKtKusPmSztK9CfDlxf6ZEcqKg1UhH04TTWes0ukt6r3VFXtVJQdOKaaxuXXjxWer/ANROtJrLQv4hUmk3PEYY5rOMmc0/zcKNPVtVjdaZY2dtxRhSgvKZ65Y/+zGk6VJJ1aj9yJZN+F6sm7Fm3pTr1VToKdSo+UYLc0b3SbzTrJ3VylTivyue5pWOu6Tpunt6XbzrVlHM5OOHnvZymp6vfa1X4rmrw009orkjp8c15cb+a/pq2VpWuaSrVa1OhRfJyeW/gJeX1rYNRoOldfqdSP8A2MGVdxpqnCUml1tldvLy92OY53O1uLVvxD/8HSS/wvBoWcFdSUIQlTk+XE9vmcqnjkWaF9cUJJ06slgXHabrq6+h38GsW85d8d/+xVqaVfRlwytqvhZPpHTSrb4p3kHUp9q5o7ey1C2v7WFxb1FKnPl9CfH+l6rzd0ZU5OMk4tc09iSGUtmanSy4tfx8XSrQlVxw1Ip7rHaYqrLHMxZY1tZhOXFulgn432FOnPMi3F55mQ9Sb62VaspcWOJluMfeQyo5nnLMiFRqdWPkSQVfsRPTpY6yXGGWeaW6VmppekkQyjSafFFNmi3Ta3WGRPyK6lnr3PZhhjPcebPPL6Z0LL8VWVKhT4pSOu0DQY6TOpUk41JTS3xyOaeoVbSTlbTUG+wf53ajTXDinJ/qkjWeOOmvx2/bv8weG4rbkQ1r62oZ8pOEZYzjO5wEulGqzi4+Wis9agskVO5rXNZ1K03KcubOGVk9Ouo6W6vXf1uXDTj6q6xY2zazGbTM6zbzzNq35I89taiKNOpFYms95FWdSk8xSa7zVcMw5FWtTWGsE21pz93e1nlNxT6m1lox6le5U+OVWo2nnOeZuXtGKecGXcSjjGDUyWVqWHSaVKKVaMYx6oU44+LZaqdJ4RafE3/hhHb5s5RyXUhHJs6JtvXnSTyvq26m+2pLP7cjIlqLcs+Sim/kV/Jt9o+latvkWeGLdpHdZ6s+8s0KintjC7ghZ9uxdt7WEeozcoJbaKytjctZcKTSM+lTisYRoUn6KMWtRe48oRy2I09gyRtJkeuRCpEkHkB4ABQoCAAoALldQQggAFAxjm+wa2RDWhjQ6TGsI8cAQQ9bzpI1px5MuW1zKU8da3RQJ7O3qXd1ChS2lN4ySyVvHPLH1WpYX9vO5pRuXilGeZd47VNWo3N9Vq044i3hLHUY1WDoVJ028yjJpkZniOn/AKM12d/J+qsBZWtS/uMN4gt5yfUiki3b1qlKjOMZcMJc+8sknpzyzyy/tV+9voUqX4Ozjw016z65GbxPtGt9YimoyTxnD5MrO0rpVFTVRxag3jJG+R09KVDUtMcYJJNYx+lnNVIOnUlCSw4vDJLtbCQn1MmWGVnzHwlhlRYUHL1SS3vK1tmMZyjFvOE8Yfb7yKE8NNEtWCrQ44+sua7SempN+ld1JOtKU5Nyby2+ss0qj7SrTTm+FPfqHwquMuFoWMtmyblNGvShkx9NkpSRu0lk45e24ljT25FecPTZejH0SvUXpHNolOA5wWeSJaUck/koyW/MQZ1aVKMd4J+8oTuqKyuFfBGrc20XFmNcW8Yy9E9X48Ovtyzz5VK1xTnL0YNMqze/q4LNSmkUbiTisZOl/Hpmfl6TQh6XMvW0dzLt5vPM1LebXecMo6Rq2jaZs2tTkYNCpiRo05ySWGcq3G9CeY8xlXDRRp15cIkrpp7sw1tVv4ZTMK4pbcjdua0ZRzlGbVnS/UjUZZKoSb5FmnacslqMYvdcixCGxq5VFT8NGK5D4U8dRalBYEUEiBqjgnpLYTg2ETlB+rsFW6ZcpeqZ0akvgW7ecsbhZVyMtg4lnmQ5EZFWYyT2JYPcqwmsk0ZBVhCjIscFOAQAFAQMAKwEygbCbJzE5g5DJVIx5ySCbD7xrIKl5Qhzqx+ZVqapQjybl7hpK8tEFYh63AIs2V3OyuFWppOaTxkrjQHSk5ycpbtvLGgT2U6VK5hUrU/KQi8uL6wIltt2kspZSS2S5El7WhcXDqQpqmpPOF1FfOQHLMuQqozb5D6awiTymORFT6ZOrZ3Cl+SW0kP1OEa115WjupLf3leEnJizlh7Mfe1V6lKcecWMNGhUgv7TLIrinSnLMNmVNIKcuompzcZZRX4XB780Sp5RCXR1xHgnGrDk/wBmQTl/WcXbuW44nB05cny7ilJNZi+aEXL9t7TK8G4t4TOktqtPHJYPPqc1F5UpRfcWY3taPq16i+JnLHZLp385wj17FC5rxhJ+kzklql6uVzNrsZLHVLz80uL3xMfG106WjqOXiGG+xstUtRqP0XSjn3s5SOq3EXlQp574lq31ivUlhwpr3I9OGP4dfyht07qOay6Sfxf0GRoUp86ZQoXdWSWZRXxNClJPdy/cmXE/oa37V7i2prOIxRg6lRjwvDidDcOO/NmJfuDjLZoxupZGHSqcLa7DQoVXw5M70OJ7/sTwqxhsm/iZqTw1aVX016Rr0KmYrfJzNK5jx7G7ZVeKK2OWU022qLyuQ2slgdb+ryH1YZRzVjXUkk9zFr3Dg24m/d0W08YMG8tpvOMHXBKilqdSEG4c0RR1y7jycfkQytauOp/EidrUjzizrqMW1beu3Te+C9Z6tKo8Smk+xmDOnKL3TXwFobVULjCZV2lG8hKO73JVWhLKTMS1liKLtOfZzONjptejUXItUKqxjJj1K1SMspE9GpNtZZNDYjUTXMRt9TKlKbT3ZZ41jOSVUkc55limu1lN1oxGu/4fVg2TRtrRkP4l2mD+PuJP0KbXwF8pfVOvh+I0dN5VIjZXFKHrTiviYn4W5qevVZJHS2/Wc38R4NtCepW0OdTPuRXnrVFerCUhIaVT64p+9k0dPpx6or3Ibh5U5axVl/Z0COV9qFT1Y8PwNWNrTQ9UYLqG0YjV/U9ao/mJ+BrT9eobvk4rkl8hHhF3TTF/hmebkx0dNgvyfM1pYI2TdHkIIAR63EogCgJgUAAXmKuYgICWOZPCHyjw7LmR03wnRdH9E/G/81dbUY8l+pkt0sU9K0ivfyyvQpLnNnSUdFsbdYVPyku2W5dnOja0vy06cTCu+k1KnNxoR4u85buXpvUjYVtSUcRoRx//ACZt9o9CtmUI+Sn3FKn0kqSfPBq2mr0rnEaqW/WTVh4cpd21ShN06q36n2lenywzs9U0+FxQ23X5Zdhx9aDozlGaxKLwzpjds2aPUVjOSrW9Kopfq2HSqt7LYbNZot9cXk0iPGHhipd6NS3061r2rqVLpQqtZUR1pp1OTSqwkyWmmVjHJlqhQrTScYt57DqrLS7LG9txe81oWdvTh6Fso+5I538sWRxtPTrqX8p/NEsLCvSn6dJo6K6tfRfDTaz3GJdaZXnVTh5RJdWdhM9rpZow4Usxl8jQoVEl6r+KMmjb1qclmi9u1l/ylSkv7NfMvUWJ60+tR/YzLziw/RWPcPrXlaS2aRj3VzduT/rP2LLsqnVk41ZLBG6j7BH5Sc8y5ksaS/Nk0yWjV9JYijotOm3FGLSoQ22NyxhFQ2MZtRuWqyk8k1T0VsQW0sRRJVqdjOKs2942nwxbMC6p3TbxCWDobupU4XwyaMas62X6b9xvFGRKN1T5qWBvlriPNNr3FipUqZeZELlJ/wAx/M7Mo/xs1s4odG939KKGzpKW7bbGeQj1Mo0aeqUYpZgSLWKSxw0m37zJdBdoKjkzzF3W2tU8p/Jx72PhfVG/yRMNW8+alj4j1Z1ZfnHMNuip38eU6sc92C1Rv6PJzfyOVVjVT3qItRpzhHepkzcYu3UxvbZveePeWIXFt+o4mU2nvJsuWlxLCWWS/jNuypVaEuSyW6fD1JHP2dXODZt6mUc7NNLiFyRqQ9Myp6YZG5ABcgJkQBWIxMg2AjGMcxjA8gFE5CnscAhRqFAUFzEFQCgt2JkWCbeAL2m2U726jTits7s7zNOxslDKjTpozujVnG3svKyj6c+vuMrpTqTlP8JTltzlg5X+V03PEZ+s6vUvqzjBtUU9l2mVkc8DToxs6Lwy5b1pQezKQ+E3FhY7XRr9V4eRqPOeRmdJLHyc/Kpc9mUNOuHTqxkn1nVajSV9pXGt3wnP+uTXuOCJFvTku1DZR4ZtDlzZ1YTWzhKlFJJyS3ybdhOLoRbm+Piaa7jl03CWVs0zoLCnVpwhOquF1N0s74OeXh37mWGvt0tk+Rpxexk2T5GmpKMd2easkq+oyrsSV6qxjhm/cilKrPPo0Kku5IsU+cVnq5jLmP8AV5Gt129rabT71sJWnU4cSoyx70aRmyi9yjWjiTL9RtN7NFCtxOT2N4qo1lwvI3ib5ZH11LL5rHcVnOSfrYO0c6v0XLsNqwfonP0KktvSZuadPK3OeaxuW8VhFipSTRBbS5FqT9FHBpUrU4KBkXXAm+Zs1ns9zHu3B5bkiw0xLvHpbGbKcTYqQhOTWc57io9OTy1xfBHoliXGqDqLHJjeNl92UO1larb8GcM1tjVQ8cu1j41GuticHeL6K6yiSNZ95Zo1nyaKiqxj1MkjcxX5WRdrynkSVTbGCorhd5NRqRlLlki7Q1JTctkW7JVHjMH8ixS4OL1UadvJYWyM3PSyJbLOF6Js0HtyM+nJZRdpzOFrcXYSJFIqwmSxmRdJ0LkiUh3ERD8g2M4hOIofka2RufeI5vtBpI2NbyROfeI5rtCvJmAMQ9jzlFEFABVuNHxATGC5ptB17qEcdZUlzR0XRa247lTa5bkyuosdJd1IWGnvqUInnVxWlXrzqye8nk6zpbdcNsqSfrvBx5nCeFyLnI5REgsstQppLLNsoOEME74SKSwFTW0sSR2uiVPLWMqb3wcPR9Y63ozPeUe455tYua1Sj5DUKsOyTK/5jV6T0+DVJP8AUkzK/MdJ6Zvs634VV4qkFOEZrK7S9canVr3UqkIRXcVacMW9Xrc5RSXedjp/RuhGxo+Vi1VcE58tm+ZjKyLIwKOtXdPGI02X7fpFXxmqqKXvNtdHrVLGBY9H7SP5Wc7zfpvVZcNfpSfpuK92SxHWLR5am3/lZorRrdfq92SVaZQXU/mZ1DVZH8Vpttri4fcQXF9xbp8+WxuPSrZvLh+5HLQ7KTy6SLqLpzPlJyy5NEE2854k/cdY9Bsn/L/cF0fsefk/3ZrcNVxFzJcOG1kzps9Il0esHzoxfvE83NO/u8PkamcZuNrzqFdw5RLttqtSlypJ/E7ldG9N/u1P5Ekej+nx5W1P5C5SnNcjS1+vFbUI/Nk76R3TWFQh+51sdGso8ren4SRaXarlRp+FGP4/pea4iprl1U/lQXzK87uvVeeFfBHoP8NtvYw8Ifw+3X8mHhHj9NTceeRVaUs8G5Ji4X5P3R6B/D7f2MPkL/D7f2FPwja+a85m6q/l7+8q1adaWfQe56itPtl/+vT8KFVjb+wp+FGumbi8n/DVfcH4aZ60rKguVGn4UKrSj7KHyL2nDyP8NP8ATJ+5Do2lR8qU37os9bVtSX8uPyHKhD9MR2cPJo2Nz+W3qv8Aysmp2N/F5VpV8DPVPJR/SvkKqcV1L5E6OHmsLHU85/DTX+RlulaapH+TLws9A4F2IOBdiM27a5cRC21b2f8A6CzToat1pr/J/udbwLsQvD7jNjWo5iNtqfXKa/yIkVrqXXVq+GP0Oj4V3BhZ5Geb+18OeVpf9dat/wCn6Dvwl97Wt84/Q3sIHEcf6vhg/g732lV/5kH4G6f5q3/UN5xQcKHH+puOfemXD5yrf9aX1E/hVXr8p8asvqdBwITgHH+m3Pfwmb/L85sR6PJ84w+LOhcO8RxLxF28W6xWJ1gz1PIBdxBcgHWPQzrHoBcZkkdn0ap+ToTn3YOPorNWKO20hcFhN9pjP01i57pTW472EP0rJhmjrsuLU59ySKEVuanpL7T0KeWSVKmHwrmOo+jBsSzcXdpzWVxcgI5KccOUWk+4SW8TotRuqdRUbWNGOJx4pSwc/JYyuxiFJS5nU9GH/wAxjtRy1PmdT0aWLmLfYZz9Lig6R0VV1Hf9KMyNms7s0elHH+PTgnhR3aMaM6n6mWei+2xotOhT1BOtFyVN5il2nZwu4S/KzgLCUld0pNvKqRZ6MorsRzy9t4mxqKS5MfnuBLA5fAy2bkcsCgkAYXYGF2C4ABMLsDhXYKGAE4UHChcBgoEkKGAwQKGQECnZDiEEAdxBxDQAfxBxIbkMgO4kLxDMgA7iF4hgAP4kGRohRJxITI0QgfxBxIYGAH8SDiGYAB+RMjMhkodxCcQ1sTJVObE4hjkNbIqRyEciNsTJUeOgAHZ5QAAAIehiHoCzaLNaJ2enPGnv3nGWb/r4nYac82Ukc828XJ6z/wDkqpUhzL2uR4dQk+1FGHM3PTN9rlJZgQLNKtldpPQkFXZ8soKtSv8ANvhQXHjCl2FB8h2M9WENk9whaazJHX9HaWIub6jk7ePFVidzo9PyVjntZjNrFZ0+Eat5dylFNZjHdd3+5PX0bT6+9S2hntSwxmjYdCrVf8yrJ/6f6Gjkxt0jlrzo7Onf0nYxfkpes2/VZ1KjsLkBva60XAYAUgQHkBQEAXAAIAoAAAAAKIAUoAAAGAAAAAABRAAXYQAAAEABQ6gAADICAKGRBQAQURgIxAEyVRkbkVjQDIjYCFUgCsQDx4BRDs8gAAAB6GjkBNQlw1YvvOv0meaUo9qOMi8NHUaNW3h2NHPNrFndI6WKsKnwMeJ1euWrrUJJbtbo5Rpxe5rH0VPTlgkc8laLHcRUSykRt7jcklKDnJIC/pVB1Kywjub5RsLSUY8oQ279jI6MaY5qdZr0YLPvZb1q58rXpUm/XksruRzy81ueI0tOpujY0oPmorPvLWSjTvItJcixGsnyZhtPkVPBGppipoKk4mLxMZkMgP4xeIjFAkyGSPIZYEoZI894qYDshkAzkBQEABRRuRcgAoggDgyNFAMgAAAAAAAAACiAFDBCDghGAjYgUuQbG9YuQEyJkBGVSZDIMQKUaAmSgABMhHkPC0ssQmu5RnczlT9VvYhOzygQAAByGjkA9GtpNbCSzyZkIntKzp1e5ks3FjtJpV7dSXPG5yGp2jt7htL0JPKOk0y6Xqy9Vkt/YQuKbTSaZzxuq3ZtxSHIv3OkV6M3wx4o9pHT0+tJ7xZ0Y0rwi5PY2NL0+derGMYttk+n6NUnNLhbOu02zpaZSdWsvTxhIzcmscUtNw07SlRjhSfM5WdWV3ezrL1Y+jEta9qUpvyUH6dTs/KiCyUVSUYrkc2rU9OdRc9y5Qqyb7COEM9RZp0uthVmM5ImhVzzIEOiRVpSz1jslenLBOpAOATIZCnZAaKA4UbkMgPQqGZFyA8TI3IuO0BcgnkMAAoCZwJkBwCe9igKAmQyAuQG5BgKLkaKAojYCYAXIZG5F5IA6wyAMBMhgQXOwCCAxGythjWKIwEABMhCjQyIUeRAAHZ5QIAAKlkfGBGPjPAEvCkhjWGPhUTHOKaIq1YXjg1GTx3nSWV6pRUZP3M41xaZZt72pRazujNx2sruMQl1JoI04J+qjm7fW1Fbtr3lr+P0kuWWY1Wtx01O7jb08UopS65GRqusKknmXHVfJGJca7WqpxpLgXaR2VnWu6vHJN562WY/s3+klCFSvVdSeZTkdBaWyp01lbi2dhGjHlmXaXlDCM2rIZGKRKhOHA5BoqHYYgqyQKiam9iJEtNASAgXvDPYFKKJuGAFAMCgAogZAcGRuQyA7iFyNABQBMXIAhcjcjWwHtjcibsXABkVZDhHAAogNgK2NyIKl1sAUccxWwbGgLkMiCAKAgZAQRg2BWyMQUawgbEAQAGi5EKPJAADs8pAFwGAAQdgMAIKpyXWLwiqD7AHKr2hxxY6NCT6ielYym+RF8q+Yk1GhOtLFODZr2mi5ac0bltZUqCXDFZM3JqYsnTtCe06/wAjoaFCFKKjCKSFihyMW7dJNJFhAM3FRA7IqEFwFLkUQcluQLFMmgMRImFOHDExcgOyGUNAB3EGRqQuwC5DcMpCcSAcA3jz1Bl9bCH5EckusYADuMFJsTGRySXUAJZFwKKQJgUFuKkUGBVsGUhrYC8Q0BUgBC5EzgbnICgAAAAAAIDEbAQBMgVoZGgxAARijQAQGIyjyfAvCKOR2eU1RHKA5EkV3EESgSKlnqJoQTZapwgibXSpC2b6izSsW+ouUlDqNClTWMszcmpipW+nLrWTUoWcIY2Q+DjFEimsczNrciSEVFbEiIlNdo5TRFTICLjQvGQSpipkSn3Dk2FSZ2FyyNMVNgSLcfFEaySLIEiQ5DEKBJt2i8SRGmhUFPz2IOIamLnuAOJibi7hgAwLsgUUO4SBouO4ckOSwAzhY5QHCZKBJCiAAoqEDIDtkHEMyKAAAAKDY1sQBWwQAAojAAAGA0BRsnuK2NAEKNTBsKRiMGNbKFQgITJQMRi5GgeYqmPjSz1FdXM11RHxvakfyw+TOryrcLfuJ4W/cUVqdZfkp/J/UetYrr+VR+T+pF3GjG1b5IsUrJvqMpa7cx5UqHhf1HrpHdrlSoeF/Unldx0FG0jBcidU+45rzlvPZUPC/qL5zXvsrfwv6mea11HTqHcOUe45bznvfZW/hf1F86L32Vv4ZfUc07jq1HuHcL7Dk/Om+9lb+GX1DzqvvZW/hl9RzV7jrMPsHYZyPnVfeyt/DL6i+dd97G28MvqOadx1yTHI4/zsvvY23hl9RV0tv1/JtvDL6k4p3HYpD4pnGed1/wCxtvDL7hfPDUF/JtfDL7hzTuO1UWSKL7Th/PLUfY2vhl9wvnnqPsbXwy+4c07juMDlE4bzz1H2Fr4JfcHnpqPsLXwS+4cU7ju8CpHCeeupewtPBL7g89tS9haeCX3Dmr3HebCo4Lz21L2Fp4JfcL57al7C08EvuHNO47zAuDgvPfUvYWngl9wvnxqfsLTwS+4c07jvkg2OB8+NT9haeCX3CefGp+wtPBL7hxT5I9A5Bk8/8+NT9haeCX3B58an7C08EvuHFPkjvwOA899T9haeCX3C+fGp+wtPBL7hzT5I74VHAefGp+wtPBL7g8+NT9haeCX3DmnyR37eQZwHnxqfsLTwS+4PPnU/YWngl9w4p8kegAef+fGp+wtPBL7g8+NT9haeCX3DmnyR34jZwPnxqfsLTwS+4Tz41P2Fp4JfcOafJHfgcD58an7C08EvuDz41P2Fp4JfcOafJHfgcB58an7C08EvuDz41P2Fp4JfcOafJHfgcB58an7C08EvuDz41P2Fp4JfcOafJHetgcB57al7C08EvuF899S9haeCX3DmnyR3jY04Tz11L2Fp4JfcHnrqXsLTwS+4c07juxDhfPXUvY2vhl9wnnpqPsbXwy+4vNX5I7piM4bz01H2Nr4ZfcJ556j7G18MvuHNPkjuVyGnEeeWo+xtfDL7hPPHUfY2vhl9w5qfJHcCHEeeOo+xtfDL7g88dQ9ja+GX3DmnyRzwAB0cAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAf/Z\n",
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"800\"\n",
       "            height=\"480\"\n",
       "            src=\"https://www.youtube.com/embed/opsmd5yuBF0\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.YouTubeVideo at 0x7fca97264630>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "YouTubeVideo('opsmd5yuBF0', width=800, height=480)"
   ]
  }
 ],
 "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.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "512px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": true,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}