labs/DRL.02.DQN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Run this cell to set your notebook up on Google Colab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!apt-get install -y xvfb python-opengl ffmpeg > /dev/null 2>&1\n",
    "\n",
    "!git clone https://github.com/yfletberliac/rlss2019-hands-on.git > /dev/null 2>&1\n",
    "!pip install -q torch==1.1.0 torchvision pyvirtualdisplay piglet > /dev/null 2>&1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color='#ed7d31'>Deep Q Networks</font>\n",
    "------------\n",
    "You can find the original paper [here](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Preliminaries: Q Learning</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color='#ed7d31'>Q-Value</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q-Value** is a measure of the overall expected reward assuming the agent is in state $s$ and performs action $a$, and then continues playing until the end of the episode following some policy $\\pi$. It is defined mathematically as:\n",
    "\n",
    "\\begin{equation}\n",
    "Q^{\\pi}\\left(s_{t}, a_{t}\\right)=E\\left[R_{t+1}+\\gamma R_{t+2}+\\gamma^{2} R_{t+3}+\\ldots | s_{t}, a_{t}\\right]\n",
    "\\end{equation}\n",
    "\n",
    "where $R_{t+1}$ is the immediate reward received after performing action $a_{t}$ in state $s_{t}$ and $\\gamma$ is the discount factor and controls the importance of the future rewards versus the immediate ones: the lower the discount factor is, the less important future rewards are."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color='#ed7d31'>Bellman Optimality Equation</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Formally, the Bellman equation defines the relationships between a given state (or, in our case, a **state-action pair**) and its successors. While many forms exist, one of the most common is the **Bellman Optimality Equation** for the optimal **Q-Value**, which is given by:\n",
    "\n",
    "\\begin{equation}\n",
    "Q^{*}(s, a)=\\sum_{s^{\\prime}, r} p\\left(s^{\\prime}, r | s, a\\right)\\left[r+\\gamma \\max _{a^{\\prime}} Q^{*}\\left(s^{\\prime}, a^{\\prime}\\right)\\right]\n",
    "\\end{equation}\n",
    "\n",
    "Of course, when no uncertainty exists (transition probabilities are either 0 or 1), we have:\n",
    "\n",
    "\\begin{equation}\n",
    "Q^{*}(s, a)=r(s, a)+\\gamma \\max _{a^{\\prime}} Q^{*}\\left(s^{\\prime}, a^{\\prime}\\right)\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color='#ed7d31'>Q-Value Iteration</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define the corresponding Bellman backup operator:\n",
    "\\begin{equation}\n",
    "[\\mathcal{T} Q]\\left(s, a\\right)=r(s, a)+\\gamma \\max _{a^{\\prime}} Q\\left(s^{\\prime}, a^{\\prime}\\right)\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Q$ is a fixed point of $\\mathcal{T}$:\n",
    "\\begin{equation}\n",
    "\\mathcal{T} Q^{*}=Q^{*}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we apply the Bellman operator $\\mathcal{T}$ repeatedly to any initial $Q$, the series converges to $Q^{*}$:\n",
    "\\begin{equation}\n",
    "Q, \\mathcal{T} Q, \\mathcal{T}^{2} Q, \\cdots \\rightarrow Q^{*}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color='#ed7d31'>Imports</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, './rlss2019-hands-on/utils')\n",
    "# If using the Docker image, replace by:\n",
    "# sys.path.insert(0, '../utils')\n",
    "\n",
    "import gym, random, os.path, math, glob, csv, base64\n",
    "from pathlib import Path\n",
    "from timeit import default_timer as timer\n",
    "from datetime import timedelta\n",
    "import numpy as np\n",
    "\n",
    "import torch\n",
    "import torch.optim as optim\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "\n",
    "import matplotlib\n",
    "%matplotlib inline\n",
    "\n",
    "from qfettes_plot import plot_all_data\n",
    "from qfettes_wrappers import *\n",
    "from openai_wrappers import make_atari, wrap_deepmind\n",
    "from gym.wrappers import Monitor\n",
    "\n",
    "from pyvirtualdisplay import Display\n",
    "from IPython import display as ipythondisplay\n",
    "from IPython.display import clear_output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color='#ed7d31'>Deep Q learning</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usually in Deep RL, the **Q-Value** is defined as $Q(s,a;\\theta)$ where $\\theta$ represents the parameters of the function approximation used.\n",
    "\n",
    "<img src=\"../imgs/approx.png\" alt=\"Drawing\" width=\"200\"/>\n",
    "\n",
    "For *MuJoCo* or *Roboschool* environments, we usually use a simple 2- or 3-layer MLP whereas when using **raw pixels for observations** such as in *Atari 2600* games, we usually use a 1-, 2- or 3-layer CNN.\n",
    "\n",
    "In our case, since we want to train DQN on *CartPole*, we will use a 3-layer perceptron for our function approximation. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Network declaration</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, we build $Q(s,a;\\theta)$ function approximation. Since the input is composed of 4 scalars, namely:\n",
    "<center>[position of cart, velocity of cart, angle of pole, rotation rate of pole]</center>\n",
    "we build a FCN -> ReLU -> FCN -> ReLU -> FCN neural network. As an exercice, change the architecture of the network:\n",
    "\n",
    "1. Change the 1st fully-connected layer from 8 hidden neurons to 16\n",
    "2. Create `self.fc2` in `__init__` with 16 neurons\n",
    "3. Create `self.fc3` with `self.num_actions` as the output size\n",
    "4. Add it to the network in `forward` with no activation function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DQN(nn.Module):\n",
    "    def __init__(self, input_shape, num_actions):\n",
    "        super().__init__()\n",
    "        \n",
    "        self.input_shape = input_shape\n",
    "        self.num_actions = num_actions\n",
    "\n",
    "        self.fc1 = nn.Linear(self.input_shape[0], 8)\n",
    "        self.fc2 = ...\n",
    "        self.fc3 = ...\n",
    "        \n",
    "    def forward(self, x):\n",
    "        x = F.relu(self.fc2(F.relu(self.fc1(x))))\n",
    "        x = ...\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Safety checks</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color='#ed7d31'>Network architecture</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a *safety check*, inspect the resulting network in the next cell. For instance, the total number of trainable parameters should change with the architecture. Check the correctness of `in_features` and `out_features`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Observation space:\n",
      " (4,) \n",
      "\n",
      "Network architecture:\n",
      " DQN(\n",
      "  (fc1): Linear(in_features=4, out_features=8, bias=True)\n",
      "  (fc2): Linear(in_features=8, out_features=8, bias=True)\n",
      "  (fc3): Linear(in_features=8, out_features=2, bias=True)\n",
      ") \n",
      "\n",
      "Total number of trainable parameters:\n",
      " 130\n"
     ]
    }
   ],
   "source": [
    "env_id = 'CartPole-v0'\n",
    "env    = gym.make(env_id)\n",
    "network = DQN(env.observation_space.shape, env.action_space.n)\n",
    "\n",
    "print(\"Observation space:\\n\", env.observation_space.shape, \"\\n\")\n",
    "print(\"Network architecture:\\n\", network, \"\\n\")\n",
    "\n",
    "model_parameters = filter(lambda p: p.requires_grad, network.parameters())\n",
    "print(\"Total number of trainable parameters:\\n\", sum([np.prod(p.size()) for p in model_parameters]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color='#ed7d31'>Run a Policy with Random Actions</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What the working environment looks like? It's always useful to know the details about the environment you train your policy on. For instance, its dynamics, the size of action and observation space, etc. Below we display three different random policies on `CartPole-v0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "xdpyinfo was not found, X start can not be checked! Please install xdpyinfo!\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<video alt=\"videos/openaigym.video.0.65.video000001.mp4\" autoplay \n",
       "                      loop controls style=\"height: 400px;\">\n",
       "                      <source src=\"data:video/mp4;base64,AAAAIGZ0eXBpc29tAAACAGlzb21pc28yYXZjMW1wNDEAAAAIZnJlZQAAFrdtZGF0AAACrgYF//+q3EXpvebZSLeWLNgg2SPu73gyNjQgLSBjb3JlIDE0OCByMjY0MyA1YzY1NzA0IC0gSC4yNjQvTVBFRy00IEFWQyBjb2RlYyAtIENvcHlsZWZ0IDIwMDMtMjAxNSAtIGh0dHA6Ly93d3cudmlkZW9sYW4ub3JnL3gyNjQuaHRtbCAtIG9wdGlvbnM6IGNhYmFjPTEgcmVmPTMgZGVibG9jaz0xOjA6MCBhbmFseXNlPTB4MzoweDExMyBtZT1oZXggc3VibWU9NyBwc3k9MSBwc3lfcmQ9MS4wMDowLjAwIG1peGVkX3JlZj0xIG1lX3JhbmdlPTE2IGNocm9tYV9tZT0xIHRyZWxsaXM9MSA4eDhkY3Q9MSBjcW09MCBkZWFkem9uZT0yMSwxMSBmYXN0X3Bza2lwPTEgY2hyb21hX3FwX29mZnNldD0tMiB0aHJlYWRzPTMgbG9va2FoZWFkX3RocmVhZHM9MSBzbGljZWRfdGhyZWFkcz0wIG5yPTAgZGVjaW1hdGU9MSBpbnRlcmxhY2VkPTAgYmx1cmF5X2NvbXBhdD0wIGNvbnN0cmFpbmVkX2ludHJhPTAgYmZyYW1lcz0zIGJfcHlyYW1pZD0yIGJfYWRhcHQ9MSBiX2JpYXM9MCBkaXJlY3Q9MSB3ZWlnaHRiPTEgb3Blbl9nb3A9MCB3ZWlnaHRwPTIga2V5aW50PTI1MCBrZXlpbnRfbWluPTI1IHNjZW5lY3V0PTQwIGludHJhX3JlZnJlc2g9MCByY19sb29rYWhlYWQ9NDAgcmM9Y3JmIG1idHJlZT0xIGNyZj0yMy4wIHFjb21wPTAuNjAgcXBtaW49MCBxcG1heD02OSBxcHN0ZXA9NCBpcF9yYXRpbz0xLjQwIGFxPTE6MS4wMACAAAABk2WIhAAz//727L4FNf2f0JcRLMXaSnA+KqSAgHc0wAAAAwAAAwAAFgn0I7DkqgN3QAAAHGAFBCwCPCVC2EhH2OkN/yx1GsgEx/k3/0/uIsDlRsNTm+/GCucdT6Yw89CLi5kMcpQmWpRTtbMx/C5c0ZJ9pBtu98dQKFBEV4vxLhusanNfDRj1lm/bFX3eLhVuq6gI5UyvUeTrJxsvpv2WQwQ9jpu9ACy4RWR7Uf7KI4faA1flcklbzs5kX+LYc7bHgUpTeL3jCpnqesrfDrQJFGhM/jc6hH/DlPuhaD0yo0c50+9yXJEYaTD9ecrNxk/GbV7dCnNyO4SHZ+X9hveUuKX/NXRv1mP1lA90ZeVg7sBb5VzGY2Kv6ScO+T/CSLyUCGdfA34Qw87rBOrHWCx+O48jdFMt0w9RnFrPSMguCEeO3LIWJYkouq0qckbRnWQneLGWnU4DjjdbFqXakw/NvROz5AtbiAE0wXo4Y/0o3UpOJVfCMbdZaifATgJQbKqSo/ze37GzdNt6oATcAAADAAADAcUAAAB6QZokbEM//p4QAABFUi5AJnV9Tgnlar3J+Jftdg3WchOOl/afXY3oqtfAM1y0KMsubs4XoZn5khQxb0hT3oDddHcnn3W+pVOSLewmYfd4JvuIoNYwN1BmLwXO2a5mTMZfweTcyca3eyfk/CrtFYi1gDQ4O2qVvnUAVsAAAABeQZ5CeIR/AAAIK0bYRn/h9st1Uyjz9niJH0kAAtRDZkDaxzwH6OwuL2By6Q7EvW7kk8rPQUQ6cZf+mC2jhrS/BavgZDKfpOHBex9yOuxznn0AAAMAA7j/cp61KoACXwAAAEcBnmF0R/8AAA0uFJr23TPP09iIl+4hPjT7PmJVw+X373IYGmdvKlgTRU9Mq9ShL88QDXDAE+ElExleR+AAAAMB+x7alUABWwAAAFIBnmNqR/8AAA00np+LDigrGz4a7QATSVCq8f9pCu/Y0Y+S92tPmA11S4/jbX4bN3KXb0/0rHkc00dHL5w87LGgRjK3AAADAAe0MS/1tTwgAJOBAAAAW0GaaEmoQWiZTAhn//6eEAAARVU/4AHSPuBR1FuGVhjTg2LI0+zyGtXxodqVj6VTr/iWo/RpR61a77imT9mZyUCUnWviW6UPfu9QzU/8NIGQJfTvFDxrVMsAB00AAABgQZ6GRREsI/8AABa+pfop8ALW0yl4a+r1D82dzfYM4EKpSHaeRaCQJKlpVGF+DwnwH39cfLXhOQU0VTrV2mzLhPWEbsiGzQ35Bsxj8D/+yQ5aNoSMvs+wAMnN2tTLAAHHAAAARQGepXRH/wAADV6N3jBMVuew8EcyrIW0UQe8RYgJRCxcTAxK67gmcarnsVWL5kL3tY5a7zLEfPgcoAAAAwOS05upVAACNwAAAEQBnqdqR/8AACO/FX42GmNRa/cCfkc2Ok+il1SM1TxT27iTLYtRPnMXeFekKmDqcnArt5P79Iz2YIJY1AABSmYlUAAbUAAAAGNBmqxJqEFsmUwIZ//+nhAAAEVIlyAOTMWkCKlCly4hrctqCrbwAB5qNRsPfXBq2wZgij5Hd4nTl7w28oMmgMeNDWLjA083evn/s55aSAglsrigyUr17X+SeAiqCw9WjLAA2YAAAABYQZ7KRRUsI/8AABaoZVAePRDb3MUKEnQdsKL0P5rJwmoT7xzzTDsZNGCytNezOYhmnSSY2v8DmXceW3esHr3TJEz9tFBfVabfPWF4AAADAFJWmNWtGWABswAAAC0Bnul0R/8AACPDMvxrtQ4G88E4rFXHsl5Mc1opMAAAAwADmgAAm4pfanhAAi4AAAAwAZ7rakf/AAAjvx+L8Ea0AJZF9uYYaJVuTOBePOoVeAAAAwAAAwBpAADvwFMsABNwAAAAV0Ga8EmoQWyZTAhn//6eEAAARUiXIArQ+5dodiC3CeVBm5jrNNs7QixMrxs/T1+QG0S8VHnaRyvHBD+NpM8kBPr6lDDwhN+AAAADAAj6gAADjiWpVAAS8QAAAD1Bnw5FFSwj/wAAFrZuwAcesS9VApzOT0O8lG+xxO6mFP9gRsdxT9WNT9AAAAMAA9kWKUi9kAQ3LUqgAJeBAAAANwGfLXRH/wAAI5K71AdqY/jYaQx+iHJ/Kc8JUwAAAwAAEEucbkGjnPcmN34qSvzd+OXFqVQAG9EAAAAxAZ8vakf/AAAjvwuwmoLPvskfPBg4BUJQZ3WgCxYxqUU3zJPFcpLL759WdTsLZVA0IAAAAHNBmzRJqEFsmUwIZ//+nhAAAEVIlyAIjDwkYW4Tyc8PviQKOtl1WLaBfSF0GJxZrvItmkh73thafHsmpRsax2VPt7u+g7zU5rbqz+0ki9vIsfRfc0GzxyLV/J8STx5NOUSSVH+OBKgrF60Fpjf2NPeeEDZgAAAALEGfUkUVLCP/AAAV52EtQXdv8xeb96gxjvk8VFkFEQL1gQpwAAGtjuSmICkhAAAALAGfcXRH/wAAIqxC3rLYyj0JYPVYTgAmPPRHU6YjsOOfvPAAAAMAAHua4Qf4AAAAIAGfc2pH/wAAIr8fjDfCLKstw4Il0hUUr8JEeYwHB5WzAAAAjUGbeEmoQWyZTAhn//6eEAAARW1neBDBQPa2rbOeR2/kRwvtlngqMvZWRa8RfOh5p6N/LViuiWJppecjY9+aJiFMaRjNnXHj075wEDgRMSb2Pq/4rxiwdnTUBvBUvbtfgZYlRP34yoaI37JQJ9VvpPwOow9tK0SlRfBsWFqXxFQTzD8hKlwPtYrxVUd4MQAAAClBn5ZFFSwj/wAAFm+XKhb93J4eYvGj6JETqzMcIlbSi9XAURssyZEQmAAAABcBn7V0R/8AACPC8HtF/OVngYYUg9AiFwAAAB8Bn7dqR/8AACPHx5t4kI2EKXMEHgIA9MUdKiM2Iz9JAAAAyUGbvEmoQWyZTAhn//6eEAAARVEKHQAFgpbvlJwAiMa2Etm0PfogSMxLOErmz46RLZ0ZgjWtqCPLopNvZ/iH2V00tIEyspQTm21YLqsSnp/Ju86OF5D6ArI3sbEySX/kfO1GmVOYMdLWcljUYTpzFLWbrAcl4VaFindjOYotyL0h+Td7P7OCMSoDnSJY4EsIkM/G/U17YsxYJxtE2IrsUPjPzTpTixCMm3izi1aUlpbu815rAfCgAh7uxcH/HXFWIvTPkBZR1986YAAAAElBn9pFFSwj/wAAFrNMx4ArQHHGNz88lBSygP8uf+AIIhKLS2672ETrPE7Yrq6UYyTyX7esHdDT/GUCSmhp3qfk8UUbsYjbYE2zAAAAMwGf+XRH/wAAI6Opgow9b0tXPUr5acBrDg5cxbPzGhrfYAH3xCLQ5dl7EHooswO1EANtuAAAADsBn/tqR/8AACO/H4ZtmYchkLN25uOZdwRKGE9qHT4trZXfmACzLLPQATtbm/TYb3UnnxMoJq0mYa023QAAAIVBm+BJqEFsmUwIZ//+nhAAAEVlPoDEABX8YQ+YPLKxnXRmXbln+rvfbefgJdHUzLzxfhCX/rmCS7b7YP45fnneg/1ooHlbrkInBK5GlFommLOzrNu7ug8ASKlO77yGOggtPenjGCmIfEbNR/tR8Q2fZ+uWzES43e79MqjNNJ4C+CetDdlhAAAAUEGeHkUVLCP/AAAIZIufXN9rfpTcQKYCA69okOHSRKHgegAx+R90Vqk5I+5YHEOYAEyPRv7XPU6tXjI6APiJLCQaTQKTxOZKgAsqTjeor8YoAAAALwGePXRH/wAAI8M5FwLgDG0elKNGszpih3w0VtMs1UlSGl7bonYahYXbX8CyOW24AAAALgGeP2pH/wAAI6jcUpnw37vdRrf5YRPXg6U7gT3jWzbCV4IAHvyVhpnvknngQ/kAAAB5QZokSahBbJlMCF///oywAABIFFtJFE/jog4ijQAERbsidUw8BkY6dx2F+uL+8lvEhLVoB6oKONAtIDVzOPtRc8qCebZ4vJmewgNV2VgnnkSHQZ2Mz0Ko0mi7lhYWnD37bm9hkD74K+mK7Z47vy2FiNUm7WAf3oXzdQAAAERBnkJFFSwj/wAAF0xDzbY8mKYQY+2Gd8FoSMEuTYe3veXXXLmGxIr4lXWBgwABdASZDrev0RsJCq63UfbNvjJmSC8YoQAAACkBnmF0R/8AAA1/XIOCcIbmhkzvsMlnY4tyEpz97lGNLWGhCgqDMUj5gAAAACsBnmNqR/8AACSyLXNfvGznw2emFJN1rpc+WRABVkAYbxhwcIN84+eq8NSBAAAAdUGaaEmoQWyZTAhf//6MsAAASAIpLmAKCnMxBLtz6S4X9AonkCuZCbZXAKz+Ey1pizlH+wLZQd0ciOJ4nwXXUITE0S0SnSBGjo0HhHQGU3jB5scvDVEJ0Ixw3kXoBkWYsoDxLv8Ocm6XKpI9jq7JpMuxnl3YgQAAAD9BnoZFFSwj/wAAF0xDzX7xoktZI/ipDw7Iv8/Kph9+BnB314aJ/TK9hZbLaqoBt7BXNrk2Bg4UMIz59Y7LB/cAAAAzAZ6ldEf/AAAN19OG0bDwDSV7GL50hY9bP7mdKAVtXEg8IAIkILpH1VajJd2PhiEc+e2hAAAALAGep2pH/wAAJL2Ct1khM+MtiLnOIqI/GBPEh/BzKvlSy6G93J/YmK9dcxS8AAAAs0GarEmoQWyZTAhf//6MsAAASBCa0pIgAvX4LW+QmgQvGelWqcv3R/7yLgojrpRXbj0beLs9oNfh3zK/9PDw06zXNOJSMoibEj3yB7VoAFf84HbfYyFRF9hQeD7oD/OxXFjQZw6zZihuFqLwSx3uWBrP+fXSC1qqBae6OLYvCEBWxTTFkMl/DPPTFR91167fyAyvT7jZ05f/4POhI9wxyW+8IvHDLzj7aVI3EKPxH8+8T2nmAAAAYkGeykUVLCP/AAAXUDeARo0kkOQ3EIg+y5NdUW1eI1re3TSk5/6EhkZsV/9RMLs85rUHpzgDOXwjRUJobyLSS/EUNgAtSJM6LGGY+wB/B5uD2lKZAEHpx7a4Zpdtd5PuAzVBAAAAOwGe6XRH/wAAJKnqU7qDzSYWG0zIS/n/mBNXeVFN2V0JCh1k8nSlKiB6BqW5K02hbX5Q+BLEM+d7mfbcAAAAOQGe62pH/wAAI72EHfhhDhW126uIzDpVXMLOow6owlIGAtwrL1ZGIaLYCNbsP0AJkTv6mXo0980+YAAAAHFBmvBJqEFsmUwIV//+OEAAARW7Er4pQKkOtlEYULgEq4XZ0djq0ik4llEahEZ5lKdKg8IbQ4Wt9z2BVIxr/8A9bInIrH4DaUzCAbSmGmSl2T7uiez45RqhkWGKSa1NKUuDwRmHeNhFM1BpUFak+Eg5KQAAAF1Bnw5FFSwj/wAAFzpz+7SHsQYuKbRkDhJAPRnVhMIvXbEDNqcIdkB8pLSyjWogLj/q0JgjDc7X/yvgBLNGdPcrmrPk2COU96Ugi3il8JldmTsJR8LuG6O8tGbhsUEAAAA2AZ8tdEf/AAAkqenHFA1Le4zVSbc23a3NNfdxVSZbsoADm9DVQyDtJOppg7RFFxhnbqOtc7rFAAAAPQGfL2pH/wAAJL2DYx1rpYfNGz9Vj1A7n67eMpjybhX94E36Rqd/vd+gBNVMiAaIi8YO1EtCJapuz6SfugMAAAB2QZsxSahBbJlMCF///oywAABIQJSkFYAWudlbTrB/MtUtfuVowNNuHP7KLRM0P6zexsTt9O6M3iqHGkMwz0mLpg+bn1mlE4vgsd3tl+rv98gM7HqwctEgTdFqQmulBIpDjFimUApuKr+/09CEiqvTnU7CrjDnMAAAAJlBm1VJ4QpSZTAhX/44QAABFPPhuOAAfkL9IfhxMJOhgeRgMlfGs0ABfHiY/iYVJ2bar14OVK9nDEXs1hdfQv6cQSmJxlVoHnMQJtgsJsfBgat1uDvzGBLUIFx9TeW5I5zP1xS7UoXT4fLvRzHtrWBUEtyKG1rmIyCB+hXu9oBk3iitlYQkLD7IfCdbvY4QbNKwHXKyaP00Y4EAAABJQZ9zRTRMI/8AABdLW2X6L2lEFVJw/k6bdDZ57sv3aclAwvQs6zONhzESvmrgIN/gBYjukITd+44IWWZ9pMHL2AmKNrurb1KzlQAAAEMBn5J0R/8AACTAmTJ8tTWH0iD1d1uhIdeG8m49VayZKl0Vh0IWaN4PCXMiAD+QZfNMFSAb2ktOU5kndXJKbizlhk2BAAAAPQGflGpH/wAAJL0nAebFBDOh7f8zMgXk/4XkoASwybfT4fFg90YDuMeLt64p/d4pTk/hGmHjPk4kyR2t7oEAAACPQZuZSahBaJlMCP/8hAAAEMwHIIAdHj90Fq3t+jdshKUVi7U+rtbRpt8kV1o0xJIYGQ6Mi0kBfRjw8k6Y/SJjHnAGAXThzN+BHFfGuDtGMydP/F3t/FpvToYh8jGesvfaaLUR/WX+Lg0nFXQ+iqOj4HTGzG/sZf5PcgiScK9PlNF1zjJ62fVAzZGttaIfOuAAAABeQZ+3RREsI/8AABffeiP6OUWOdz9RYtppRKS8GJCE8+zpt7sfpodW9w2zl2AbEM0+NmnSdi7rKP47tbPwLN/angMMTT3+4fNzbJoABb/DRnDJ11fH3QQWPnF43qMcqQAAAD4Bn9Z0R/8AACWojkV3VHYkNHWjOyfMgVFT7UwFL5e2+P1Mah7UtrZoWNAnYKairX2ar62G1UlUQwuYOaQ1qQAAAD8Bn9hqR/8AACW/CvPtxfW2MJojkMXTtbtILoHQi3bS/UXvPcxglofDZxMNf04ULzbf+kfpvAB+vRFl0YGvf4AAAAXLbW9vdgAAAGxtdmhkAAAAAAAAAAAAAAAAAAAD6AAABIgAAQAAAQAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAgAABPV0cmFrAAAAXHRraGQAAAADAAAAAAAAAAAAAAABAAAAAAAABIgAAAAAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAABAAAAAAlgAAAGQAAAAAAAkZWR0cwAAABxlbHN0AAAAAAAAAAEAAASIAAACAAABAAAAAARtbWRpYQAAACBtZGhkAAAAAAAAAAAAAAAAAAAyAAAAOgBVxAAAAAAALWhkbHIAAAAAAAAAAHZpZGUAAAAAAAAAAAAAAABWaWRlb0hhbmRsZXIAAAAEGG1pbmYAAAAUdm1oZAAAAAEAAAAAAAAAAAAAACRkaW5mAAAAHGRyZWYAAAAAAAAAAQAAAAx1cmwgAAAAAQAAA9hzdGJsAAAAmHN0c2QAAAAAAAAAAQAAAIhhdmMxAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAAAlgBkABIAAAASAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGP//AAAAMmF2Y0MBZAAf/+EAGWdkAB+s2UCYM+XhAAADAAEAAAMAZA8YMZYBAAZo6+PLIsAAAAAYc3R0cwAAAAAAAAABAAAAOgAAAQAAAAAUc3RzcwAAAAAAAAABAAAAAQAAAeBjdHRzAAAAAAAAADoAAAABAAACAAAAAAEAAAUAAAAAAQAAAgAAAAABAAAAAAAAAAEAAAEAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAAAEAAAUAAAAAAQAAAgAAAAABAAAAAAAAAAEAAAEAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAAAEAAAUAAAAAAQAAAgAAAAABAAAAAAAAAAEAAAEAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAAAEAAAUAAAAAAQAAAgAAAAABAAAAAAAAAAEAAAEAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAAAEAAAIAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAABxzdHNjAAAAAAAAAAEAAAABAAAAOgAAAAEAAAD8c3RzegAAAAAAAAAAAAAAOgAABEkAAAB+AAAAYgAAAEsAAABWAAAAXwAAAGQAAABJAAAASAAAAGcAAABcAAAAMQAAADQAAABbAAAAQQAAADsAAAA1AAAAdwAAADAAAAAwAAAAJAAAAJEAAAAtAAAAGwAAACMAAADNAAAATQAAADcAAAA/AAAAiQAAAFQAAAAzAAAAMgAAAH0AAABIAAAALQAAAC8AAAB5AAAAQwAAADcAAAAwAAAAtwAAAGYAAAA/AAAAPQAAAHUAAABhAAAAOgAAAEEAAAB6AAAAnQAAAE0AAABHAAAAQQAAAJMAAABiAAAAQgAAAEMAAAAUc3RjbwAAAAAAAAABAAAAMAAAAGJ1ZHRhAAAAWm1ldGEAAAAAAAAAIWhkbHIAAAAAAAAAAG1kaXJhcHBsAAAAAAAAAAAAAAAALWlsc3QAAAAlqXRvbwAAAB1kYXRhAAAAAQAAAABMYXZmNTYuNDAuMTAx\" type=\"video/mp4\" />\n",
       "                 </video><br><video alt=\"videos/openaigym.video.0.65.video000000.mp4\" autoplay \n",
       "                      loop controls style=\"height: 400px;\">\n",
       "                      <source src=\"data:video/mp4;base64,AAAAIGZ0eXBpc29tAAACAGlzb21pc28yYXZjMW1wNDEAAAAIZnJlZQAACn5tZGF0AAACrgYF//+q3EXpvebZSLeWLNgg2SPu73gyNjQgLSBjb3JlIDE0OCByMjY0MyA1YzY1NzA0IC0gSC4yNjQvTVBFRy00IEFWQyBjb2RlYyAtIENvcHlsZWZ0IDIwMDMtMjAxNSAtIGh0dHA6Ly93d3cudmlkZW9sYW4ub3JnL3gyNjQuaHRtbCAtIG9wdGlvbnM6IGNhYmFjPTEgcmVmPTMgZGVibG9jaz0xOjA6MCBhbmFseXNlPTB4MzoweDExMyBtZT1oZXggc3VibWU9NyBwc3k9MSBwc3lfcmQ9MS4wMDowLjAwIG1peGVkX3JlZj0xIG1lX3JhbmdlPTE2IGNocm9tYV9tZT0xIHRyZWxsaXM9MSA4eDhkY3Q9MSBjcW09MCBkZWFkem9uZT0yMSwxMSBmYXN0X3Bza2lwPTEgY2hyb21hX3FwX29mZnNldD0tMiB0aHJlYWRzPTMgbG9va2FoZWFkX3RocmVhZHM9MSBzbGljZWRfdGhyZWFkcz0wIG5yPTAgZGVjaW1hdGU9MSBpbnRlcmxhY2VkPTAgYmx1cmF5X2NvbXBhdD0wIGNvbnN0cmFpbmVkX2ludHJhPTAgYmZyYW1lcz0zIGJfcHlyYW1pZD0yIGJfYWRhcHQ9MSBiX2JpYXM9MCBkaXJlY3Q9MSB3ZWlnaHRiPTEgb3Blbl9nb3A9MCB3ZWlnaHRwPTIga2V5aW50PTI1MCBrZXlpbnRfbWluPTI1IHNjZW5lY3V0PTQwIGludHJhX3JlZnJlc2g9MCByY19sb29rYWhlYWQ9NDAgcmM9Y3JmIG1idHJlZT0xIGNyZj0yMy4wIHFjb21wPTAuNjAgcXBtaW49MCBxcG1heD02OSBxcHN0ZXA9NCBpcF9yYXRpbz0xLjQwIGFxPTE6MS4wMACAAAAB8GWIhAAv//72rvzLK0cLlS4dWXuzUfLoSXL9iDB9aAAAAwAAAwAAJuKiZ0WFMeJsgAAALmAIWElDyDzETFWKgSxIZq+D1dlAMw7qxX62af1Tw/JsTsknrDHtV715ZZra1KfA40JSKFipHkliEdXUkUNZnNl6j20VEQNyiaz/G3fYJkUirSC8qOSOSVd1x0ngVkhSQUIMssEpCKyRNCshnFiv7uKQKV+clFLNgXU7pfPoWzZCYAcrHV+6qdePr9PgzaYSxTzjfFqkV59QsfZ16wcJ5itqp/la59D0vkrEpWwutFToXieAKH5e1MTL0n9AzWtsXgPiQZn465BJTo8QHG3W9/65bvcFRrQYp4d2+wot4XQIlsuuQRN/JHs6GjF/H8OCv7jKDuAJxKRkP5IMBhEY4fuRYOi72Q9cIQ1laK3X41oK4oIJdRZAt6AzxmBXNoD/+5Qf6amJwQCfwxDwzZ/8mfBElcLGnhWN2cwVgw07PhePU6OxJCX6ZJvAtZUi3kIV7DcnWaeoQNkj+jZECn5QFGijWIXmujdkqVAvKqWknpNwKJyrNtHfauJJAApnwwl9S6Mrpvu063XPBOMGxS6EcB2Mprb5R99BJRRezLtF4L2UJUHMVsAvVwbMa5nu/F9Slljx5pAAAAMAAAMAA4sAAAB4QZokbEL//oywAAAKFgMSYZr6Cyd9E7Ds4xP/4wAmrkRKdg8bGUf2KfA/dichGm9fPieY+KIowCPnGpH0YrfZZXVIqJd76G/fJRwvWjAOi/zPD7HxRpYzuN7NylijBoA9/vAyC2TAAOlx6fX1oX8rMuUDPt72rLiAAAAAQ0GeQniEfwAAFqsUiEUmGPDXOaQdSvU051ZGaIOfDp0D4Y47cLcEADVIkxvfg3/LYJjJ32iGAAADAAAL/52QO8qgomcAAAAzAZ5hdEf/AAAjrD5s3j6jn9ztjJgIyl+Tng34+Y+3v6OB2QAAAwAAAwBvkbH72UfeyKqAAAAALQGeY2pH/wAAI78dLBoMhDoI8Os5SiHg+4ybh+gjehlgAAADAEf1KuWFwAB8wQAAAKtBmmhJqEFomUwIX//+jLAAAEYxNF6HRkQAtdace/YesIq3rwN8jr2Zl6hd2oNNDOsQPM2w8m2mPUcKVLUwhRXFFJ9nwuqSdvNVR3OeDTORR3BZtBiKFvgERHWufgl27p9K/YAiesvGhcysg55x6WRFPcuuFLQbyevuhHxukX7krE0bbF4PDrKyxXhP8w4+5elL1XuIf+g1IzCTFZgl6qa4O+dFmfUtGElk1HEAAAA5QZ6GRREsI/8AABa1KzdrPjmcZEq/NWHBhtAD5b2qx8gjVpFm20bj/d8tTvb+QL6tX9xD4G3rCtAxAAAAMgGepXRH/wAAI8MXaFURC0RtV/XaZLUaGY2ef10atj2vFni4HbVglep/K3IuF3GIDdHzAAAAMQGep2pH/wAABR5FOOifnF2TWTJwrcXF8FUZoAD74gLvtNJv5WqEAvDjA9J6NJfPe+AAAADDQZqsSahBbJlMCFf//jhAAAENTskngAWseDzuTw3+uNmucesVGSABAIeC3HRD+2ac1xxtTqYNjQ4OH0/wASFjQ3kT79axuF87IjL0aPjr2mDpOKdsfvwAIIn1nlR8jFulsPZP/xCJGwZ4tOCCDbGkqfHmMzE76aPZxREQDpmHt0RHdRvQeXGlyxNVeS2Pu1viemMrnVRBPxNY5/9zsrKwlWklosjF/QYj1UU39hCM2Imx3BQdNDW9urHN5E+dbtOoDBg/AAAAYEGeykUVLCP/AAAWbk8t3lIpr7pRb0651RIZK7BPrvpVo3W74QNmNiRMukJpMilUsf7ZR6kCVssiniyILCOs1It+k5hnaVmrPk+UwELl9Had3FV8+oh2HsQ0nYLxedjegQAAADMBnul0R/8AACPDF2ipoLQL7P1uHF9YMpGzqBpr9c7ZKtGKrpEt/kkisBzIUUdMzKVr1DwAAABLAZ7rakf/AAAjrpIB2Uw4mABLVOprYWQOpTrNospUXE+iV5cXs54MnsULco8nZNHdTBt5pHj8mwUGF0Hf14bVNWtWefHjL3RsACkgAAAAv0Ga70moQWyZTAj//IQAAA/YXMG1X4cscVByT3da96K+CYOAWCar+iFVFYrh4PAACykPTcfaue1U+xAPv20q6CGw3EVlJLJbOIkex6/jiJRPWy2O6bA19nSoW0wG5fxTjO09uQbX8nZaduvwq3G95qLytvlIb8dPqGD8fUTLfe7JqyW4dR5rhwcd9NBSxBB5gyr6MNz5IDZPBpcRSoGk3h5gt0UcCCQo/wyLDKWX7FhRhjWTNl2lbTac3lkM+JpnAAAAdUGfDkI//wAAI703TPN9UcIhzBgAtGe9jfnS8vLNarQv42hIF5GretePo7VZBz+YJ6qjV3/xkwaXvKmT9q6jeXHI5GbzxE8BdxHMHnyWwztgaPjMO3dmCWbljgjnb2fhtfBOQt0FzxD+SvZQ+1L4gPAtnRCN6QAAAF0Bny1pEf8AACOp5IXR6sSmat6ND7qc10HeLpii+JdylzmTcpcoxuts5BipqFBiC36gZu0H5aGr49y1DRHPXUGAAIQuhUwhb+yS7hCD1prLrDieWO4vrugQx7xaRcEAAAPTbW9vdgAAAGxtdmhkAAAAAAAAAAAAAAAAAAAD6AAAAUAAAQAAAQAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAgAAAv10cmFrAAAAXHRraGQAAAADAAAAAAAAAAAAAAABAAAAAAAAAUAAAAAAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAABAAAAAAlgAAAGQAAAAAAAkZWR0cwAAABxlbHN0AAAAAAAAAAEAAAFAAAACAAABAAAAAAJ1bWRpYQAAACBtZGhkAAAAAAAAAAAAAAAAAAAyAAAAEABVxAAAAAAALWhkbHIAAAAAAAAAAHZpZGUAAAAAAAAAAAAAAABWaWRlb0hhbmRsZXIAAAACIG1pbmYAAAAUdm1oZAAAAAEAAAAAAAAAAAAAACRkaW5mAAAAHGRyZWYAAAAAAAAAAQAAAAx1cmwgAAAAAQAAAeBzdGJsAAAAmHN0c2QAAAAAAAAAAQAAAIhhdmMxAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAAAlgBkABIAAAASAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGP//AAAAMmF2Y0MBZAAf/+EAGWdkAB+s2UCYM+XhAAADAAEAAAMAZA8YMZYBAAZo6+PLIsAAAAAYc3R0cwAAAAAAAAABAAAAEAAAAQAAAAAUc3RzcwAAAAAAAAABAAAAAQAAAJBjdHRzAAAAAAAAABAAAAABAAACAAAAAAEAAAUAAAAAAQAAAgAAAAABAAAAAAAAAAEAAAEAAAAAAQAABQAAAAABAAACAAAAAAEAAAAAAAAAAQAAAQAAAAABAAAFAAAAAAEAAAIAAAAAAQAAAAAAAAABAAABAAAAAAEAAAQAAAAAAQAAAgAAAAABAAAAAAAAABxzdHNjAAAAAAAAAAEAAAABAAAAEAAAAAEAAABUc3RzegAAAAAAAAAAAAAAEAAABKYAAAB8AAAARwAAADcAAAAxAAAArwAAAD0AAAA2AAAANQAAAMcAAABkAAAANwAAAE8AAADDAAAAeQAAAGEAAAAUc3RjbwAAAAAAAAABAAAAMAAAAGJ1ZHRhAAAAWm1ldGEAAAAAAAAAIWhkbHIAAAAAAAAAAG1kaXJhcHBsAAAAAAAAAAAAAAAALWlsc3QAAAAlqXRvbwAAAB1kYXRhAAAAAQAAAABMYXZmNTYuNDAuMTAx\" type=\"video/mp4\" />\n",
       "                 </video>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display = Display(visible=0, size=(1400, 900))\n",
    "display.start()\n",
    "\n",
    "def show_video():\n",
    "    html = []\n",
    "    for mp4 in Path(\"videos\").glob(\"*.mp4\"):\n",
    "        video_b64 = base64.b64encode(mp4.read_bytes())\n",
    "        html.append('''<video alt=\"{}\" autoplay \n",
    "                      loop controls style=\"height: 400px;\">\n",
    "                      <source src=\"data:video/mp4;base64,{}\" type=\"video/mp4\" />\n",
    "                 </video>'''.format(mp4, video_b64.decode('ascii')))\n",
    "    ipythondisplay.display(ipythondisplay.HTML(data=\"<br>\".join(html)))\n",
    "    \n",
    "env = Monitor(env, './videos', force=True, video_callable=lambda episode: True)\n",
    "\n",
    "for episode in range(2):\n",
    "    done = False\n",
    "    obs = env.reset()\n",
    "    while not done:\n",
    "        action = env.action_space.sample()\n",
    "        obs, reward, done, info = env.step(action)\n",
    "env.close()\n",
    "show_video()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see the episode ending prematurely because the pole drops."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "<font color='#ed7d31'>**Question**:</font>\n",
    "\n",
    "It is also important to identify some of the characteristics of the problem. `CartPole-v0` can be described as a **fully-observable**, **deterministic**, **continuous state space**, with a **discrete action space** and **frequent rewards**. Take some time to understand each of these terms :-) Try to find the opposite term for each of them, e.g. deterministic <> stochastic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Experience Replay Memory</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As usual RL tasks have no pre-generated training sets which they can learn from, in off-policy learning, our agent must keep records of all the state-transitions it encountered so it can **learn from them later**. The memory-buffer used to store this is often referred to as the **Experience Replay Memory**. There are several types and architectures of these memory buffers — but some very common ones are:\n",
    "- the *cyclic memory buffers*: they make sure the agent keeps training over its new behavior rather than things that might no longer be relevant\n",
    "- the *reservoir-sampling-based memory buffers*: they guarantee each state-transition recorded has an even probability to be inserted to the buffer\n",
    "\n",
    "We use a combination of both.\n",
    "\n",
    "In `push`:\n",
    "1. Append the transition to memory\n",
    "2. Create the if statement which deletes an old transition from the memory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ExperienceReplayMemory:\n",
    "    def __init__(self, capacity):\n",
    "        self.capacity = capacity\n",
    "        self.memory = []\n",
    "\n",
    "    def push(self, transition):\n",
    "        # Append the transition below\n",
    "        ...\n",
    "        \n",
    "        # Now, we need an `if` statement in order to keep the capacity to its limit. Write it below.\n",
    "        # Hint: `del something` will delete something if something is an array\n",
    "        if ...:\n",
    "            \n",
    "        raise NotImplementedError\n",
    "\n",
    "    def sample(self, batch_size):\n",
    "        return random.sample(self.memory, batch_size)\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.memory)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have:\n",
    "- the **DQN** network,\n",
    "- the **ExperienceReplayMemory**.\n",
    "\n",
    "Let's build the **Agent** class !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Agent declaration</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the cell below:\n",
    "1. Create `self.target_model` in `declare_networks`\n",
    "2. Complete the epsilon-greedy algorithm in `get_action`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Agent(object):\n",
    "    def __init__(self, config, env, log_dir='/tmp/gym'):\n",
    "        self.log_dir = log_dir\n",
    "        self.rewards = []\n",
    "        self.action_log_frequency = config.ACTION_SELECTION_COUNT_FREQUENCY\n",
    "        self.action_selections = [0 for _ in range(env.action_space.n)]\n",
    "    \n",
    "    # Define the DQN networks\n",
    "    def declare_networks(self):\n",
    "        self.model = DQN(self.num_feats, self.num_actions)\n",
    "        # Create `self.target_model` with the same network architecture\n",
    "        self.target_model = ...\n",
    "        raise NotImplementedError\n",
    "\n",
    "    # Define the Replay Memory\n",
    "    def declare_memory(self):\n",
    "        self.memory = ExperienceReplayMemory(self.experience_replay_size)\n",
    "    \n",
    "    # Append the new transition to the Replay Memory\n",
    "    def append_to_replay(self, s, a, r, s_):\n",
    "        self.memory.push((s, a, r, s_))\n",
    "    \n",
    "    # Sample transitions from the Replay Memory\n",
    "    def sample_minibatch(self):\n",
    "        transitions = self.memory.sample(self.batch_size)\n",
    "        batch_state, batch_action, batch_reward, batch_next_state = zip(*transitions)\n",
    "\n",
    "        shape = (-1,)+self.num_feats\n",
    "\n",
    "        batch_state = torch.tensor(batch_state, device=self.device, dtype=torch.float).view(shape)\n",
    "        batch_action = torch.tensor(batch_action, device=self.device, dtype=torch.long).squeeze().view(-1, 1)\n",
    "        batch_reward = torch.tensor(batch_reward, device=self.device, dtype=torch.float).squeeze().view(-1, 1)\n",
    "        \n",
    "        non_final_mask = torch.tensor(tuple(map(lambda s: s is not None, batch_next_state)), device=self.device, dtype=torch.uint8)\n",
    "        # Sometimes all next states are false\n",
    "        try:\n",
    "            non_final_next_states = torch.tensor([s for s in batch_next_state if s is not None], device=self.device, dtype=torch.float).view(shape)\n",
    "            empty_next_state_values = False\n",
    "        except:\n",
    "            non_final_next_states = None\n",
    "            empty_next_state_values = True\n",
    "\n",
    "        return batch_state, batch_action, batch_reward, non_final_next_states, non_final_mask, empty_next_state_values\n",
    "    \n",
    "    # Sample action\n",
    "    def get_action(self, s, eps=0.1):\n",
    "        with torch.no_grad():\n",
    "            # Epsilon-greedy\n",
    "            if np.random.random() >= eps:\n",
    "                X = torch.tensor([s], device=self.device, dtype=torch.float)\n",
    "                a = self.model(X).max(1)[1].view(1, 1)\n",
    "                return a.item()\n",
    "            else:\n",
    "                ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "<font color='#ed7d31'>**Question**:</font>\n",
    "\n",
    "Remember we define the objective function as\n",
    "\\begin{equation}\n",
    "J=\\left(r+\\gamma \\max _{a^{\\prime}} Q\\left(s^{\\prime}, a^{\\prime}, \\mathbf{\\theta}^{-}\\right)-Q(s, a, \\mathbf{\\theta})\\right)^{2},\n",
    "\\end{equation}\n",
    "where $\\theta^{-}$ are the target parameters.\n",
    "\n",
    "Why do we need a target network in the first place ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Learning</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the cell below, and from the above objective fonction:\n",
    "1. Write the value `expected_q_values`\n",
    "2. Write `diff`\n",
    "3. The `update` function needs some work"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Learning(Agent):\n",
    "    def __init__(self, env=None, config=None, log_dir='/tmp/gym'):\n",
    "        super().__init__(config=config, env=env, log_dir=log_dir)\n",
    "    \n",
    "    # Compute loss from the Bellman Optimality Equation\n",
    "    def compute_loss(self, batch_vars):\n",
    "        batch_state, batch_action, batch_reward, non_final_next_states, non_final_mask, empty_next_state_values = batch_vars\n",
    "\n",
    "        # Estimate\n",
    "        current_q_values = self.model(batch_state).gather(1, batch_action)\n",
    "        \n",
    "        # Target\n",
    "        with torch.no_grad():\n",
    "            max_next_q_values = torch.zeros(self.batch_size, device=self.device, dtype=torch.float).unsqueeze(dim=1)\n",
    "            if not empty_next_state_values:\n",
    "                max_next_action = self.get_max_next_state_action(non_final_next_states)\n",
    "                max_next_q_values[non_final_mask] = self.target_model(non_final_next_states).gather(1, max_next_action)\n",
    "        # From the equation above, write the value `expected_q_values`.\n",
    "            expected_q_values = ...\n",
    "        \n",
    "        # From the equation above, write the value `diff`.\n",
    "        diff = ...\n",
    "        loss = self.MSE(diff)\n",
    "        loss = loss.mean()\n",
    "        \n",
    "        raise NotImplementedError\n",
    "        return loss\n",
    "\n",
    "    # Update both networks (the agent and the target)\n",
    "    def update(self, s, a, r, s_, sample_idx=0):\n",
    "        self.append_to_replay(s, a, r, s_)\n",
    "        \n",
    "        # When not to update ?\n",
    "        # There is a concise way to write to skip the update, fill in the 2 blanks in the `if` statement below.\n",
    "        # Hint: the sample count should be < the learn_start hyperparameter and respect the update_freq.\n",
    "        if ... or ...:\n",
    "            raise NotImplementedError\n",
    "            return None\n",
    "\n",
    "        batch_vars = self.sample_minibatch()\n",
    "        loss = self.compute_loss(batch_vars)\n",
    "\n",
    "        # Optimize the model\n",
    "        self.optimizer.zero_grad()\n",
    "        loss.backward()\n",
    "        for param in self.model.parameters():\n",
    "            param.grad.data.clamp_(-1, 1)\n",
    "        self.optimizer.step()\n",
    "\n",
    "        self.update_target_model()\n",
    "        self.save_td(loss.item(), sample_idx)\n",
    "\n",
    "    def update_target_model(self):\n",
    "        # Copy weights from model to target_model following `target_net_update_freq`.\n",
    "        self.update_count+=1\n",
    "        if self.update_count % self.target_net_update_freq == 0:\n",
    "            self.target_model.load_state_dict(self.model.state_dict())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Model declaration</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Model(Learning):\n",
    "    def __init__(self, env=None, config=None, log_dir='/tmp/gym'):\n",
    "        super().__init__(config=config, env=env, log_dir=log_dir)\n",
    "        self.device = config.device\n",
    "\n",
    "        # Hyperparameters\n",
    "        self.gamma = config.GAMMA\n",
    "        self.target_net_update_freq = config.TARGET_NET_UPDATE_FREQ\n",
    "        self.experience_replay_size = config.EXP_REPLAY_SIZE\n",
    "        self.batch_size = config.BATCH_SIZE\n",
    "        self.learn_start = config.LEARN_START\n",
    "        self.update_freq = config.UPDATE_FREQ\n",
    "\n",
    "        # Environment specific parameters\n",
    "        self.num_feats = env.observation_space.shape\n",
    "        self.num_actions = env.action_space.n\n",
    "        self.env = env\n",
    "\n",
    "        self.declare_networks()\n",
    "        self.declare_memory()\n",
    "        self.target_model.load_state_dict(self.model.state_dict())\n",
    "        self.optimizer = optim.Adam(self.model.parameters(), lr=config.LR)\n",
    "        \n",
    "        # Move to correct device\n",
    "        self.model = self.model.to(self.device)\n",
    "        self.target_model.to(self.device)\n",
    "        \n",
    "        self.model.train()\n",
    "        self.target_model.train()\n",
    "        \n",
    "        self.update_count = 0\n",
    "            \n",
    "    def save_td(self, td, tstep):\n",
    "        with open(os.path.join(self.log_dir, 'td.csv'), 'a') as f:\n",
    "            writer = csv.writer(f)\n",
    "            writer.writerow((tstep, td))\n",
    "\n",
    "    def get_max_next_state_action(self, next_states):\n",
    "        return self.target_model(next_states).max(dim=1)[1].view(-1, 1)\n",
    "    \n",
    "    def MSE(self, x):\n",
    "        return 0.5 * x.pow(2)\n",
    "\n",
    "    def save_reward(self, reward):\n",
    "        self.rewards.append(reward)\n",
    "\n",
    "    def save_action(self, action, tstep):\n",
    "        self.action_selections[int(action)] += 1.0/self.action_log_frequency\n",
    "        if (tstep+1) % self.action_log_frequency == 0:\n",
    "            with open(os.path.join(self.log_dir, 'action_log.csv'), 'a') as f:\n",
    "                writer = csv.writer(f)\n",
    "                writer.writerow(list([tstep]+self.action_selections))\n",
    "            self.action_selections = [0 for _ in range(len(self.action_selections))]\n",
    "            \n",
    "    def save_w(self):\n",
    "        if not os.path.exists(\"../saved_agents\"):\n",
    "            os.makedirs(\"../saved_agents\")\n",
    "        torch.save(self.model.state_dict(), '../saved_agents/model.dump')\n",
    "        torch.save(self.optimizer.state_dict(), '../saved_agents/optim.dump')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Hyperparameters</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Config(object):\n",
    "    def __init__(self):\n",
    "        self.device = torch.device(\"cuda\" if torch.cuda.is_available() else \"cpu\")\n",
    "        \n",
    "        # Main agent variables\n",
    "        self.GAMMA=0.99\n",
    "        self.LR=1e-3\n",
    "        \n",
    "        # Epsilon variables\n",
    "        self.epsilon_start    = 1.0\n",
    "        self.epsilon_final    = 0.01\n",
    "        self.epsilon_decay    = 10000\n",
    "        self.epsilon_by_sample = lambda sample_idx: config.epsilon_final + (config.epsilon_start - config.epsilon_final) * math.exp(-1. * sample_idx / config.epsilon_decay)\n",
    "\n",
    "        # Memory\n",
    "        self.TARGET_NET_UPDATE_FREQ = 1000\n",
    "        self.EXP_REPLAY_SIZE = 10000\n",
    "        self.BATCH_SIZE = 64\n",
    "\n",
    "        # Learning control variables\n",
    "        self.LEARN_START = 1000\n",
    "        self.MAX_SAMPLES = 50000\n",
    "        self.UPDATE_FREQ = 1\n",
    "\n",
    "        # Data logging parameters\n",
    "        self.ACTION_SELECTION_COUNT_FREQUENCY = 1000\n",
    "        \n",
    "        \n",
    "config = Config()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Training</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "from openai_monitor import Monitor\n",
    "from IPython import display\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "start=timer()\n",
    "\n",
    "log_dir = \"/tmp/gym/\"\n",
    "try:\n",
    "    os.makedirs(log_dir)\n",
    "except OSError:\n",
    "    files = glob.glob(os.path.join(log_dir, '*.monitor.csv')) \\\n",
    "        + glob.glob(os.path.join(log_dir, '*td.csv')) \\\n",
    "        + glob.glob(os.path.join(log_dir, '*action_log.csv'))\n",
    "    for f in files:\n",
    "        os.remove(f)\n",
    "\n",
    "env_id = 'CartPole-v0'\n",
    "env    = gym.make(env_id)\n",
    "env    = Monitor(env, os.path.join(log_dir, env_id))\n",
    "        \n",
    "model  = Model(env=env, config=config, log_dir=log_dir)\n",
    "\n",
    "episode_reward = 0\n",
    "\n",
    "observation = env.reset()\n",
    "for sample_idx in range(1, config.MAX_SAMPLES + 1):\n",
    "    \n",
    "    epsilon = config.epsilon_by_sample(sample_idx)\n",
    "\n",
    "    action = model.get_action(observation, epsilon)\n",
    "    # Log action selection\n",
    "    model.save_action(action, sample_idx)\n",
    "\n",
    "    prev_observation=observation\n",
    "    observation, reward, done, _ = env.step(action)\n",
    "    observation = None if done else observation\n",
    "\n",
    "    model.update(prev_observation, action, reward, observation, sample_idx)\n",
    "    episode_reward += reward\n",
    "\n",
    "    if done:\n",
    "        observation = env.reset()\n",
    "        model.save_reward(episode_reward)\n",
    "        episode_reward = 0\n",
    "    if sample_idx % 1000 == 0:\n",
    "        try:\n",
    "            clear_output(True)\n",
    "            plot_all_data(log_dir, env_id, 'DQN', config.MAX_SAMPLES, bin_size=(10, 100, 100, 1), smooth=1, time=timedelta(seconds=int(timer()-start)), ipynb=True)\n",
    "        except IOError:\n",
    "            pass\n",
    "\n",
    "model.save_w()\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By observing the plots, does the learning appear to be stable?\n",
    "\n",
    "If your answer is *yes*, then start a second run, and a third, with the same hyperparameters. ;-)\n",
    "\n",
    "You have just faced reproducibility concerns, which is quite a serious problem in deep RL and which can be dealt with by e.g. running your experiments on a sufficient number of seeds (~ 6-8 min.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color='#ed7d31'>Visualize the agent</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from gym.wrappers import Monitor\n",
    "\n",
    "# Loading the agent\n",
    "fname_model = \"../saved_agents/model.dump\"\n",
    "fname_optim = \"../saved_agents/optim.dump\"\n",
    "log_dir = \"/tmp/gym/\"\n",
    "\n",
    "model  = Model(env=env, config=config, log_dir=log_dir)\n",
    "\n",
    "if os.path.isfile(fname_model):\n",
    "    model.model.load_state_dict(torch.load(fname_model))\n",
    "    model.target_model.load_state_dict(model.model.state_dict())\n",
    "\n",
    "if os.path.isfile(fname_optim):\n",
    "    model.optimizer.load_state_dict(torch.load(fname_optim))\n",
    "\n",
    "env_id = 'CartPole-v0'\n",
    "env    = gym.make(env_id)\n",
    "env    = Monitor(env, './videos', force=True, video_callable=lambda episode: True)\n",
    "\n",
    "for episode in range(3):\n",
    "    done = False\n",
    "    obs = env.reset()\n",
    "    while not done:\n",
    "        action = model.get_action(obs)\n",
    "        obs, _, done, _ = env.step(action)\n",
    "\n",
    "env.close()\n",
    "show_video()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can experiment with modifying the hypermarameters (learning rate, batch size, experience replay size, etc.) to see if you can make its performance improve !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-------------"
   ]
  }
 ],
 "metadata": {
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}