Very quick roadmap to Asynchronous Advantage Actor Critic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Very Quick Roadmap to\n",
    "# Asynchronous Advantage Actor Critic (A3C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![input-to-nn-channel-combined](./img/snaps-0-1-2-3-x2.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "start_time": "2019-07-17T02:39:50.642Z"
    }
   },
   "source": [
    "<h1>Tabla de contenidos<span class=\"tocSkip\"></span></h1>\n",
    "\n",
    "<div class=\"toc\">\n",
    "    <ul class=\"toc-item\">\n",
    "        <li><span><a href=\"#Aproximación-de-Funciones-(Function-Approximation)\" data-toc-modified-id=\"Aproximación-de-Funciones-(Function-Approximation)-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Aproximación de Funciones (<em>Function Approximation</em>)</a>\n",
    "            </span>\n",
    "            <ul class=\"toc-item\">\n",
    "                <li><span><a href=\"#Value-Function\" data-toc-modified-id=\"Value-Function-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Value Function</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Tabular\" data-toc-modified-id=\"Tabular-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Tabular</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Curse-of-dimensionality\" data-toc-modified-id=\"Curse-of-dimensionality-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Curse of dimensionality</a>\n",
    "                            </span>\n",
    "                            <ul class=\"toc-item\">\n",
    "                                <li><span><a href=\"#Simulación\" data-toc-modified-id=\"Simulación-1.2.1.1\"><span class=\"toc-item-num\">1.2.1.1&nbsp;&nbsp;</span>Simulación</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Entrenar-agente\" data-toc-modified-id=\"Entrenar-agente-1.2.1.2\"><span class=\"toc-item-num\">1.2.1.2&nbsp;&nbsp;</span>Entrenar agente</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Solo-visualización\" data-toc-modified-id=\"Solo-visualización-1.2.1.3\"><span class=\"toc-item-num\">1.2.1.3&nbsp;&nbsp;</span>Solo visualización</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Extra-commands\" data-toc-modified-id=\"Extra-commands-1.2.1.4\"><span class=\"toc-item-num\">1.2.1.4&nbsp;&nbsp;</span>Extra commands</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                            </ul>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Aproximación-de-Función-de-Valor\" data-toc-modified-id=\"Aproximación-de-Función-de-Valor-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Aproximación de Función de Valor</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Aproximador-Lineal\" data-toc-modified-id=\"Aproximador-Lineal-1.3.1\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Aproximador Lineal</a>\n",
    "                            </span>\n",
    "                            <ul class=\"toc-item\">\n",
    "                                <li><span><a href=\"#Entrenar-agente\" data-toc-modified-id=\"Entrenar-agente-1.3.1.1\"><span class=\"toc-item-num\">1.3.1.1&nbsp;&nbsp;</span>Entrenar agente</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Solo-visualización\" data-toc-modified-id=\"Solo-visualización-1.3.1.2\"><span class=\"toc-item-num\">1.3.1.2&nbsp;&nbsp;</span>Solo visualización</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                            </ul>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Funciones-Diferenciables-no-Lineales:-Redes-Neuronales\" data-toc-modified-id=\"Funciones-Diferenciables-no-Lineales:-Redes-Neuronales-1.3.2\"><span class=\"toc-item-num\">1.3.2&nbsp;&nbsp;</span>Funciones Diferenciables no-Lineales: <em>Redes Neuronales</em></a>\n",
    "                            </span>\n",
    "                            <ul class=\"toc-item\">\n",
    "                                <li><span><a href=\"#Pseudocodigo-para-one-step-Q-learning-con-NN\" data-toc-modified-id=\"Pseudocodigo-para-one-step-Q-learning-con-NN-1.3.2.1\"><span class=\"toc-item-num\">1.3.2.1&nbsp;&nbsp;</span>Pseudocodigo para one step Q-learning con NN</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                            </ul>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Extensiones\" data-toc-modified-id=\"Extensiones-1.3.3\"><span class=\"toc-item-num\">1.3.3&nbsp;&nbsp;</span>Extensiones</a>\n",
    "                            </span>\n",
    "                            <ul class=\"toc-item\">\n",
    "                                <li><span><a href=\"#DQN-con-Atari\" data-toc-modified-id=\"DQN-con-Atari-1.3.3.1\"><span class=\"toc-item-num\">1.3.3.1&nbsp;&nbsp;</span>DQN con Atari</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Multi-step-Return\" data-toc-modified-id=\"Multi-step-Return-1.3.3.2\"><span class=\"toc-item-num\">1.3.3.2&nbsp;&nbsp;</span>Multi-step Return</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#n-como-hiperparámetro\" data-toc-modified-id=\"n-como-hiperparámetro-1.3.3.3\"><span class=\"toc-item-num\">1.3.3.3&nbsp;&nbsp;</span>n como hiperparámetro</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                            </ul>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Policy-Approximation\" data-toc-modified-id=\"Policy-Approximation-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Policy Approximation</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Actor-Critic\" data-toc-modified-id=\"Actor-Critic-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Actor-Critic</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Ventajas\" data-toc-modified-id=\"Ventajas-1.5.1\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Ventajas</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Loss-and-Gradient\" data-toc-modified-id=\"Loss-and-Gradient-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Loss and Gradient</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Policy-Objective-Functions-(-funciones-objetivo-para-las-políticas)\" data-toc-modified-id=\"Policy-Objective-Functions-(-funciones-objetivo-para-las-políticas)-1.6.1\"><span class=\"toc-item-num\">1.6.1&nbsp;&nbsp;</span>Policy Objective Functions ( funciones objetivo para las políticas)</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#How-to-sample\" data-toc-modified-id=\"How-to-sample-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>How to sample</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Toy-example\" data-toc-modified-id=\"Toy-example-1.7.1\"><span class=\"toc-item-num\">1.7.1&nbsp;&nbsp;</span>Toy example</a>\n",
    "                            </span>\n",
    "                            <ul class=\"toc-item\">\n",
    "                                <li><span><a href=\"#&quot;Score-function-trick&quot;-o-&quot;REINFORCE-trick&quot;-o-&quot;log-likelihood-trick&quot;\" data-toc-modified-id=\"&quot;Score-function-trick&quot;-o-&quot;REINFORCE-trick&quot;-o-&quot;log-likelihood-trick&quot;-1.7.1.1\"><span class=\"toc-item-num\">1.7.1.1&nbsp;&nbsp;</span>\"Score function trick\" o \"REINFORCE trick\" o \"log-likelihood trick\"</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                                <li><span><a href=\"#Demostración\" data-toc-modified-id=\"Demostración-1.7.1.2\"><span class=\"toc-item-num\">1.7.1.2&nbsp;&nbsp;</span>Demostración</a>\n",
    "                                    </span>\n",
    "                                </li>\n",
    "                            </ul>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Ejemplo-concreto-de-update-con-política-Softmax-(se-usa-a-menudo)\" data-toc-modified-id=\"Ejemplo-concreto-de-update-con-política-Softmax-(se-usa-a-menudo)-1.7.2\"><span class=\"toc-item-num\">1.7.2&nbsp;&nbsp;</span>Ejemplo concreto de update con política <em>Softmax</em> (se usa a menudo)</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Queremos-extenderlo-al-caso-multi-step,-donde\" data-toc-modified-id=\"Queremos-extenderlo-al-caso-multi-step,-donde-1.7.3\"><span class=\"toc-item-num\">1.7.3&nbsp;&nbsp;</span>Queremos extenderlo al caso multi-step, donde</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Policy-Gradient-Theorem-(con-demostración)\" data-toc-modified-id=\"Policy-Gradient-Theorem-(con-demostración)-1.8\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>Policy Gradient Theorem (con demostración)</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Teorema:\" data-toc-modified-id=\"Teorema:-1.8.1\"><span class=\"toc-item-num\">1.8.1&nbsp;&nbsp;</span>Teorema:</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Policy-Gradient-sobre-trayectorias\" data-toc-modified-id=\"Policy-Gradient-sobre-trayectorias-1.9\"><span class=\"toc-item-num\">1.9&nbsp;&nbsp;</span>Policy Gradient sobre trayectorias</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Baselines\" data-toc-modified-id=\"Baselines-1.9.1\"><span class=\"toc-item-num\">1.9.1&nbsp;&nbsp;</span>Baselines</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Baselines,-again\" data-toc-modified-id=\"Baselines,-again-1.9.2\"><span class=\"toc-item-num\">1.9.2&nbsp;&nbsp;</span>Baselines, again</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Terreno-conocido\" data-toc-modified-id=\"Terreno-conocido-1.9.3\"><span class=\"toc-item-num\">1.9.3&nbsp;&nbsp;</span>Terreno conocido</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "            </ul>\n",
    "        </li>\n",
    "        <li><span><a href=\"#Actor-Critic:-Pseudocódigo-e-Implementación\" data-toc-modified-id=\"Actor-Critic:-Pseudocódigo-e-Implementación-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Actor-Critic: Pseudocódigo e Implementación</a>\n",
    "            </span>\n",
    "            <ul class=\"toc-item\">\n",
    "                <li><span><a href=\"#Vanilla-Actor-Critic\" data-toc-modified-id=\"Vanilla-Actor-Critic-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Vanilla Actor-Critic</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Advantage-Actor-Critic:-Detalles-de-implementación\" data-toc-modified-id=\"Advantage-Actor-Critic:-Detalles-de-implementación-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Advantage Actor-Critic: Detalles de implementación</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "            </ul>\n",
    "        </li>\n",
    "        <li><span><a href=\"#Asynchronous-Advantage-Actor-Critic-(A3C)---Código\" data-toc-modified-id=\"Asynchronous-Advantage-Actor-Critic-(A3C)-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Asynchronous Advantage Actor Critic (A3C) - Código</a>\n",
    "            </span>\n",
    "        </li>\n",
    "        <li><span><a href=\"#Acerca-de-la-implementación\" data-toc-modified-id=\"Acerca-de-la-implementación-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Acerca de la implementación</a>\n",
    "            </span>\n",
    "            <ul class=\"toc-item\">\n",
    "                <li><span><a href=\"#Modificaciones-particulares:\" data-toc-modified-id=\"Modificaciones-particulares:-4.1\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>Modificaciones particulares:</a>\n",
    "                    </span>\n",
    "                    <ul class=\"toc-item\">\n",
    "                        <li><span><a href=\"#Input\" data-toc-modified-id=\"Input-4.1.1\"><span class=\"toc-item-num\">4.1.1&nbsp;&nbsp;</span>Input</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                        <li><span><a href=\"#Dropout:\" data-toc-modified-id=\"Dropout:-4.1.2\"><span class=\"toc-item-num\">4.1.2&nbsp;&nbsp;</span>Dropout:</a>\n",
    "                            </span>\n",
    "                        </li>\n",
    "                    </ul>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Dive-into-code\" data-toc-modified-id=\"Dive-into-code-4.2\"><span class=\"toc-item-num\">4.2&nbsp;&nbsp;</span>Dive into code</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Problem-to-solve\" data-toc-modified-id=\"Problem-to-solve-4.3\"><span class=\"toc-item-num\">4.3&nbsp;&nbsp;</span>Problem to solve</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Estrategias-de-modelado\" data-toc-modified-id=\"Estrategias-de-modelado-4.4\"><span class=\"toc-item-num\">4.4&nbsp;&nbsp;</span>Estrategias de modelado</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "                <li><span><a href=\"#Observaciones\" data-toc-modified-id=\"Observaciones-4.5\"><span class=\"toc-item-num\">4.5&nbsp;&nbsp;</span>Observaciones</a>\n",
    "                    </span>\n",
    "                </li>\n",
    "            </ul>\n",
    "        </li>\n",
    "        <li><span><a href=\"#Conclusión\" data-toc-modified-id=\"Conclusión-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Conclusión</a>\n",
    "            </span>\n",
    "        </li>\n",
    "    </ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aproximación de Funciones (*Function Approximation*)\n",
    "\n",
    "Hasta ahora hemos visto distintas maneras de encontrar soluciones a **Procesos de Decisión Markovianos** (***MDPs***) del tipo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./img/agent-env-diagram.png\" align=\"center\" width=\"500\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para ello, un agente puede aprender y/o hacer uso de\n",
    "- una ***Value Function*** / Función de valor\n",
    "- una ***Policy Function*** / Política de comportamiento\n",
    "- o un ***Modelo*** del Environment / Donde *modelo* será conocer las ***transiciones*** del environment (o un estimado de las mismas)\n",
    "\n",
    "Estas funciones, son esencialmente un *mapeo* (*mapping*) que **reducen la dimensionalidad** del problema: \n",
    "\n",
    "---\n",
    "\n",
    "> desde $\\big[$ `observación` $\\big]$ $\\mapsto$ $\\big[$ `representación con \"mayor nivel de abstracción\"` $\\big]$\n",
    "   \n",
    "---\n",
    "**Particularmente:**\n",
    "\n",
    "- Value Function:\n",
    "\n",
    "> desde $\\big[$ `estados o pares estado-acción` $\\big]$ $\\mapsto$ $\\big[$ `algún valor / puntaje` $\\big]$\n",
    "---\n",
    "- Policy Function:\n",
    "\n",
    "> desde $\\big[$ `estados` $\\big]$ $\\mapsto$ $\\big[$ `acciones` $\\big]$\n",
    ">\n",
    "> desde $\\big[$ `states` $\\big]$ $\\mapsto$ $\\big[$ `actions` $\\big]$\n",
    "\n",
    "---\n",
    "- Modelo: \n",
    "\n",
    "> desde $\\big[$ `estado` $\\big]$ $\\mapsto$ $\\big[$ `siguiente observación o esperanza de` $\\big]$\n",
    "\n",
    "---\n",
    "Queremos aprender estas funciones **directamente desde la experiencia**.\n",
    "\n",
    "----------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Value Function\n",
    "\n",
    "Una opción intuitiva sería usar **Funciones de Valor**, ya que son fáciles de interpretar y de decidir una política a partir de ellas, además de disponer de una teoría más extensa que soporte sus prácticas.\n",
    "\n",
    "### Tabular\n",
    "\n",
    "Los algoritmos más simples, se basan en **soluciones tabulares**, que buscan llevar un **historial** de los estados visitados hasta el momento.\n",
    "\n",
    "El problema con ésto es que la cantidad de estados posible es gigantesca a pesar de estar resolviendo problemas simples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-07T18:49:30.163529Z",
     "start_time": "2019-07-07T18:49:30.026042Z"
    }
   },
   "source": [
    "![pacman-micro-layout](./img/pacman-micro.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Curse of dimensionality\n",
    "\n",
    "Consideremos un mapa (*layout*) de *pac-man* de 5x5 celdas como el de arriba.\n",
    "\n",
    "![pacman-micro-grid](./img/pacman-micro-grid.png)\n",
    "\n",
    "Si contamos las diferentes formas de organizar **solo** las bolitas (*pellets*), existen $2^{25}$ (más de *33 millones*) posibles combinaciones, que para modelos tabulares serán **estados completamente diferentes** uno de otro."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Simulación\n",
    "\n",
    "Llevadolo a la práctica, usando el algoritmo ***Q Learning*** para resolver una versión aún más simple de este mapa (con solo 2 pellets) se necesitan alrededor de **2000 episodios** para aprender a ganar casi con seguridad, pero la cantidad de estados (*states*) guardados en la Q function supera los **8000 elementos** (*<state: value>*), con una fuerte tendencia a seguir aumentando, mientras que el reward promedio se mantiene casi constante:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-07T19:10:28.814430Z",
     "start_time": "2019-07-07T19:10:28.688116Z"
    },
    "cell_style": "split"
   },
   "source": [
    "Entrenado por **2.000 episodios** (juegos):\n",
    "![pacman-2000-ep-plot](./img/q-table-2000-ep.png \"2000 episodes\") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "Luego de **10.000 episodios**:\n",
    "\n",
    "![pacman-10000-ep-plot](./img/q-table-10000-ep.png  \"10000 episodes\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Las siguientes celdas permiten **reproducir los resultados** de arriba al entrenar un agente con *Q learning* por 2000 episodios, y mostrar 3 juegos siguiendo una política *greedy* con respecto a la Value Function aproximada:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Entrenar agente"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T17:05:17.573855Z",
     "start_time": "2019-07-19T17:05:17.569240Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Couldn't change to ./cs188x_pacman folder. Are you already there?\n",
      "Current directory: /home/jack/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/cs188x_pacman\n"
     ]
    }
   ],
   "source": [
    "# Change directory to run pac-man simulator python files on ./cs188x_pacman\n",
    "# Assumes this notebook on main directory\n",
    "import os\n",
    "ORIGINAL_DIR = os.getcwd()\n",
    "try:\n",
    "    cs188x_pacman_dir = './cs188x_pacman'\n",
    "    os.chdir(cs188x_pacman_dir)\n",
    "    original_dir = os.getcwd()[:2-len(cs188x_pacman_dir)]\n",
    "    print(\"Original directory:\\n\",original_dir)\n",
    "    print(\"Moved to:\\n\", os.getcwd())\n",
    "except:\n",
    "    print(\"Couldn't change to ./cs188x_pacman folder. Are you already there?\")\n",
    "    print(\"Current directory:\", os.getcwd())\n",
    "# Or use directly\n",
    "#os.chdir('/home/user/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/cs188x_pacman')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T17:06:27.523793Z",
     "start_time": "2019-07-19T17:05:28.595008Z"
    },
    "cell_style": "center",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Beginning 2000 episodes of Training\n",
      "Episodes\tMean R lifetime / last 50 ep\tTraining time\n",
      "  50/2000\tr: -510.72 / -510.72\t0.60 sec\n",
      " 100/2000\tr: -510.80 / -510.88\t0.60 sec\n",
      " 150/2000\tr: -510.70 / -510.50\t0.59 sec\n",
      " 200/2000\tr: -505.81 / -491.16\t0.76 sec\n",
      " 250/2000\tr: -507.06 / -512.04\t0.90 sec\n",
      " 300/2000\tr: -491.09 / -411.26\t0.88 sec\n",
      " 350/2000\tr: -473.79 / -369.94\t0.76 sec\n",
      " 400/2000\tr: -455.99 / -331.38\t0.75 sec\n",
      " 450/2000\tr: -440.14 / -313.36\t0.88 sec\n",
      " 500/2000\tr: -406.96 / -108.38\t0.92 sec\n",
      " 550/2000\tr: -381.89 / -131.16\t1.04 sec\n",
      " 600/2000\tr: -365.92 / -190.24\t1.26 sec\n",
      " 650/2000\tr: -343.22 / -70.82\t1.01 sec\n",
      " 700/2000\tr: -319.46 / -10.66\t1.04 sec\n",
      " 750/2000\tr: -301.63 / -51.90\t1.17 sec\n",
      " 800/2000\tr: -289.77 / -111.86\t1.02 sec\n",
      " 850/2000\tr: -278.19 / -93.04\t1.10 sec\n",
      " 900/2000\tr: -258.80 / 70.82\t1.12 sec\n",
      " 950/2000\tr: -240.47 / 89.64\t1.22 sec\n",
      "1000/2000\tr: -222.90 / 110.84\t1.50 sec\n",
      "1050/2000\tr: -209.85 / 51.06\t1.44 sec\n",
      "1100/2000\tr: -198.02 / 50.52\t1.20 sec\n",
      "1150/2000\tr: -189.89 / -10.96\t1.40 sec\n",
      "1200/2000\tr: -182.45 / -11.50\t1.79 sec\n",
      "1250/2000\tr: -173.20 / 48.90\t1.69 sec\n",
      "1300/2000\tr: -165.59 / 24.76\t1.96 sec\n",
      "1350/2000\tr: -156.94 / 67.78\t1.53 sec\n",
      "1400/2000\tr: -151.78 / -12.36\t1.21 sec\n",
      "1450/2000\tr: -146.29 / 7.42\t1.10 sec\n",
      "1500/2000\tr: -135.70 / 171.24\t1.40 sec\n",
      "1550/2000\tr: -129.75 / 49.02\t1.38 sec\n",
      "1600/2000\tr: -120.36 / 170.50\t1.19 sec\n",
      "1650/2000\tr: -118.29 / -52.08\t1.17 sec\n",
      "1700/2000\tr: -113.96 / 28.94\t1.02 sec\n",
      "1750/2000\tr: -111.59 / -30.84\t1.06 sec\n",
      "1800/2000\tr: -105.51 / 107.10\t1.13 sec\n",
      "1850/2000\tr: -96.97 / 210.70\t1.22 sec\n",
      "1900/2000\tr: -93.12 / 49.12\t1.11 sec\n",
      "1950/2000\tr: -90.51 / 8.68\t1.11 sec\n",
      "2000/2000\tr: -84.51 / 149.66\t1.19 sec\n",
      "Training Done (turning off epsilon and alpha)\n",
      "---------------------------------------------\n",
      "Plotting Q size over episodes:\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEGCAYAAACUzrmNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nOzdd3hUZfbA8e9JIQmQRkjoEHovQqSDBQVEBNuKYsG+Kq66uuuiW9R13Z9tLdjdVdaCAlawsIJYAKV3CL2HEgKEFNJn3t8f7x0ygTRCJpOQ83mePJm5c+fOmTsz73nbvVeMMSillFKlCfB3AEoppao/TRZKKaXKpMlCKaVUmTRZKKWUKpMmC6WUUmUK8ncAvtCwYUMTHx/v7zCUUqpGWbFixWFjTGxxj52VySI+Pp7ly5f7OwyllKpRRGR3SY9pN5RSSqkyabJQSilVJk0WSimlynRWjlkUJz8/n6SkJHJycvwdSq0SGhpK8+bNCQ4O9ncoSqkzUGuSRVJSEuHh4cTHxyMi/g6nVjDGcOTIEZKSkmjdurW/w1FKnQGfdkOJyO9FZIOIrBeRj0UkVERai8gSEdkqItNFpI6zbohzf5vzeLzXdh5xlm8WkREViSUnJ4eYmBhNFFVIRIiJidHWnFJnAZ8lCxFpBtwHJBhjugGBwLXAM8CLxpj2QCpwm/OU24BUY0w74EVnPUSki/O8rsBI4HURCaxgTBV/Q6pCdJ8rdXbw9QB3EBAmIkFAXeAAcCHwqfP4e8Dlzu2xzn2cx4eJLWnGAtOMMbnGmJ3ANqCvj+NWSqka5VBGDh8s2sW36w74ZPs+G7MwxuwTkeeBPUA2MAdYARwzxhQ4qyUBzZzbzYC9znMLRCQNiHGWL/batPdzapSkpCQmTpxIYmIiLpeLUaNG8a9//YuQkJAi6+3atYtff/2V8ePHl7q9n376ieeff56vv/76lMc8ByY2bNiwwvG++eab1K1bl5tuuqnC21BKnTljDJ+t3Mev2w6z88hxcvPd5Lnc5OS7yM5zcTyvgJx8NwCX9WzKqO5NKj0GnyULEYnGtgpaA8eAT4BLilnVc/Wl4vorTCnLT369O4E7AVq2bFmBiH3LGMOVV17J3XffzcyZM3G5XNx55508/PDDvPzyy0XW3bVrFx999FGZycLX7rrrLr++vlLKlh1//zqRKb/somH9EDo0qk9MvTqEBAUSEhRA3ZBA6tYJIrpuHYZ1jqNDo3CfxOHL2VAXATuNMSkAIvI5MBCIEpEgp3XRHNjvrJ8EtACSnG6rSOCo13IP7+ecYIx5G3gbICEhodpd/u+HH34gNDSUW265BYDAwEBefPFFWrVqxVNPPUX9+vVPrDtp0iQ2btxIr169mDBhAldccQU33ngjx48fB+DVV19l4MCBAKSnp3PFFVewefNmhg4dyuuvv05AQNHexQ8//JDJkyeTl5dHv379eP311wkMLDrsM2nSJGbNmkVQUBDDhw/n+eef5/HHH6d+/fqMHz+eUaNGnVh33bp17Nixg7p163LXXXexZ88eAF566SUGDRpU+TtPqVrAGMP+tBy2HMwgz+VmX2o2K/aksjU5gy3Jmdw6qDV/Hd3Zb+OAvkwWe4D+IlIX2w01DFgO/AhcDUwDJgAznfVnOfcXOY//YIwxIjIL+EhEXgCaAu2BpWcS2BNfbSBxf/qZbOIUXZpG8NhlXUt8fMOGDfTp06fIsoiICOLj49m2bRu9evU6sfzpp58u0r2UlZXF3LlzCQ0NZevWrVx33XUnzn21dOlSEhMTadWqFSNHjuTzzz/n6quvPrGtjRs3Mn36dH755ReCg4O55557mDp1apGupaNHj/LFF1+wadMmRIRjx44VibNp06asXr0agNdee42ff/6ZVq1aMX78eH7/+98zePBg9uzZw4gRI9i4cWMF96BSZ7fjuQXM35JCdr6LfJebjJwCNh/MIC07n+x8FxsPpHM4M6/Ic5pFhdGhUX2uSWjBbYNb+3XCiC/HLJaIyKfASqAAWIWt+X8DTBORfzjL3nGe8g7wgYhsw7YornW2s0FEZgCJznYmGmNcvorbV4wxxX7Q5bkGen5+Pvfeey+rV68mMDCQLVu2nHisb9++tGnTBoDrrruOhQsXFkkW8+bNY8WKFZx77rkAZGdnExcXV2T7ERERhIaGcvvtt3PppZcyevToYuP45Zdf+M9//sOCBQsA+P7770lMTDzxeHp6OhkZGYSH+6YZrFRNdSAtm1umLGPTwYwiyxvWD6Fh/ToEBwZwfsc4ejSPpEuTCEKDA4mpX4cmkWF+ivhUPj0ozxjzGPDYSYt3UMxsJmNMDvCbErbzFPBUZcVVWgvAV7p27cpnn31WZFl6ejrJycl07Nix1Oe++OKLNGrUiDVr1uB2uwkNDT3x2MkJ6OT7xhgmTJjA//3f/5W4/aCgIJYuXcq8efOYNm0ar776Kj/88EORdQ4cOMBtt93GrFmzTnSZud1uFi1aRFhY9flCK1UdzF53gMdmbeBwZi4AbgP1Q4J484Y+dGocTnBQAHWDA4muV8fPkZafnhuqigwbNoysrCzef/99AFwuFw899BD33nvvKYVteHg4GRmFNZC0tDSaNGlCQEAAH3zwAS5XYcNq6dKl7Ny5E7fbzfTp0xk8ePApr/vpp59y6NAhwHY57d5d9CzEmZmZpKWlMWrUKF566aUTXU4e+fn5XHPNNTzzzDN06NDhxPLhw4fz6quvnrh/8vOUqm3cbsPjszZw99SVNIoIZeIF7Zh4QTvuG9aeL+4ZyMhujYlvWI9mUWE1KlFALTrdh7+JCF988QUTJ07kySefJCUlhXHjxvHnP//5lHV79OhBUFAQPXv25Oabb+aee+7hqquu4pNPPuGCCy6gXr16J9YdMGAAkyZNYt26dQwdOpQrrriiyLa6dOnCP/7xD4YPH47b7SY4OJjXXnuNVq1anVgnIyODsWPHkpOTgzGGF198scg2fv31V5YtW8Zjjz3GY4/ZhuK3337L5MmTmThxIj169KCgoIChQ4fy5ptvVuZuU6pGWL7rKMt2pbJm7zH+t+Egtw5qzSOjOhEcePbUx6U8feY1TUJCgjn54kcbN26kc+fOforoVL/++ivXXXcdn3/++SkD32eb6rbvlaosmbkFPPr5OmatsRM0AwOEB4a1594L29XIsxeIyApjTEJxj2nLwk8GDhx4SneQUqrmyMl3cft7y1i2K5X7hrXntsGtCQ0OICSoQmcjqvY0WSilVDkt2XGE2esPsuPwcTYfTOdQRi4vjevF2F418qQSp0WThVJKlcPeo1lMmLKUABHaxNajX+sYLu3RhBFdG/s7tCqhyUIppcpgjOEvX64nUIS5D55H06jaN11ck4VSSjmMMew9ms3inUdYsuMom5PTcbkhJSOXw5m5/G10l1qZKECThVKqFsorcDMn8SCfLE/iWFYe+S5DboGLg2k5HM+zxzE1qFeH7s0iCQ4MoHuzCLo3i2R8v1ZlbPnspcmiCgUGBtK9e3cKCgpo3bo1H3zwAVFRUVUex65duxg9ejTr16+v8tdWyl9y8l3MXL2PDxfvYdPBdPJdhhYNwmjTsD7BgQHUCRKGtI+lbVx9+rVuQPu4+jVy+quvaLKoQmFhYSeOcp4wYQKvvfZasQflVTaXy3XKWWaVqg2MMXy+ch+v/LCVPUezcBvo0iSC24e0oW98A4Z2iCUwQBNCeWiy8JMBAwawdu3aE/efe+45ZsyYQW5uLldccQVPPPEEzz77LKGhodx33338/ve/Z82aNfzwww/MmzePKVOm8OGHH3L33XezbNkysrOzufrqq3niiScAe/GjW2+9lTlz5nDvvffSvn17br31VurWrXvKKUGUqumO5xaw7VAmyek5Jy52k5KRyxer9rFidyo9W0Rxb69mnBsfzeB2DbXFUAG1M1nMngQH11XuNht3h0ueLteqLpeLefPmcdtt9vLjc+bMYevWrSxduhRjDGPGjGH+/PkMHTqUf/3rX9x3330sX76c3Nxc8vPzWbhwIUOGDAHgqaeeokGDBrhcLoYNG8batWvp0aMHAKGhoSxcuBCwpxB55ZVXOO+88/jjH/9Yue9dKT/6dfth7pm6kmNZ+ac81qZhPZ68vBvX921JgLYgzkjtTBZ+kp2dTa9evdi1axd9+vTh4osvBmyymDNnDueccw5gT+y3detWbrrpJlasWEFGRgYhISH07t2b5cuXs2DBAiZPngzAjBkzePvttykoKODAgQMkJiaeSBbjxo0D7IkIjx07xnnnnQfAjTfeyOzZs6v67St1RvIK3Hy5ah+pWXmkZOSyNimNzNwCtiRn0LphPZ6+sgfNosLwXPsrLDiQ1g3raSuiktTOZFHOFkBl84xZpKWlMXr0aF577TXuu+8+jDE88sgj/Pa3vz3lOfHx8UyZMoWBAwfSo0cPfvzxR7Zv307nzp3ZuXMnzz//PMuWLSM6Opqbb76ZnJycE8/1nHCwpGtpKFVT7EjJ5L5pq1i/z160rE5QAN2aRtA0KpTeraJ4eGQnIkKD/Rzl2a12Jgs/i4yMZPLkyYwdO5a7776bESNG8Ne//pXrr7+e+vXrs2/fPoKDg4mLi2Po0KE8//zzvPvuu3Tv3p0HH3yQPn36ICKkp6dTr149IiMjSU5OZvbs2Zx//vmnvF5UVBSRkZEsXLiQwYMHM3Xq1Kp/00pV0IG0bMb/ewm5BS7evKE3QzvEUicwgKCz6IyuNYEmCz8555xz6NmzJ9OmTePGG29k48aNDBgwAID69evz4YcfEhcXx5AhQ3jqqacYMGAA9erVIzQ09MR4Rc+ePTnnnHPo2rUrbdq0KfX611OmTDkxwD1ixIgqeY9KVVRugYuPl+xh7b40Vu05RmZuAZ/cNYDOTSL8HVqtpacoVz6n+16BHXPIc7nZfyybORsOkpKRS4Hb4HIbCtyGfJeb47kuMnPz2Xn4OMnpuTSJDKV+SBCPj+nKoHYN/f0Wznp6inKllF8YY/hkRRIfLt5N4v50Cty2cioCkWHBBAUIgQFCUEAAgQFCvZAgwkOC6NUiihv6t2JI+1g/vwPloclCKVXpklKzmLl6P/O3pLBk51G6NYvgjqFtaFC3DuGhQVzYKY64iNCyN6SqjVqVLHRWUNU7G7s5Vek2HUznhv8s4XBmHq1i6vL3sV25oV8rPc6hhqs1ySI0NJQjR44QExOjCaOKGGM4cuQIoaFag6wN1uw9xvTle/lqzX7q1Qni+weH0i4u3N9hqUpSa5JF8+bNSUpKIiUlxd+h1CqhoaE0b97c32EoH1qXlMZb87fz9doD1K0TyPkdY5k0sjMtY+r6OzRViWpNsggODqZ169b+DkOps0ZugYt7P1rF3MRkwoIDue/Cdtx5Xlvqh9SaYqVW0U9VKXXaClxu7vvYJoo/DO/ATQPj9Qjqs5wmC6XUafvPwp18tyGZv43uwq2DtcVeG+jx8kqp07L/WDaT523l4i6NNFHUIposlFLllpVXwKTP1+FyG/42uou/w1FVSLuhlFIlKnC5+XFzCttTMkk9nsePmw+x9VAmT47tRosGOtupNtFkoZQq0T+/3cS7v+wEICQogEYRobx/a189DUctpMlCKVWsvUez+GDxLq7s3YwnxnQlXGc71Wo6ZqGUOoUxhue+20yACA+P6KSJQmnLQilVaM+RLFbtTeWjJXtYsvMoEy9oS+NIPV2L0mShlHIcTMthxEvzyc53ERkWzP9d2Z1xCS38HZaqJjRZKKUA+HrtfrLzXXx0Rz/6tIomJCjQ3yGpakSThVIKgJmr99OjeSQD2+oV6dSpdIBbKcX2lEzW7UtjTM+m/g5FVVPaslCqFjuSmctjszawJukYImiyUCXyactCRKJE5FMR2SQiG0VkgIg0EJG5IrLV+R/trCsiMllEtonIWhHp7bWdCc76W0Vkgi9jVqq2SMvO58Z3ljI3MZn2ceH8eVRnvdSpKpGvWxYvA/8zxlwtInWAusCjwDxjzNMiMgmYBPwJuARo7/z1A94A+olIA+AxIAEwwAoRmWWMSfVx7EqdlVIycnlwxmqW7DyKMYZ/35TA+R3j/B2WquZ8lixEJAIYCtwMYIzJA/JEZCxwvrPae8BP2GQxFnjf2Is2L3ZaJU2cdecaY446250LjAQ+9lXsSp3NnvnfJhbvOMJNA+K5tEcTereM9ndIqgbwZcuiDZACTBGRnsAK4H6gkTHmAIAx5oCIeKo0zYC9Xs9PcpaVtLwIEbkTuBOgZcuWlftOlDpLrNqTyqcrkrjrvLZMuqSTv8NRNYgvk0UQ0Bv4nTFmiYi8jO1yKokUs8yUsrzoAmPeBt4GSEhIOOVxpWqrhVsPszk5g4Np2Uxftpe48BDuvbCdv8NSNYwvk0USkGSMWeLc/xSbLJJFpInTqmgCHPJa3/tw0ebAfmf5+Sct/8mHcSt1VtianMELc7cwe/1BAAIERnZrzAMXddDrZKvT5rNvjDHmoIjsFZGOxpjNwDAg0fmbADzt/J/pPGUWcK+ITMMOcKc5CeU74J+eWVPAcOARX8WtVE2Xk+/id871sUOCAvjjiI5c368lIUGBhNXRo7JVxfi6evE7YKozE2oHcAt2uu4MEbkN2AP8xln3W2AUsA3IctbFGHNURJ4Eljnr/d0z2K2UKmSMITO3gIc/XcvcxGR+f1EHbujfkpj6If4OTZ0FxE4+OrskJCSY5cuX+zsMpXzuUEYOWw5msmjHYWYsTyIlIxeAv1zamduHtPFzdKqmEZEVxpiE4h7TjkulaiBjDO8s3Mkz/9tEvssQIHBhpzj6tm5A+0bhXKDHTahKpslCqRrieG4Bq/YcY9PBdD5buY+NB9K5uEsjbhkUT4dG4TTU7iblQ5oslKoBFm0/woMzVnMgLQeALk0iePbqHvymT3NEiptdrlTl0mShVDWVlVfA6j3HeH/Rbv634SBtGtbjnQkJdG4SQdOoMH+Hp2oZTRZK+ZHLbVi+6ygr9xxj1Z5UNh5M51B6LrkF7hPrhIcEcd+w9tx1Xhvq1tGfrPIP/eYp5Sc/b0nhqW8S2ZKcCUB8TF16tYimSWQoYcGBBAcKXZtGkhAfTXhosJ+jVbWdJgul/GDGsr386fO1xMfU46VxvRjaIZYG9er4OyylSqTJQqkqYIwhPbuAnUeO89mKJD5cspvB7Rry75sSCA3Wo6pV9afJQikf2nMki/unr2LzwQyy8lwA1AkMYFxCCx4f01UThaoxNFko5QPGGDbsT+e3H6zgeF4B157bkqZRoTSJDGNA2xjtclI1jiYLpc6QMYb5Ww/z4eLd7EjJJD2ngJx8Fxk5BUSGBTP19n50axbp7zCVOiOaLJQ6A/kuNxOnrmROYjKNI0Lp1SKK6HrBBAYIPZpFcX6nWOLC9brWquY7rWQhIgFAfWNMuo/iUapGOJ5bwL5j2bw9fwdzEpN5eGRHbh/chjpBAf4OTSmfKDNZiMhHwF2AC3tp1EgRecEY85yvg1OqOjp6PI/Rkxew3zn1xv3D2nPP+XrlOXV2K0/LoosxJl1Ersdec+JP2KShyULVOsYY/vTZWg5n5vHMVd1pEV2XAW1j/B2WUj5XnmQRLCLBwOXAq8aYfD1xmaoNcgtcbNifzvHcAvIK3BxIy+GbtQdYtOMIf7m0M+PObenvEJWqMuVJFm8Bu4A1wHwRaQWk+TIopfxl5Z5UHv18HUeP53EsO588r3M0ATSPDmPSJZ24dVBrP0WolH+UJ1l8ZYyZ7LkjInuAW30XklJVzxjD+4t2849vEmkUEcqwznFEhAbTu1U0MfXqEBQYQEy9OjSLCiMgQFvWqvYpT7L4DOjtuWOMMSIyDejjs6iUqkI5+S4mfbaWL1fv58JOcbx4TS8i6+qJ+5TyVmKyEJFOQFfs7KcrvR6KAHTiuDorHM7M5a4PVrBiTyoPXdyBiRe005aDUsUorWXRERgNRAGXeS3PAO7wZVBK+YoxhoXbDjN7/UEWbT/CzsPHqRMYwCvXncPoHk39HZ5S1VaJycIYMxOYKSIDjDGLqjAmpXxiR0omD0xfzdqkNOqHBNG/TQxX92nOhZ3i6Nwkwt/hKVWtlWfMYpuIPArEe69vjNFBblUjpB7PIzkjh5vfXUaey83TV3bnit7NCAnSM74qVV7lSRYzgQXA99ijuJWq9nILXHy0ZA/Tl+1l08EMACLDgpl2Z39tRShVAeVJFnWNMX/yeSRKVYIfNx/il62Hmbsxmd1HsujVIopJl3SiXp1ABrePpXXDev4OUakaqTzJ4msRGWWM+dbn0Sh1BrYmZ3DLlGWEBAXQqUkEfx/bjfM6xPo7LKXOCuVJFvcDj4pIHpAHCPZwC23Lq2rl7fk7CA0O4Jc/XUhM/RB/h6PUWaXMZGGMCa+KQJQ6E8npOXy5eh/XnttSE4VSPlDmyffFukFE/urcbyEifX0fmlJlc7sNs9cdYMK7S3G5DbcP0XM2KeUL5emGeh1wAxcCTwKZwGvAuT6MS6li5bvcbE/JJC0rn3X70pixfC9bkjNp3bAer43vTasYHcBWyhfKkyz6GWN6i8gqAGNMqojo1eZVlXO5DTf8ZwlLdh49saxT43BevrYXo3s0JVBP06GUz5QnWeSLSCBgAEQkFtvSUKpKvTV/O0t2HuXBizvQs0UUnZuE6/Wtlaoi5UkWk4EvgDgReQq4GviLT6NS6iSr9x7jxblbGNW9Mb+7sB16AS6lqlZ5ZkNNFZEVwDDstNnLjTEbfR6ZUtgjsZNSs7nj/eU0jgzlqcu7a6JQyg/K07IASMae8iMICBOR3saYlb4LS9V2s9bs58PFu1m26yjGQHhIEB/d3o/oejpcppQ/lJksRORJ4GZgO864hfP/Qt+FpWqrvAI3f/96Ax8u3kOb2HrcfV5b4sJDGNiuIe0b6SE/SvlLeVoW1wBtjTF5vg5G1W4pGblMnLqSpbuO8tvz2vDwiE46w0mpaqLMg/KA9dgLIFWIiASKyCoR+dq531pElojIVhGZ7pmGKyIhzv1tzuPxXtt4xFm+WURGVDQWVT1l5OTzwtwtDH/xZ9buO8bL1/bikUs6a6JQqhopT8vi/4BVIrIeyPUsNMaMKedr3A9sxF6OFeAZ4EVjzDQReRO4DXjD+Z9qjGknItc6640TkS7AtdhLvDYFvheRDsYYPV36WeB4bgET3l3Kyj3HuKhzIx4a3kFPIa5UNVSeZPEetuBex2keXyEizYFLgaeAB8VOY7kQGO+17cexyWKscxvgU+BVZ/2xwDRjTC6wU0S2AX0BvXpfDedyG+76cAWr9x7jjet7c0n3Jv4OSSlVgvIki8PGmMkV3P5LwMOAZ2QyBjhmjClw7icBzZzbzYC9AMaYAhFJc9ZvBiz22qb3c04QkTuBOwFatmxZwXBVVXrv110s2HqYf17RXROFUtVcecYsVojI/4nIABHp7fkr60kiMho4ZIxZ4b24mFVNGY+V9pzCBca8bYxJMMYkxMbqNQyqu91HjvPsd5u4sFMc1/Vt4e9wlFJlKE/L4hznf3+vZeWZOjsIGCMio4BQ7JjFS0CUiAQ5rYvmwH5n/SSgBZAkIkFAJHDUa7mH93NUDbT3aBY3vLOE4MAAnrqimx5kp1QNUJ4juC+oyIaNMY8AjwCIyPnAH4wx14vIJ9hThkwDJmCv8Q0wy7m/yHn8B2OMEZFZwEci8gJ2gLs9sLQiMSn/yCtwcyAtm4ycAhZtP8Jb87eT7zJ8eFs/mkSG+Ts8pVQ5lOegvEbAP4GmxphLnNlJA4wx71TwNf8ETBORfwCrAM923gE+cAawj2JnQGGM2SAiM4BEoACYqDOhaobU43k8+sU6vttwELdXx+GANjE8PqYrHRvrQXZK1RRizCnd/0VXEJkNTAH+bIzp6XQRrTLGdK+KACsiISHBLF++3N9h1Go7UjK5/j9LOJyZy4QB8XRsHE5kWDCtYuppklCqmhKRFcaYhOIeK8+YRUNjzAwReQROzFTSmr0q0cG0HCZMWUpugZvP7h5Ij+YVPqZTKVVNlCdZHBeRGAqvZ9EfSPNpVKrGeXv+dmat2c++1GxSs/IJCw5k2p39NVEodZYoT7J4EDv43FZEfgFisQPQSgGQmVvAv+ZsoVVMXS7p3oRmUWGc3zGWrk0j/R2aUqqSlGc21EoROQ/oiD3mYbMxJt/nkaka4/vEZHIL3Dx1RXfOjW/g73CUUj5QYrIQkStLeKiDiGCM+dxHMaka5uu1B2gcEUqfltH+DkUp5SOltSwuK+UxA2iyqKUycwtISs3CGMgtcDN/Swo39G9FgJ4lVqmzVonJwhhzS1UGoqonYwzr9qUxa/V+lu1OJSU9h/1pOaesd1lPPbeTUmczfxyUp2qAHSmZfLlqH7PW7GfXkSyCA4WEVg3o3zaGNg3rEd+wHkFOSyIiLJhztAtKqbNaeWZD/RfnoDzn/hZgOoVHXquzzP/WH2TiRytxG8OANjHcdV5bRnZrTFRdvf61UrWVHpSnTsjIyWf2+oP85Yv19GgeyVs39CEuItTfYSmlqgE9KE8BsPPwcca8spCM3AI6N4lgys3naktCKXWCHpSnAJjyy05yC9x8fEd/+rZuoNe/VkoVoQflKdJz8vl0RRKX9WzKgLYx/g5HKVUNladlgXOhog0+jkX5yYxle8nKc3HzwHh/h6KUqqbKc1lVdRb7dfthnp+zmf5tGtC9uZ7LSSlVvBKThYgMcv6HVF04qqq43YaPl+7htv8up2WDurw2vszLqiularHSuqEmA32wlznVkuQskZPv4uu1B3jv112s25dG/zYNeOW63sTU1zqBUqpkpSWLfBGZAjQTkcknP2iMuc93YanKZIxh1d5jfL3mAJ+vSuJYVj7t4urz/G96clXvZojozCelVOlKSxajgYuAC4EVVROOqmzGGB6btYH3F+2mTmAAF3WJ44b+rRjQJkaThFKq3Eo7keBhYJqIbDTGrKnCmFQlyC1wsXjHUWau2sfnq/Zx66DWPHBxeyJCg/0dmlKqBirP1NkjIvIFMAh7FPdC4H5jTJJPI1MVUuBy887Cnfx7wU4OZ+YSIPDb89owaWQnbUkopSqsPMliCvAR8Bvn/g3Osot9FZSqmJSMXO6fts0YmKkAACAASURBVIpftx9hSPuG3DywO/3axFA/pFyH0yilVInKU4rEGWOmeN3/r4g84KuA1OnJK3CzYncqP29J4f1FuyhwG569ugfXJLTwd2hKqbNIeZJFiojcAHzs3L8OOOK7kFR57TmSxZ0fLGfTwQwALu3ehIeGd6BNbH0/R6aUOtuUJ1ncCrwKvIgds/jVWab8ZM+RLD5YvItpy/YiwMvX9uK8DrF6llillM+U50SCe4AxVRCLKsPeo1lMXbKHdxfuxG0MF3VuxCOjOtEqpp6/Q1NKneV05LMGMMbwwPTVzFy9H4ArezfjTyM70UgvTKSUqiKaLGqAT1ckMXP1fm4eGM+tg1rTMqauv0NSStUymiyquQNp2fz960T6xjfgb6O7EKAXJVJK+UGZpygXkb943dazzVWhfJebez9ahcuZDquJQinlL6WdovxhERlA0UuoLvJ9SAogLSufRz5fx4rdqTxzVQ/iG+ogtlLKf0rrhtqMPWq7jYgsADYCMSLS0RizuUqiq6WW7jzKbf9dRkZuAfec35bLejb1d0hKqVqutGSRCjwKnO/8dQZGAJOchDHQ59HVQi634W8z1xMRFsz03w6gS9MIf4eklFKlJouRwGNAW+AFYA1w3BhzS1UEVlt9tjKJTQczeHX8OZoolFLVRoljFsaYR40xw4BdwIfYxBIrIgtF5Ksqiq/WMMbw1Zr9PPXNRnq1iOLS7k38HZJSSp1Qnqmz3xljlgHLRORuY8xgEWno68Bqmzd+3s6z/9tMz+aRvDSul55OXClVrZTndB8Pe9292Vl22FcB1UbrktJ4Yc4WLu3RhJfH9SIosMwZzUopVaVOq1Q6nSvmiUgLEflRRDaKyAYRud9Z3kBE5orIVud/tLNcRGSyiGwTkbUi0ttrWxOc9beKyITTibm6S8vO54Hpq4ipX4d/Xt5dE4VSqlryZclUADxkjOkM9AcmikgXYBIwzxjTHpjn3Ae4BGjv/N0JvAE2uWAH2vsBfYHHPAmmpsvOc3H7e8vYczSLF8f1IrKuXvJUKVU9+SxZGGMOGGNWOrczsMdpNAPGAu85q70HXO7cHgu8b6zFQJSINMFO151rjDlqjEkF5mJnatVoSalZXPfvxSzfncqL43oxsK0OAymlqq8qOTeUiMQD5wBLgEbGmANgE4qIxDmrNQP2ej0tyVlW0vIaa/+xbC57ZSEFLsMb1/dmZDed+aSUqt58nixEpD7wGfCAMSa9lFk+xT1gSll+8uvcie2+omXLlhULtgoYY3j0i3Xk5Lv56neDaBcX7u+QlFKqTD4dTRWRYGyimGqM+dxZnOx0L+H8P+QsTwK8LxzdHNhfyvIijDFvG2MSjDEJsbGxlftGKkmBy83rP23np80pPDyyoyYKpVSN4bNkIbYJ8Q6w0RjzgtdDswDPjKYJwEyv5Tc5s6L6A2lOd9V3wHARiXYGtoc7y2qU1ON5jH5lIc99t5mLOscxYUC8v0NSSqly82U31CDgRmCdiKx2lj0KPA3MEJHbgD3YkxUCfAuMArYBWcAtAMaYoyLyJLDMWe/vxpijPozbJ579bhNbD2U6YxSN9aA7pVSN4rNkYYxZSPHjDQDDilnfABNL2Na7wLuVF13VWrknlWnL9nLboNZcoqfxUErVQHqlPB/ZkpzBl6v2sWTnUVbuSSW2fgj3X9Te32EppVSFaLLwgSOZuVz79mLSsvPp1jSC+4e156rezQkP1YPulFI1kyYLH3jiq0QycvL55r7BdGqspxlXStV8eiKiSvZ9YjKz1uxn4gXtNFEopc4amiwqUXpOPn/5cj0dG4Vzz/nt/B2OUkpVGu2GqiTGGJ6YlcihjBzeurEPdYI0Dyulzh5aolUCYwxPfr2Rz1YmMfGCdvRsEeXvkJRSqlJpsqgEr/24jXd/2cktg+J58OIO/g5HKaUqnSaLM/TT5kP8a+4WxvZqyt9Gd9Ejs5VSZyVNFmcgJ9/FHz5ZQ8dG4Tx9ZQ9NFEqps5YOcJ+Bz1YmcTgzj1fH9yasTqC/w1FKKZ/RlkUFud2GdxbspHuzSPq1buDvcJRSyqc0WVTQZyuT2HH4OLcPaa3dT0qps552Q1XAv+fv4J+zN9K7ZRSj9CyySqlaQFsWp2nm6n089e1GRnVrwkd39Cc4UHehUurspy2L07DpYDqTPlvHufHRvHRtL00USqlaQ0u7ctp1+Dg3vbOU8NAgXhvfWxOFUqpW0RKvHH7YlMy1by8m3+Xmw9v7ERcR6u+QlFKqSmmyKMOrP2zl1v8up15IIB/e3o8OjcL9HZJSSlU5HbMoRVpWPm/8tJ2LOjfi9et765lklVK1lpZ+pXh/0S6O57l4aHgHTRRKqVpNS8AS5OS7mPLrLi7sFEfnJnrFO6VU7abJogTfb0zm6PE8bhvc2t+hKKWU32myKMGs1fuJCw+hf5sYf4eilFJ+p8miGOk5+fy0OYXRPZoSGKDnfVJKKU0Wxfhu/UHyXG4u66nnfVJKKdBkUaz/rT9I8+gweum1tJVSCtBkcYrcAhe/bj/ChZ3i9NTjSinl0GRxkpW7j5Gd72JI+1h/h6KUUtWGJouTLNiaQlCA0L+NXv1OKaU8NFmcZMHWw/RuGU14aLC/Q1FKqWpDk4WXI5m5rN+fxpD2Df0dilKqJnO74Yu7YddCyMuC9y+HxJm+e719K2DGTZCf47OX0GThJSk1m+bRYQztoOMVSqkzkLYX1nwEn9wC3/4BdvwIW+f45rXysuCz220ySl7vm9dAk0URPVtEMf+PF9CjeaS/Q1GVbdM3kLSi/Osf3gprPyl9ndwMWPQ6uF1Fl7sKYMnbkJN++nHWNPtWwv7VlbvNvCxY8ALkHYeCPPj5Ocg6Wv7nb/8Rfn4Wfnoafvzn6X3uZ8Lttt+HrKOQussuO34IVk+1t1N3F657/Aj88rJ9zpma93c4usPeTtl05tsrgZ6i/CQ6XfYs9c0foElPGD+tfOsvfh2WvwvxgyCiafHrrJ0B3z0CjbpAm/MLl2/9Dmb/EQqyYdD9Zxp59fbVfRBYB+74ofK2uf5TmPcEhEVBvVj48R92+Xl/LPu5+1bCh1eB8UrgexbDhFmVF19J9q+03weAOvXs/6EPQ9JSCK4HyesK113yJsx/FloPhabnVPw1d/9qt5VwK6ya6tNkoS0LVTNlJIMx5Vs3Pwcy9kP6vqLLc9JKfo6nZrjxK9tySD9w6jpJy4v+9/D0TRfXR52+v2hLxO2GzBR72xg4tqfwdvIG2LPE1kLLy+0qWoOtCLe7+L5vYyD7WNHXStkChzaV/7MoTm4mFOQW3vfst41f2z+ATV8VPu7KL/6zy8+GL+6C+o3g4Z3w2DHocvmpn/uZcOWf2pL08HwPDm+GY7tBAuG8P8FNMyGuM6Tts61OsN8rsPsP4Pjhwu147+PS5GXBzIkQ1RIufhIadoCUzaf/nspJk4WqeXb8DC90Kv+AoacATt9fuOzAGngmHtZ9WvxzPMliw5fw7R/hld6ndoXscwqHfV7dHAW5sHm2rUnuW1H42mCf/0ofmP1w4bJ1M+DFrnBsr43lpR5wcD1s/wHeGAjvDoepV5fvfQIsfgNePff0um1OtuhVeLnnqQlj/WfwfIfC/XhsN7hyIf84pCVV7LWMgf8Ms/sYIDsVdvxk99/On519Wdd+Xp4k+MOT9j0W5BXd1pqPbUE99hWo2wBEIKKZjfdMkpm398bArPuKf8zzfUjZYr8/US0g0Om8iWppWzvpSbaLM2Wjs+4m2LkAnm/vdOmtgmdb21ZrWTzdT2Nfg5D6ENtRWxZKnZB3HGb9Dowbdi0o33OOOYVM1uHCGuzO+XYb3zx0aqvB7bKFd3Bd2PMrLH8H8rNg87eF62Qfg8NbQAIgaVlhYbT9R8hNh4set/cTvbo/Nn9rt7PsP7b7AODgOlvgJn4Ja6cBBjZ8Aes/h5BI6Hun7d44urN873X9p3Z7Z1JobJ8HmQftoKy3tTPstvcssve9a7EVrdEeWGNj9bzW5tngLoCLHrP/c9Pggj/bxzZ9bVs9az+BzORT49uzxLYq2g4rXBbR1O7znHLW1ktzZLv9Pmz7vvjk42lZpGyyiS2qVeFj0c7t1N2FrYq6De1+2/mz/S6u/8y+N+O2FYrMQyXH4ul+OvcOaD3ELovtZCsnecfP/L0Wo8YkCxEZKSKbRWSbiEzydzyqAn6ZDNNvLH2dfSvh3ZF28Njj24fhB6ffev5ztvCPaG4LaW9uN0y/wdY63x9b2OT3tBIAMpzEsHcp1I2BgpzCfmbvddz50Psmez+mPUS2KFrw719p/3ccBcdTbAHy1lD44k4IjYQ+N0PjHnaQ9c3B9sedOMvGHdUSvrrf6XZyEtnK922NGmyy2PQ1dLwE+t9jl236umiM6z6F2Sf9DI7ttTVTKFp4f/dn26J5+wJb4HkseQteH2jjnnwOTLve7sN9zntLnGW7wuY9aVsqnsLZM2DsnZA8NWVv2cfggyvg1b7wxmD497DC9+ix0dmnx/bYrsXEmXZfn3s71G9sE/a5t0GjbjaB7l9puxTBtvo2fePE7bI1+2YJtkXh4Rlv8rSGso7ClFHwSoJT6XAK/dxM+935z8Xw9YPFJ4PEL+3/zIN2thPY7qNvHrL7LHUnhDeB7KN2v0XHFz7XkziO7bafZdPe0Gqg3Yee73HiTPvXuIct8N++wH53Xh9gY/UMhhtjWzdRLQsrJQCxHez/w1tOjb0S1IhkISKBwGvAJUAX4DoR6eLfqNRpObAGvn/c1qpKq/kse8fWXA+ssfc3fQNL37KFqTGw+X+25thznP1B5mUVPnffCmeMocAWSqlObdw7WXgKjaTl0OYC6DUetn5ftB/a093RYQSM+CeM+wC6jLVdQ56+ck8tsu+d9v8nt9gCr8NIuORZCKoDFz8BHUdCVip8doctbLuMhYH32R90+r7C2A5vsXGfcyMc3W5rwl3GQIPW0Lh7YW0UbDfGzHthyRuFs2CgcJ2AoMICI+uo7ZqqU88mCk+hc2AN/O8RCAiwtfG6DW0htvlb2zIKjYTN39jkvuB5+OgacOVBaFRh4ZayGcKb2kHo4loyc/9mP4fYDrZL5sg2+PXVwseNsQmprnNc0/Yf7F+XsRAQaFsXw/4GwWE2+e5bbpNsQBB0vNTG++U9Ttyz7fab9ykaQ0Szop/7hi9g9y8Q3th+p1a+Z5d7vpuuXNuS9CRdbxu+tBUMsJUNY+DrB2xLcepv7PKe19r/BdmFrQmAyOa2Fbp7kf2edr7MtgRSd9rvUr1Ym4DSk2wF4Yq3oFFXiGwJ9eNsrKvedz7TI3BkK/T7re1+8ojt5HwutThZAH2BbcaYHcaYPGAaMNbPManSuPJhzXTb7+122YE44waMLexKes7mb+ztlE126uk3D9mBwsxkOJRol7fsD83PtYWrJ6mArfkF1oHRLxZuA2xtLrCOvZ2+3/avZ+yHFn2heV/IyyhaE/cU4FGtYMBEOzjZZaxtbWz5zj6WtNwOKLYaCEGhdhsjn4Yr3y4sMNpeCFf9B65+1yYGV55NAHGd7eOHnO6KDiPt/ejWcOFfAIE69e3zATqPhb1LbOtq7mO2APe8H+/WzsavIK6rrYV73vvmb21f+eiXYMRTtqD89g/286jbACZ8Bdd/YmMEOx4AMOQPNjEe3W5r60nLbFLpdb3d5wV59jViO9pCyrP/3G5bqP70jC2I+98D4z6E6z62LbUdP9lxiZ0L7PTWI1th8O8hIBh++j9nHzk/7V7jof/d9nbCrTaO5PV2BlGfm21SK8iFwJDCuJslFP1OnWhZOIPciTNtS3HCVxA/BOb81SbNZf+GfnfbweiAYJtUso4W7t+jO+DgWhj4O9vaSVpmu+U2fmXjyTpsk0GPawtf27tlERhsW5XrnTGyzpfZfWfckJcJQx6ySTAg2LYou10J18+A6z6CG7+EVoPtZ5+ZUliZadCm6Htt0MZuw0fjFjUlWTQD9nrdT3KWnSAid4rIchFZnpKSUqXBqWLMf852ySR+aefhH1xnf2hQcv/2rgW2IAFbO9r8re0SGu50QS15CzDQPKGwUPAMKnpqqW0vLHzM86NJ3W2b/WCThadm3DzBJh3v7YDTNSS2O8SjWYLtYkicaQvKPYuhRT9bCLQdZgv8HuOKf18t+9kptHFdbHLy1AD3LrEFXvwQ6HcXnPewrfF2GWML5eAwu163K21Cmv8cLHrNFkxXvmXfk6drZNs825/e/SpnoNOpXSbOsrXTpufAOTdAp9G25pycCKOeg7Bou15UC2jSy+6z0Ejoe4ftBhr4O5tMwptCt6ttgnXl2s8zZYt9L55kYYzd9icT4Kd/2vd7waOF+6Hr5TbhznsS3h9j16lTH7r/Bpr0sPs9vOmpBT7YlsaYVyAozO7nNufb93TJM9DuIuezllOnoYY3tsvT99tZZbsW2v0rAmMm29df8pb9XIb9ze6PthfYhPf5HTDjRvtePZMpul1l9/vWuXZQvkU/W5h3Gg0tB9gKRLAzbTYqvmgs0a1sMoztBA3b28/Jo93Fdj/0uMZOGfYmAqNfsK3NNR8Xtpi9x0TAfhdj2vksWdSU4yyKO/ihSKeiMeZt4G2AhISESpr6UAsc22sLirK43XBgtf2yu132CxwSYX/EoVEQ4Vwo6uB62x0w/3l7f+/SwqmA595uj1/w/jLnpNs+f3cBrP7Y/tCi4+06xm1/zAm32nn3a6cDAs362AItqlVhwb9/FaTtgQsesU3zyBaFSSl1t/0RJm+whUbGQVv4Nupuf2CerhXPGEXqbtttEFSnMM6AAOg8xtaWN31tB147X2Yfu3aqLShLO0bn4ids/7II1GtouzO2Oq2U6FYw8N7Cda95v+hzY9rCI0m25hoQWLj88Bbb1bNzge2eadgB+k+0s5nWTrdTNbf/YLsrPLGN+9DWZN0FhYnCo/No+xk362MT1QPr7P4Rgd+tgKCQwjGfdTPsLKjYjs5AdLo9QnnuY06L6h37/Qj0KmKa9rafy/J3bC379u9tDMGhNmnvW2EL8oAS6rCNusDDO2xsInDnT3Z5UIhtkcZ2gtCIos8JDLYtovT9dh3jKmy5NGgDDyae+rl1vRK23mW/T2ATx7bv7X6JagktzoWFL9oWxuVv2M/kmg/sugEBNhEcWF20ZQFO4b6g8HsT085+piER9jO+4s3i3zfY/RzexLau3fl2WXSrU9cbP8N2aflATUkWSYB3idYc2F/Cuqq8lk+xfa5jXoXeZQw8z7q38EjUkwUE2drVkW12e2BriBFN7QFJOWm27zi6FTRoW1iI5+fA5F62D9aj21W2W8EzPtCsty1MmvSCvYshtrNNFGALmF0LbCJLnOn0ZV9iH4vtaF8nO9UW7NGtbDzp+2zfcNNzCpNB84SiR/ke231qrQ1sIbP0LfjuUTtTqc0FdrlI6YnCw3ud2E62SwiKf62TBRZzYssuY22yeG+0LXRunWP3lafl8v1jtmDpcnnRGELCi3+NTpfZri5Pa8s7Wdapa/9HNLOf7RKnYIvr4nQvYsc16oTDZZNtF9fJRGzMi16FMS8XVjAAWg2y2+x6Ren7wROHtw4jbPdN82JaJOB87vvtdyQ63g4ge8d0sk6jbAumuTNYvvI9W6G5+MnCWBe+CBf/3RbyUDTBxXW23VYn7wNP8vAki+Aw2yUWHV++709sJ1uJCgy2CcFz4F+R1yjHd6mCakqyWAa0F5HWwD7gWmC8f0Oq4dL324IGsbNl2l1U9MfrbeNXNlH0vdN2twQE2pp0brptZcz7ux04zTpqf0hDHrSF+5K37OBoZortigFbiCdvsLe3fW8TxXmTbG0ssI59/qoP7Hl1jqcUHgHdPMEmC+8Cof1w2wectMwWBG3OL6wtx3ayXQ6eAeCoVvb97VtpBxGHPVa4nWYJsO0ZOwMrJNyOWXjGC7y17G9/pBkHoOd1RQvT0xXbsTBZVPQHHh0PN35hp1g27GATq2fbAOs+sV1kJRWiJ4vrBNd+ZLtTSiICv5lixy3qxthuKYDxn9jusaa9S2+pnvew/Q55pnt6dL4M7lpoB/NPV1i03Q+egvtkEU1tyzMz2Y5BlVUwh0bCHfNsK2j9Z7DTqQB1GWP/t7sIfju/aNLxdv4jdrzl5NfpfSOENyr6vGs/Kr7QL05sJ5u46tQ/tdVSBWpEsjDGFIjIvcB3QCDwrjFmg5/Dqt4SZ9rz69w2xzbTTzbnr7ZL6YZP7dTDOX8uHOT02PiVPbfOkW32VBkj/ll8DTcsGj643Bb2l71sC36wNVTjtlMNPbXV2E62Gyc/x/a3h0XD0D8U3a6nsDOuwued/B/sTKPAOvZ0EKk7bZLy3kZBjm2hgP1xRTQrnLrZeUzhus3PBYydqhgcapNBcT/GgEBbqC1/t7Aro6I8tf+w6MKWUkUUl9SiW9uadmCw7es+nVPYdLq07HVa9rd/3joML9/2QyNPTRRgY6xIovAobpseEU0Lpx6X93Nr1NX+73yZnWTRpEfhd0LE/h5KEt2q+ApAeOPCrk6Phu3KFw/YZJ6fZSdXlOdzqmQ1IlkAGGO+Bb4tc0VlJc60/aY750P7i4s+5nbZWT09r7W1pD632ALQU7P2WPCCHW8493Y7K6W4RAF2QPDiJ+0UP0+igKI12hPJwpkBkrzeTnfsduWp2/Ue+PNso/3FdraKpwkPtuBpeyFs+Z+dMdXR6wfkKYznP29riLEdC2fGxHUp+iNtNdB2f+Vl2djCGhTOUDpZ/3sAKXrgV0U0dObE+6KGGBjkzOLq4pcaaLXj+dwjWxROdCiveg3tILrn8/KnWGcWXUG2tizUaXAV2Hn2PcfbQb0FL9i++EZdbcHuGfjd+JWdSrlxlu1GErEDo3kZdiYH2AJ4yRt2hkd0Kzsw2qSHPQDqoidg8ANlxzOomFMg1G1g+2RTdxbWxDyF+P8m2YFW7/50j6hWdtwivJFNQGCb6pc8feq6XS63yaL1EKgXU7jc8+MuyLGzXoJCCgsN71YF2H7wk1tVJWnY3tbWz5RnP5RnvKIiLn7CN9utiTzHWnQZe3qtLI++d1RuPBXlXYny4dhESTRZ1FRbv4M5f7FTOJv1sdMQQyNtf3/LAfYAsYBge1Bb6k7bwmjS03YfnJg66vQ3t+xvD4xa87Gd5pp1uLAQ71pMYX46ul1lk5NnGmjD9nYWyIE1tsBsPfTU5wQE2phiytFE73iJne1ycvM+LMr2DbccUNhV07inHbjsdtWZvafKEN7YDvZ7d6sp32jcw85c6nGNvyM5M2FRdkZUSd2kPiamsk6wVY0kJCSY5cuXl72iP2Wm2CZueWs6+dlwaKPts2w1CL74rTOVFDsTptNouPCv8Nq5dpbOjh/t3P0lXtPx+k+Ekf+0R/9u/Ar+tKvw9WfeaxMNYgcusw7bGUN3/lR57/l0eE5tUNI0yvJu4+SZSm5X0emn/lTWdFtVedzuM/suVRfvj7Xjbg+ss9N4K5mIrDDGFDsj4izYezXQ3qX2rKlz/1q+9fOz7Xl1/n0B/PdSO/Vw82w7I6dZgp2nPep5e1qF2E42UQQE2aNwg8KgRX87cyhxpi2gkpbbGq13QeUZCzj3NhjrnJKh65WV+75PR0DAmf+4AwJOLYyrS6IATRRV6WxIFGAnAQTXtdOXq5h2Q1W1/Gz48m5bw/31Vdt/7pl+WJIf/gGHNtiEsPErO5MJYwvz+EH2wLbwRnbdzmPsXOxGXaF+LNw62x7Bu/U7e9DUjp/s4yfPZ293sT3AqPMYe1Db7fPObHaKUqryDXnIHukdWPVFtyYLbwfW2LNkAicOGhextXHjtlM5jechsd0/4vxHTrodYGct5Gbao4Xr1LPTMnPSbRfPuKl2kPf9sXbetLsAMHZgNyjEzhByu+xf2l5IuM0OtLW7yJ6FMjAY2pxn1/Wep91ljL0Cl6cv3HP6g46X2NbGJxM4ccoMbwEBdm64R3nn5iulqk5Y9KlH3lcRTRbewqJtjfvEOI7XeI4EFiYHY+xjniSCJ5kYr9vYg7bq1LfHM+Qdt+MNwWH2pGCdR9s+x+Xv2O0HBAFiz7tTkGefExBk/+rHwVDn4jANWtuT0+VnF3/8RKNu9rQSHUed+t4uftIObtdtYMc9lFKqnHSAWymlFKAD3Eoppc6QJgullFJl0mShlFKqTJoslFJKlUmThVJKqTJpslBKKVUmTRZKKaXKpMlCKaVUmc7Kg/JEJAXYfQabaAgcrqRwKpPGdfqqa2zVNS6ovrFV17ig+sZ2unG1MsbEFvfAWZkszpSILC/pKEZ/0rhOX3WNrbrGBdU3tuoaF1Tf2CozLu2GUkopVSZNFkoppcqkyaJ4b/s7gBJoXKevusZWXeOC6htbdY0Lqm9slRaXjlkopZQqk7YslFJKlUmThVJKqTJpsvAiIiNFZLOIbBORSVX82i1E5EcR2SgiG0Tkfmf54yKyT0RWO3+jvJ7ziBPrZhEZ4eP4donIOieG5c6yBiIyV0S2Ov+jneUiIpOd2NaKSG8fxdTRa7+sFpF0EXnAX/tMRN4VkUMist5r2WnvIxGZ4Ky/VUQm+Ciu50Rkk/PaX4hIlLM8XkSyvfbdm17P6eN8B7Y5sYuPYjvtz6+yf7slxDXdK6ZdIrLaWV5l+6yUcsL33zNjjP7ZcZtAYDvQBqgDrAG6VOHrNwF6O7fDgS1AF+Bx4A/FrN/FiTEEaO3EHujD+HYBDU9a9iwwybk9CXjGuT0KmI29Wnl/YEkVfX4HgVb+2mfAUKA3sL6i+whoAOxw/kc7t6N9ENdwIMi5/YxXXPHe6520naXAACfm2cAlPtpnp/X5+eK3W1xcJz3+L+BvVb3PSiknfP4905ZFob7ANmPMDmNMHjANGFtVL26MOWCMWenczgA2As1KecpYYJoxJtcYsxPYhn0PVWks8J5z+z3gcq/l7xtrMRAlIk18HMswYLsxprQj9326z4wxE5K47QAABaZJREFU84Gjxbzm6eyjEcBcY8xRY0wqMBcYWdlxGWPmGGMKnLuLgealbcOJLcIYs8jY0uZ9r/dSqbGVoqTPr9J/u6XF5bQOrgE+Lm0bvthnpZQTPv+eabIo1AzY63U/idILa58RkXjgHGCJs+hepwn5rqd5SdXHa4A5IrJCRO50ljUyxhwA+yUG4vwUG8C1FP3xVod9Bqe/j/wR463Y2qdHaxFZJSI/i8gQZ1kzJ5aqiut0Pr+q3mdDgGRjzFavZVW+z04qJ3z+PdNkUai4vsQqn1csIvWBz4AHjDHpwBtAW6AXcADb/IWqj3eQMaY3cAkwUUSGlrJulcYmInWAMcAnzqLqss9KU1IsVb3v/gwUAFOdRQeAlsaYc4AHgY9EJKKK4zrdz6+qP9frKFoxqfJ9Vkw5UeKqJcRw2rFpsiiUBLTwut8c2F+VAYhIMPYLMNUY8zmAMSbZGOMyxriBf1PYbVKl8Rpj9jv/DwFfOHEke7qXnP+H/BEbNoGtNMYkOzFWi33mON19VGUxOoOao4HrnW4SnC6eI87tFdixgA5OXN5dVT6LqwKfX1XusyDgSmC6V7xVus+KKyeogu+ZJotCy4D2ItLaqaleC8yqqhd3+kHfATYaY17wWu7d138F4JmdMQu4VkRCRKQ10B47mOaL2OqJSLjnNnZwdL0Tg2cWxQRgpldsNzkzMfoDaZ4mso8UqelVh33m5XT30XfAcBGJdrpfhjvLKpWIjAT+BIwxxmR5LY8VkUDndhvsPtrhxJYhIv2d7+pNXu+lsmM73c+vKn+7FwGbjDEnupeqcp+VVE5QFd+zMxmZP9v+sDMHtmBrBn+u4tcejG0GrgVWO3+jgA+Adc7yWUATr+f82Yl1M5UwM6WU2NpgZ5isATZ49g0QA8wDtjr/GzjLBXjNiW0dkODD2OoCR4BIr2V+2WfYhHUAyMfW3G6ryD7CjiFsc/5u8VFc27B91p7v2pvOulc5n/EaYCVwmdd2ErAF93bgVZwzQPggttP+/Cr7t1tcXM7y/wJ3nbRule0zSi4nfP4909N9KKWUKpN2QymllCqTJgullFJl0mShlFKqTJoslFJKlUmThVJKqTJpslCqFCLikqJnti31jKYicpeI3FQJr7tLRBqe6XaUqiw6dVapUohIpjGmvh9edxd2Tvzhqn5tpYqjLQulKsCp+T8jIkudv3bO8sdF5A/O7ftEJNE5Id40Z1kDEfnSWbZYRHo4y2NEZI5zMrq38Dp3j4jc4LzGahF5S0QCnb//ish6sddL+L0fdoOqRTRZKFW6sJO6ocZ5PZZujOmLPTL3pWKeOwk4xxjTA7jLWfYEsMpZ9ij2tNUAjwELjT0Z3SygJYCIdAbGYU/k2AtwAddjT7LXzBjTzRjTHZhSie9ZqVME+TsApaq5bKeQLs7HXv9fLObxtcBUEfkS+NJZNhh7egiMMT84LYr/b+/uVSIGojAMv99ayIKgWNiJYGOpsDcgWImdCOI1bC8ICnoFFraCCIKVlSyIjT+NiChi4QVYC1ppeSxmFoM/OxK08nsgJJlJAlOdzDCcM0gqtjOf2zuSnvLzM0ALuEppgWiSksQdAuOStoAOcFx/iGZlnlmY1RffXHfNkfLytIDrnLG0V2ror74hYDcipvIxERHrkQrWTAKnQBvYrjkGsx9xsDCrb7Fyvqh2SGoAoxFxAiwDQ8AAcE5aRkLSNPAYqR5BtX2WVOoSUlK4BUkjuW9Y0ljeKdWIiANgjVQC1OzPeBnKrLempNvK/VFEdLfP9ku6JP10LX14rw/Yy0tMAjYj4lnSOrAj6Q544T2t9AawL+kGOAMeACLiXtIqqUphg5QFtQ285u90f/hWfm/IZp9566xZDd7aav+Nl6HMzKzIMwszMyvyzMLMzIocLMzMrMjBwszMihwszMysyMHCzMyK3gAMgktiNVMu/gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final Q size (table): 8014 different states saved\n",
      "\n",
      "Pacman emerges victorious! Score: 495\n",
      "Pacman emerges victorious! Score: 491\n",
      "Pacman emerges victorious! Score: 491\n",
      "Average Score: 492.3333333333333\n",
      "Scores:        495.0, 491.0, 491.0\n",
      "Win Rate:      3/3 (1.00)\n",
      "Record:        Win, Win, Win\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<game.Game at 0x7f4bbf072cc0>,\n",
       " <game.Game at 0x7f4bbf0f8208>,\n",
       " <game.Game at 0x7f4bbefe89e8>]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "from pacman import readCommand, runGames\n",
    "prefs = ['--pacman',     'PacmanQAgent',\n",
    "         '--numTraining','2000',\n",
    "         '--numGames',   '2003',\n",
    "         '--layout',     'smallGrid']\n",
    "args = readCommand(prefs)\n",
    "runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Solo visualización\n",
    "\n",
    "El siguiente código muestra el último juego de un agente **entrenado por 2000** episodios."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-17T01:37:20.819864Z",
     "start_time": "2019-07-17T01:37:16.597464Z"
    },
    "code_folding": [],
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%%capture\n",
    "# ^ Comment this line to get a verbose output\n",
    "prefs = ['--pacman',     'PacmanQAgent',\n",
    "         '--numGames',   '0',\n",
    "         '--layout',     'smallGrid',\n",
    "         '--replay',     'recorded/recorded-game-pacman-q-agent-2000th-game']\n",
    "args = readCommand(prefs)  # Get game components based on prefs\n",
    "runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Extra commands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[qLearningAgents.py](./cs188x_pacman/qlearningAgents.py) contiene la implementación de los distintos agentes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-17T01:37:23.925584Z",
     "start_time": "2019-07-17T01:37:23.923849Z"
    },
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "# To record EVERY game, add: , ['--recordActions', 'True']\n",
    "#prefs = ['--pacman',        'PacmanQAgent',\n",
    "#         '--numTraining',   '2000',\n",
    "#         '--numGames',      '2003',\n",
    "#         '--layout',        'smallGrid',\n",
    "#         '--recordActions', 'True']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-17T01:37:24.011715Z",
     "start_time": "2019-07-17T01:37:24.009935Z"
    }
   },
   "outputs": [],
   "source": [
    "# To print all options use '--help'\n",
    "#args = pacman.readCommand(['--help']) # or uncomment this line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aproximación de Función de Valor\n",
    "\n",
    "Vemos que hay varios problemas de modelos tabulares para grandes MDPs: \n",
    "\n",
    "- Necesitamos **enormes cantidades de memoria** para guardar cada estado posible\n",
    "- Aprender un valor **para cada** estado requiere de **mucho tiempo**\n",
    "- Generalmente los estados son **parcialmente observables**\n",
    "\n",
    "Queda claro que para resolver problemas con **grandes espacios** de estado (discreto, continuos e *infinitos*), será necesario **aproximar la Función de Valor**, y no depender de recordar cada observación.\n",
    "\n",
    "Para estados similares, esperamos obtener resultados similares.\n",
    "\n",
    "Si el espacio de estados es muy grande o contínuo, sólo veremos cada estado una única vez, por lo que sólo recordarlos no nos ayudará a predecir algún otro parecido.\n",
    "___\n",
    "\n",
    "Siendo concretos, en el ejemplo de Pac-man\n",
    "\n",
    "* Si en el pasado obtuvimos un ***reward negativo*** por estar al lado de un fantasma en la esquina superior del mapa\n",
    "  \n",
    "  queremos que si encuentra un estado *\"parecido\"* lo considere peligroso (**generalice**)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![pacman-danger-similar-states](./img/pacman-micro-danger1.png  \"Similar states\")\n",
    "\n",
    "$$\\text{Dos estados completamente diferentes para modelos tabulares}$$\n",
    "\n",
    "$$\\text{Diferencia: pellet desplazado dos celdas a la derecha}$$\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Existen distintos tipos de aproximadores de funciones que podemos usar, como:\n",
    "\n",
    "* **Aproximador lineal** (si conocemos *buenas features*)\n",
    "* **Red Neuronal**\n",
    "* Decision tree\n",
    "* Neirest Neighbour (no paramétrico)\n",
    "* Constructores de features\n",
    "  * Fourier / wavelets bases\n",
    "  * Coarse coding\n",
    "\n",
    "Pero necesitamos considerar propiedades particulares de Reinforcement Learning:\n",
    "* La **experiencia no es iid** (steps consecutivos están altamente correlacionados)\n",
    "* La **política** del agente afecta **directamente la data** que recibe\n",
    "* Las Funciones de Valor pueden ser **no-estacionarias** (como al usar *bootstraping*)\n",
    "* El feedback **no** suele ser instantáneo (*delayed feedback*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aproximador Lineal\n",
    "\n",
    "![pacman-small-layout](./img/pacman-small.png)\n",
    "\n",
    "Es la más simple de las opciones de arriba, pero tiene **el mayor peso teórico** que la respalda, lo que la vuelve una excelente opción para una gran variedad de casos.\n",
    "\n",
    "Se basa en reducir el espacio de estados a una serie de *features* que lo representan, y usar como **Función de Valor aproximada**, a una combinación lineal de estas *features* con un cierto peso $w_i$ (*weights*) que se necesita aprender."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$n $ : número de *features*\n",
    "\n",
    "$f_i(s,a)$ : función que devuelve un valor correspondiente a una feature $i$ dado estado $s$ y acción $a$\n",
    "\n",
    "$$\\tilde{Q}(s,a) = \\sum\\limits_{i=1}^n f_i(s,a) * w_i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parte de la simpleza de esta herramienta, surge de que al derivar nuestra función Q aproximada con respecto a los pesos, obtenemos una sumatoria de **solo los valores de las *features***, lo que facilita actualizar nuestras estimaciones de los distintos pesos:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Error de predicción** (o *advantage function*):\n",
    "\n",
    "$advantage = (R + \\gamma \\max\\limits_{a} \\tilde{Q}(S', a)) - \\tilde{Q}(S,A)$\n",
    "\n",
    "**Update:**\n",
    "\n",
    "$w_i \\leftarrow w_i + \\alpha \\cdot advantage \\cdot f_i(S,A)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Volviendo a nuestro simulador de Pacman, podemos resolver desafíos con un **espacio mucho mayor**, en una **menor cantidad de episodios y espacio en memoria** (aunque **mayor cantidad de tiempo** de aprendizaje), usando un aproximador lineal con features como:\n",
    "\n",
    "1. Fantasma en celda contigua (1 ó 0)\n",
    "2. Comer *pellet* (1 ó 0)\n",
    "3. Distancia a comida más cercana (float)\n",
    "\n",
    "ver archivo [./cs188x_pacman/featureExtractors.py](./cs188x_pacman/featureExtractors.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Entrenar agente"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El siguiente código entrena por 100 partidas un aproximador lineal con las features mencionadas en un mapa mucho mayor: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T16:17:36.496533Z",
     "start_time": "2019-07-19T16:17:01.372131Z"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Beginning 100 episodes of Training\n",
      "Episodes\tMean R lifetime / last 50 ep\tTraining time\n",
      "  50/ 100\tr: 1083.90 / 1083.90\t11.15 sec\n",
      " 100/ 100\tr: 1118.30 / 1152.70\t10.30 sec\n",
      "Training Done (turning off epsilon and alpha)\n",
      "---------------------------------------------\n",
      "Pacman died! Score: 65\n",
      "Average Score: 65.0\n",
      "Scores:        65.0\n",
      "Win Rate:      0/1 (0.00)\n",
      "Record:        Loss\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<game.Game at 0x7fd53b38a2b0>]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from pacman import readCommand, runGames\n",
    "prefs = ['--pacman',     'ApproximateQAgent',\n",
    "         '--numTraining','100',\n",
    "         '--numGames',   '101',\n",
    "         '--layout',     'mediumClassic',\n",
    "         '--agentArgs',  'extractor=SimpleExtractor']\n",
    "args = readCommand(prefs)  # Get game components based on prefs\n",
    "runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Solo visualización"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación, se facilita (solo como visualización) la última partida de un agente entrenado por **100 episodios** con un aproximador lineal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-17T01:48:28.796911Z",
     "start_time": "2019-07-17T01:48:09.872361Z"
    },
    "cell_style": "center",
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%%capture\n",
    "# ^ Comment this line to get a verbose output\n",
    "prefs = ['--pacman',     'ApproximateQAgent',\n",
    "         '--numGames',   '0',\n",
    "         '--layout',     'mediumClassic',\n",
    "         '--agentArgs',  'extractor=SimpleExtractor',\n",
    "         '--replay',     'recorded/recorded-game-pacman-approx-linear-q-agent-100th-game']\n",
    "args = readCommand(prefs)  # Get game components based on options\n",
    "runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uno de los problemas con usar aproximadores lineales, es que necesitamos ***buenas* features** para obtener resultados agradables, donde \"*buenas*\" dependerá de cada caso particular.\n",
    "\n",
    "En el ejemplo de arriba, \"*Fantasma en celda contigua*\" aumenta en gran medida la performance del algoritmo, lo que intuitivamente es de esperar, ya que estamos casi **prefijando** el comportamiento de pacman para este problema en particular.\n",
    "\n",
    "Y aún consiguiendo estas features, vienen con la limitación de que en un aproximador lineal, no podrán ser \"relacionadas\" entre sí, por lo que debemos incluirlas como productos o algún otro tipo de polinomio, dejando de ser lineal (y con ello desaparecerán ciertas garantías)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Funciones Diferenciables no-Lineales: *Redes Neuronales*\n",
    "\n",
    "Una solución más general a este tipo de problemas es usar Redes Neuronales (NNs) **como aproximador** de nuestra Función de Valor.\n",
    "\n",
    "De esta forma, ya no necesitamos transformar nuestro espacio de estados, ni conocer cómo funciona el problema, sino que podemos usar **directamente** los datos *crudos* observados (ej: píxeles) como entrada, y obtener como salida de la NN el valor que lo represente.\n",
    "\n",
    "Concretamente, la **Función de Valor serán los pesos (*weights*) de la red neuronal**, que *mapearán* directamente desde una entrada cruda, a algún valor o puntaje que represente ese estado.\n",
    "\n",
    "Las features estarán **implícitas en los pesos** de la red, dejando en manos del **optimizador** de la red neuronal el problema de encontrar buenas features, generalizando a una mayor cantidad de casos, sin necesidad de tener que conocer la naturaleza del problema.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es conveniente comenzar a pensar en este tipo de diseño de algoritmos de una manera ***más modular***, donde cada módulo puede ser reemplazado por uno equivalente, o que generalice a varios de ellos.\n",
    "\n",
    "En el caso de Q Learning con aproximador lineal, solo basta con reemplazar \"el módulo\" encargado de transformar el espacio mediante las features preprogramadas, por una red neuronal, como se muestra a continuación."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Pseudocodigo para one step Q-learning con NN \n",
    "(usando funciones de [PyTorch](https://pytorch.org/), como se usará en el resto del TP)\n",
    "\n",
    ">    `Usando NN, calcular Q values para estado observado`\n",
    ">\n",
    ">    `Q(S_t, a) para cada acción a`\n",
    ">\n",
    ">    q = q_net( obs )\n",
    ">    \n",
    ">    `Seleccionar acción de forma epsilon-greedy `\n",
    ">\n",
    ">    action = epsilon_greedy( q )\n",
    ">    \n",
    ">    `Obtenemos el valor de esta acción`\n",
    ">\n",
    ">    qa = q [ action ] \n",
    ">    \n",
    ">    `Realizamos la acción elegida y obtenemos nueva obs`\n",
    ">\n",
    ">    reward, discount, next_obs = env.step( action )\n",
    ">    \n",
    ">    `Usamos NN nuevamente para estimar max valor de prox accion`\n",
    ">\n",
    ">    max_q_next = torch.max( q_net( next_obs ) )\n",
    ">    \n",
    ">    `Calculamos TD-error, con especial atención a NO propagar`\n",
    ">\n",
    ">    `gradiente de next_obs, solo de qa`\n",
    ">\n",
    ">    advantage = reward + discount * max_q_next.detach() - qa\n",
    ">    \n",
    ">    `Definimos loss`\n",
    ">\n",
    ">    `(ver archivo con deducción de por qué norma L2)`\n",
    ">\n",
    ">    q_loss = delta**2 / 2\n",
    ">    \n",
    ">    `Usamos optimizador con respecto a este q_loss`\n",
    ">\n",
    ">    `con Stochastic Gradient Descent, RMSProp, Adam, etc`\n",
    ">\n",
    ">    optimizer.minimize( q_loss )\n",
    "\n",
    "Deducción de por qué normal L2: \n",
    "\n",
    "[sarsa_updates_are_MSE.ipynb](https://github.com/LecJackS/saved_models/blob/master/gym_pacman/resources/sarsa_updates_are_MSE.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación, una implementación *vanilla* del pseudocódigo de arriba, aunque con pocas garantías de converger, ya que para este simulador particular de Pacman, las observaciones son **caracteres ascii** y no píxeles o algún valor numérico, por lo que hubo que hacer bastante procesamiento de datos, que pudo no haber sido la mejor manera.\n",
    "\n",
    "Se exploraron varias opciones en esta dirección, en especial, para cada caracter ascii diferente observado (10 en total):\n",
    "* un número entre 0 y 1 (0/10, 1/10, 2/10, ... , 9/10)\n",
    "* un one-hot vector de 10 dimensiones\n",
    "* una fusión de las anteriores, aprovechando el triple canal de entrada de colores de la red neuronal convolucional, dividiendo en cada canal:\n",
    " \n",
    " Canal 1: enemigos / agentes\n",
    " \n",
    " Canal 2: objetos interactivos / pellets\n",
    " \n",
    " Canal 3: objetos inertes / muros y límites del mapa\n",
    "\n",
    "A pesar de que conceptualmente parecen ideas sólidas (sobre todo las últimas dos que agregan cierta abstracción/conocimiento previo a la representación del problema), el algoritmo parece no converger, o lo hace muy lentamente.\n",
    "\n",
    "Dada la **amplia** variedad de factores que pueden ser la causa de ésto (hiperparámetros, representación pobre, errores de programación y manejo del modelo, modelo de NN demasiado grande o poco apto, etc) y las no-tan-claras capacidades de convergencia de este tipo de modelo no-lineal, se decidió por avanzar en los temas del trabajo práctico, dejando este algoritmo sin una solución/implementación satisfactoria.\n",
    "\n",
    "Para ver el código del agente '*NNQAgentAllQActionsOut*':\n",
    "[./ cs188x_pacman / qLearningAgents.py](./cs188x_pacman/qLearningAgents.py)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-17T01:50:15.094377Z",
     "start_time": "2019-07-17T01:50:15.092390Z"
    },
    "code_folding": [
     0
    ],
    "run_control": {
     "marked": false
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# NN Agent-pNNQAgent\n",
    "#options = [\"-pNNQAgentAllQActionsOut\", \"-x500\", \"-n510\", \"-k2\", \"-gDirectionalGhost\",\"-lsmallGridMoreFood\"]\n",
    "#prefs = ['--pacman',     'NNQAgentAllQActionsOut',\n",
    "#         '--numTraining','500',\n",
    "#         '--numGames',   '501',\n",
    "#         '--numghosts',  '2',\n",
    "#         '--ghosts',     'DirectionalGhost',\n",
    "#         '--layout',     'smallGridMoreFood']\n",
    "#args = readCommand(prefs)  # Get game components based on options\n",
    "#runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Extensiones\n",
    "\n",
    "El tipo de dificultades anterior no es ajeno al área de Deep Reinforcement Learning en general, por lo que existen varios métodos o *trucos* para mejorar las capacidades de este tipo de algoritmos. Entre ellos:\n",
    "\n",
    "##### DQN con Atari\n",
    "Paper: [Playing Atari with Deep Reinforcement Learning](https://github.com/LecJackS/saved_models/blob/master/gym_pacman/resources/Playing_Atari_with_Deep_Reinforcement_Learning_-_DQN.pdf)\n",
    "\n",
    "* **Replay Buffer (DQN):**\n",
    "\n",
    "  Reemplaza el aprendizaje online de los anteriores algoritmos, por sampleo de mini-batches de un buffer/historial de transiciones \n",
    "  $T_{t=0}, T_{t=1}, T_{t=2}, ... , T_{t=n}$\n",
    "  \n",
    "  Siendo $T_{t=i}$: [observación > accion > nueva observación]\n",
    "  \n",
    "  Cada sample se suele observar varias veces antes de ser descartado(4-8 en DQN).\n",
    "  \n",
    "  Si se *samplea* de manera aleatoria entre los datos guardados, obtendremos una data con **características más iid**.\n",
    "  \n",
    "  **OBS: Replay Buffer $\\approx$ Modelo**\n",
    "  \n",
    "  Tener un *replay buffer* suele ser considerado como una forma de *Modelo* (aproximado), ya que las observaciones fueron *samples* del environment y mantienen su distribución.\n",
    "  \n",
    "  Volver a observar datos guardados de este buffer, es equivalente a obtener muestras de un Modelo de tipo *caja negra*, del cual suponemos tiene distribución similar a la del *environment*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **Target Network (DQN):**\n",
    "\n",
    "  Se tiene una segunda NN con **el mismo** modelo (de por ejemplo la Value Function) pero con otros parámetros (típicamente llamados $\\theta^{-}$)\n",
    "  \n",
    "  Se usa para realizar *bootstraping*, por lo que la idea detrás es que sea **una función más estable o estacionaria** que la Función de Valor con parámetros $\\theta$.\n",
    "  \n",
    "  Más en la dirección del *Aprendizaje Supervisado*, mientras que con *Replay Buffer* se actualizan los parámetros $\\theta$ en cada mini-batch, los parámetros $\\theta^{-}$ de la *Target Network* se \"actualizan\" de manera más esporádica (ej. cada 10.000 time steps).\n",
    "  \n",
    "  Esta actualización de los parámetros $\\theta^{-}$ es simplemente sobreescribir los $\\theta^{-}$ ya existentes con los $\\theta$ aprendidos usando *Replay Buffer*, y **mantenerlos fijos** durante el resto de la franja de tiempo, en la cual se usa este red para realizar *bootstraping*.\n",
    "  \n",
    "  Cabe destacar que ahora la loss function es función de ambas redes (con $\\theta$ y $\\theta^-$):\n",
    "  \n",
    "  $loss(\\theta) = \\frac{1}{2} \\, (R_{i+1} + \\gamma \\, [\\![ \\mathop{max}_{a} q_{\\theta^-} (S_{i+1}, a) ]\\!] - q_\\theta(S_i, A_i))^2 $\n",
    "  \n",
    "  Donde los dobles corchetes $[\\![ * ]\\!]$ indican que **no** debe *fluir* ese gradiente (en caso contrario es llamada *Residual Network*, generalmente con **menor performance**, por no respetar *causalidad*).\n",
    "  \n",
    "  Con esta *Target Network* extra se logra (no siempre) mayor estabilidad en el algoritmo, aunque **no queda claro cuándo y en qué tipo de problemas**.\n",
    "  \n",
    "  Una observación de [Vlad Mnih](https://www.cs.toronto.edu/~vmnih/) (uno de los autores de DQN) es que ***a medida que la capacidad o \"tamaño\" del modelo de red neuronal incrementa, la Target Network se vuelve menos importante***.\n",
    "  \n",
    "  Una hipótesis (no formal) de por qué esto es así, se basa en que teniendo un **modelo neuronal pequeño**, los updates de cada acción afectarán **gran parte de la red**, volviendo a nuestro objetivo **altamente no-estacionario**.\n",
    "  \n",
    "  Mientras que con un modelo neuronal de **mayor capacidad**, cada update afectará a una **pequeña porción de la red**, por lo que el objetivo no cambiará tanto, **ganando estabilidad** y restandole importancia a los beneficios que se puedan ganar al incluir una  Target Network.\n",
    "  \n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En el caso de DQN con Atari, también fueron usadas otras estrategias como **pre-procesamiento** de los datos de entrada, ***hyper parameter tunning*** corriendo múltiples instancias con un gran poder de hardware para elegir los mejores parámetros, como con el discount factor de 0.99 elegido sobre varios, para tener cierto horizonte sobre el cual optimizar.\n",
    "\n",
    "Se logró cierta generalidad en el resultado, ya que **una vez hayados estos valores, se fijaron para todos los juegos testeados**, pero al mismo tiempo da una idea de que sigue siendo necesaria (al menos para DQN) cierta *fuerza bruta* que suplante la falta de conocimiento en el tema."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Multi-step Return\n",
    "\n",
    "![n-step-td](./img/n-step-td.jpg)\n",
    "\n",
    "Otro método que suele ayudar a encontrar un equilibrio entre **bias** y **varianza** para estos modelos, es usar como *Return* $G_t$ algo intermedio entre TD return ($G_t^{(1)}$) y MC return ($G_t^{(\\infty)}$): \n",
    "\n",
    "> El **n-step TD return**\n",
    "\n",
    "Denotaremos con superíndice $^{(n)}$ al return correspondiente a $n$ pasos (acciones por *time-step*) que tomaremos con rewards $R_{t+1}, R_{t+2}, ... ,R_{t+n}$, y una estimación a futuro $\\tilde{V}(S_{t+n})$ del último estado  (*bootstrap*), cada uno con sus respectivos descuentos $\\gamma^{i-1}$:\n",
    "\n",
    "$$G_t^{(n)} = R_{t+1} + \\gamma\\, R_{t+2}\\, + \\gamma^2\\, R_{t+3} + \\, ... \\, + \\, \\gamma^{n-1} R_{t+n} + \\gamma^{n}\\, \\tilde{V}(S_{t+n})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$G_t^{(n)} = ( \\sum_{i=1}^n \\gamma^{i-1}\\, R_{t+i} ) + \\gamma^n \\, \\tilde{V}(S_{t+n})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Con lo que obtenemos ***n-step Temporal-Difference Learning***\n",
    "\n",
    "con update:\n",
    "\n",
    "$\\tilde{V}(S_t) \\leftarrow \\tilde{V}(S_t) + \\alpha \\, (G_t^{(n)} - \\tilde{V}(S_t))$\n",
    "\n",
    "lo cual nos permite tener un control sobre un rango de acción $n$, que será otro hyperparámetro cuyo valor dependerá de cada problema."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### n como hiperparámetro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para obtener una intuición de cómo mejora nuestro algoritmo, consideremos el siguiente ejemplo:\n",
    "\n",
    "> Con política de ***random walk*** y\n",
    "> un **único reward** en un extremo del MDP\n",
    ">    \n",
    "> buscamos mejorar nuestra **estimación de la Value Function** (el valor de cada estado A-E) usando TD-error con n-step return:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considerar para 19 estados (A a S), por simplicidad solo se muestran 5  (A a E):\n",
    "![n-step-td-random-walk-silver-example](./img/n-step-td-random-walk-silver-example.png)\n",
    "\n",
    "\n",
    "![n-step-td-random-walk-hado-example](./img/n-step-td-random-walk-hado-example.png)\n",
    "\n",
    "En el eje vertical tenemos el **error de predicción**\n",
    "\n",
    "En el eje horizontal **step size** (o *learning rate*) $\\alpha$\n",
    "\n",
    "Podemos ver cómo con $G_t^{(1)}$ (o TD(0)) la curva de la **Raiz del Error Cuadrático Medio (RMSE)** se mantiene alta a pesar de lo distintos valores que puede tomar $\\alpha$.\n",
    "\n",
    "Mientras que con returns $G_t^{(n)}$ con $n$ entre 2 y 8 para el caso on-line, ó 4 y 16 para el offline, obtenemos el menor error **si elegimos el $\\alpha$ adecuado**.\n",
    "\n",
    "Y para $n > 16$ el error sigue creciendo a medida que nos acercamos a Monte Carlo ($G_t^{(\\infty)}$)\n",
    "\n",
    "Este error se verá directamente reflejado en las decisiones y consecuentes observaciones que tome el agente.\n",
    "\n",
    "* Si estamos en el rango de $n$ y $\\alpha$ de menor error, estaremos yendo en la dirección adecuada, por lo que \"avanzaremos\" hacia nuestro objetivo a mayor velocidad.\n",
    "\n",
    "* De manera opuesta, a mayor RMSE, el aprendizaje será más lento, jamás convergeremos a óptimo cercano al buscado, ya que el objetivo se seguirá \"moviendo\" a causa de la varianza, o \"apuntaremos\" en la dirección equivocada a causa del bias, convergiendo a un óptimo local.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-08T03:59:00.800520Z",
     "start_time": "2019-07-08T03:59:00.591805Z"
    }
   },
   "source": [
    "---\n",
    ">Fuente de gran parte de la sección de aproximación:\n",
    ">\n",
    ">*ReinforcementLearning 5: Function Approximation and Deep Reinforcement Learning*\n",
    ">\n",
    ">Hado van Hasselt - DeepMind\n",
    ">\n",
    ">https://www.youtube.com/watch?v=wAk1lxmiW4c\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy Approximation\n",
    "\n",
    "Hasta ahora, los algoritmos vistos hicieron uso directo de la ***Función* de Valor*** para determinar su política óptima:\n",
    "\n",
    "1. Elegir la **acción con máximo valor** a partir del estado observado.\n",
    "   \n",
    "2. Para agregar **exploración**, se elige una acción **al azar** con probabilidad epsilon $\\epsilon$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se podría entonces considerar que **aprender la Función de Valor** es un problema **más general** que el que buscamos resolver.\n",
    "\n",
    "Esto es porque **aprender la Función de Valor** a partir de una observación para **luego elegir la acción con máximo valor** entre las opciones posibles, podría reducirse a **aprender directamente la acción a elegir, a partir de una observación**, sin pasar por una función de valor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> *When solving a problem of interest, do not solve a more general problem as an intermediate step.*\n",
    "> \n",
    "> *Try to get the answer that you really need but not a more general one.*\n",
    "\n",
    "$$- \\text{Vladimir Vapnik, on 'transduction'}$$\n",
    "http://www.cs.bham.ac.uk/~jdk/transductive.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pensando en eficiencia de datos, si lo que buscamos es un comportamiento óptimo, al resolver un problema más general se necesitará **al menos** la misma cantidad de data.\n",
    "\n",
    "Por lo que aprender la política **directamente** reduciría este problema."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "Consideramos nuevamente los tres grandes grupos de aprendizaje por refuerzo.\n",
    "\n",
    "* **Model-based RL**\n",
    "\n",
    " `+` Se aprende usando Aprendizaje Supervisado (well understood)\n",
    " \n",
    " `+` Representa **toda** la información de la dinámica del *environment*\n",
    " \n",
    " `-` Muy costoso de aprender, sobre todo para problemas complejos\n",
    " \n",
    " `-` Ineficiente con los datos; aprende dinámica de **todo** lo observado\n",
    " \n",
    " `-` Objetivo captura información irrelevante\n",
    " \n",
    " \n",
    "* **Value-based RL**\n",
    "\n",
    " `+` Objetivo cercano a Control óptimo\n",
    " \n",
    " `+` *Well-understood*\n",
    " \n",
    " `-` Puede ser muy costoso de aprender, aunque la política óptima sea simple\n",
    " \n",
    " `-` Objetivo captura información irrelevante\n",
    " \n",
    "\n",
    "* **Policy-based RL**\n",
    " \n",
    " `+` Objetivo correcto: *Encontrar política óptima para estados observados*\n",
    " \n",
    " `-` Ignora información que puede ser relevante. Ineficiente con los datos.\n",
    " \n",
    " `-` Aprendizaje muy lento al comienzo, sin garantías de aprender algo *útil*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Actor-Critic\n",
    "\n",
    "![value-policy-actor-critic](./img/value-policy-actor-critic.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "center"
   },
   "source": [
    "Una forma de mantener el objetivo de ***policy-based RL*** sin perder eficiencia en los datos, es **aprender tanto la Value Function como la Policy Function**.\n",
    "\n",
    "Mientras que el objetivo sigue siendo **aprender la política óptima**, se puede aprovechar gran parte del modelo de red neuronal **para también**, tener una representación de los **valores de cada estado**.\n",
    "\n",
    "De esta forma no solo **el agente** tiene una representación más completa del estado observado, sino que **el gradiente** a seguir contendrá **información más relevante** sobre un posible mejor resultado, que si solo representara información de la política.\n",
    "\n",
    "Este tipo de modelos con *Función de Valor* y *Función de Política* se llaman ***Actor-Critic***, donde ***\"el Crítico\"*** es la **Función de Valor**, y ***\"el Actor\"*** es la **Función de Política** a seguir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![actor-critic-model](./img/actor-critic-model.png)\n",
    "\n",
    "El digrama representa un modelo básico de Actor-Critic, donde todos los parámetros están compartidos, menos en la últiima capa (*layer*) donde se dividen en los valores para cada estado posible (Critic) o la política a seguir (Actor) con probabilidades para cada acción.\n",
    "\n",
    "$\\pi (a_t | s_t; \\theta)$ y $V (s_t ; \\theta_v)$ son las funciones correspondientes a cada objetivo (Value/Policy), con $\\theta$ y $\\theta_v$ todos los parámetros de cada una (compartidos e individuales).\n",
    "\n",
    "$\\pi (a_t | s_t; \\theta)$: Devuelve la probabilidad de elegir cada acción. Las $n$ salidas suman 1.\n",
    "\n",
    "$V (s_t ; \\theta_v)$: Devuelve un valor que representa el puntaje del estado presente, siguiendo la política $\\pi_\\theta$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ventajas\n",
    "\n",
    " * Buenas propiedades de convergencia\n",
    " \n",
    " \n",
    " * Ganamos características de *Policy models*:\n",
    " \n",
    "   1. Facilmente se puede extender a **acciones de espacio contínuo**\n",
    "   \n",
    "      * Se cambia cantidad de outputs por solo dos valores: **Media** y **Desviación estándar** de una **Distribución Normal**\n",
    "      \n",
    "   2. Puede aprender **políticas estocásticas**: control sobre las **probabilidades** de cada acción \n",
    "      * Puede ser usado como de **qué tanta confianza** se tiene en cierta acción\n",
    "      * El agente puede controlar **qué tanto explora**\n",
    "      * Puede resolver problemas con **información oculta** (*Partially Observable MDPs* o *POMDPs*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loss and Gradient\n",
    "\n",
    "Necesitamos **cuantificar la calidad de la policy $\\pi_\\theta$** para poder mejorarla.\n",
    "\n",
    "Para eso es necesario convertiro en un **problema de optimización**.\n",
    "\n",
    "#### Policy Objective Functions ( funciones objetivo para las políticas)\n",
    "\n",
    "Vamos a querer **maximizar** estos objetivos, que representarán cierto *puntaje* de la política:\n",
    "\n",
    "1. ***Start value*** $J_1(\\theta)$: Si el *environment* es episódico, puede usarse ***start value*** $J_1(\\theta)$ (valor de comienzo)\n",
    " \n",
    " $$J_1(\\theta) = \\mathbf{v}_{\\pi_\\theta} (s_1)$$\n",
    " \n",
    " A partir de un estado inicial $(s_1)$, queremos maximizar $\\mathbf{v}_{\\pi_\\theta}(s_1)$, que es el valor del primer estado, siguiendo la política $\\pi_\\theta$\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "2. Si el *environment* no tiene un *start state* bien definido, tenemos dos opciones similares entre sí:\n",
    " \n",
    " * ***Average value*** $J_{avV} (\\theta)$ (valor promedio)\n",
    " \n",
    "  $$J_{avV}(\\theta) = \\sum_s d_{\\pi_\\theta} (s) \\, \\mathbf{v}_{\\pi_\\theta} (s)$$\n",
    "  \n",
    "  $d_{\\pi_\\theta}(s)$ distribución **inducida por la política $\\pi_\\theta$** que el agente sigue.\n",
    "  \n",
    "  con $d_{\\pi_\\theta}(s) = p \\, (S_t=s | \\pi_\\theta)$ la probabilidad de estar en el estado $s$ a largo plazo\n",
    "\n",
    "  `+` Equivalente al *ratio* de tiempo que estaremos en $s$ **siguiendo la política $\\pi$**\n",
    " \n",
    " `+` Para **estados continuos** la integral reemplaza la sumatoria.\n",
    " \n",
    " `+` Da **prioridad a los estados que visita**, sin darle importancia a los que no.\n",
    " \n",
    " ---\n",
    " \n",
    "3. ***Average reward per time step*** $J_{avR} (\\theta)$ (reward promedio en cada paso)\n",
    " \n",
    " $$J_{avR}(\\theta) = \\sum_s d_{\\pi_\\theta} (s) \\, \\sum_a \\pi_\\theta(s,a) \\sum_r p(r|s,a)\\, r$$\n",
    " \n",
    " `+` Notar que **solo usa *rewards* inmediatos**, no $\\mathbf{v}_{\\pi_\\theta}(s)$\n",
    " \n",
    " Ésto vale pues por la sumatoria de afuera, estamos sumando sobre todos los estados, que capturan la dinámica de la misma forma que $\\mathbf{v}_{\\pi_\\theta}(s)$\n",
    "\n",
    " `+` Muy común su uso en plots o gráficos en investigación y papers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**OBS:**\n",
    "\n",
    "Es importante remarcar que las distribuciones $d_{\\pi_\\theta}$ de los estados son **en función de $\\pi_\\theta$**, la política paramétrica actual.\n",
    "\n",
    "Esto nos asegura que en el caso de tomar samples, sean sobre la distribución correcta, que es siguiendo la politica política actual, que es a quien queremos corregir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How to sample\n",
    "\n",
    "#### Toy example\n",
    "\n",
    "Consideramos $J(\\theta) = \\mathbf{E} \\, [ R(S,A) ]$ para el caso ***bandits***\n",
    "\n",
    "con $\\mathbf{E} \\, [ R(S,A) ]$ esperanza **sobre estados y acciones**\n",
    "\n",
    "Queremos **un gradiente**, pero samplear esa esperanza nos devuelve **un valor escalar** $R_{t+1}$ que no podemos usar para actualizar la función de política.\n",
    "\n",
    "Para solucionar eso, podemos usar esta equivalencia (demostración a continuación):\n",
    "\n",
    "> $$\\nabla_\\theta \\mathbf{E} \\, [ R(S,A) ] =  \\mathbf{E} \\, [ \\nabla_\\theta \\log \\pi_\\theta (A | S) \\, R(S,A) ]$$\n",
    "\n",
    "En la que ahora **tenemos la esperanza de un gradiente** que sí podemos samplear."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### \"Score function trick\" o \"REINFORCE trick\" o \"log-likelihood trick\"\n",
    "\n",
    "sea:\n",
    "\n",
    "$d(s)$ una **distribución sobre los estados** (variables aleatorias)\n",
    "\n",
    "$\\pi_\\theta (a | s)$ **distribución sobre las políticas** (estocásticas) \n",
    "\n",
    "$R (s, a)$ el reward (o reward esperado) luego de tomar acción $a$ en estado $s$ \n",
    "\n",
    "$$\\nabla_\\theta \\mathbf{E} \\, [ R(S,A) ] = \\nabla_\\theta \\sum_s d(s) \\sum_a \\pi_\\theta (a | s) \\, R (s, a)$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Demostración\n",
    "\n",
    "Movemos el gradiente al interior de la sumatoria, ya que solo $\\pi_\\theta$ depende de $\\theta$\n",
    "\n",
    "$$= \\sum_s d(s) \\sum_a \\nabla_\\theta \\pi_\\theta(a|s) \\, R(s,a)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Multiplicamos y dividimos por $\\pi_\\theta (a|s)$, para darle forma de esperanza (cada acción es pesada por la probabilidad de ser elegida)\n",
    "\n",
    "$$= \\sum_s d(s) \\sum_a \\pi_\\theta (a|s) \\frac{\\nabla_\\theta \\pi_\\theta (a|s)}{\\pi_\\theta(a|s)} R(s,a) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sabiendo $\\nabla \\log y = \\frac{1}{y} \\nabla y$, reescribimos\n",
    "$$= \\sum_s d(s) \\sum_a \\pi_\\theta (a|s) \\, \\nabla_\\theta \\log \\pi_\\theta(a|s) \\, R(s,a)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo cual es la esperanza del gradiente del logaritmo de la política $\\pi$, multiplicado por el reward $R(s,a)$\n",
    "\n",
    "> $$\\nabla_\\theta \\mathbf{E} \\, [ R(S,A) ] = \\mathbf{E} \\, [ \\nabla_\\theta \\log \\pi_\\theta (A | S) \\, R(S,A) ]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que ahora podemos samplear y usar como update para los parámetros $\\theta$\n",
    "\n",
    "> $$\\theta_{t+1} = \\theta_t + \\alpha \\, R_{t+1} \\, \\nabla_\\theta \\log \\pi_{\\theta_t} (A_t | S_t)$$\n",
    "\n",
    "Que bajo condiciones normales **podemos asumir que alcanzará un óptimo local**, ya que sigue el gradiente de nuestro objetivo:\n",
    "\n",
    "> la **Función de Política paramétrica $\\pi_\\theta$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La intuición detrás de este update es que la política será modificada de forma tal que **las acciones con mayor reward aumentarán su probabilidad de ser elegidas**, mientras que **las de menor reward o reward negativo, incrementarán menos o reducirán la probabilidad de ser elegidas**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejemplo concreto de update con política *Softmax* (se usa a menudo)\n",
    "\n",
    "Sea $\\pi_\\theta(a|s)$ una política softmax sobre una función de preferencias $h(s,a)$\n",
    "\n",
    "$$\\pi_\\theta(a|s) = \\frac{e^{h(s,a)}}{\\sum_b e^{h(s,b)}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El gradiente de la probabilidad logarítmica $\\log \\pi_\\theta (a|s)$ será\n",
    "\n",
    "> $$ \\nabla_\\theta \\log \\pi_{\\theta}(a|s) = \\nabla_\\theta h(s,a) - \\sum_b \\pi_\\theta(b|s) \\nabla_\\theta h(s,b) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Queremos extenderlo al caso multi-step, donde\n",
    "\n",
    "1. Hay **secuencialidad**\n",
    "2. No solo hay rewards inmediatos, sino *valores* (*values*) con dependencias temporales\n",
    "\n",
    "Para ello tenemos las siguientes **herramientas teóricas**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy Gradient Theorem (con demostración)\n",
    "\n",
    "* Nos permite *reemplazar* los rewards instantáneos en la ecuación antes derivada, con *long-term values* $q_\\pi(s,a)$\n",
    "\n",
    "* Aplica para objetivos (*objectives*):\n",
    "  * Estado de comienzo $J=J_1$ (start state objective)\n",
    "  * Reward promedio $J_{avR}$ (average reward objective)\n",
    "  * Valor promedio $\\frac{1}{1-\\gamma} J_{avV}$ (average value objective)\n",
    "\n",
    "#### Teorema:\n",
    "\n",
    "> Para cualquier política diferenciable $\\pi_\\theta(s,a)$,\n",
    ">\n",
    "> para cualquier función objetivo (de la política) $J=J_1$, $J_{avR}$, ó $\\frac{1}{1-\\gamma} J_{avV}$,\n",
    ">\n",
    "> el gradiente de la política es\n",
    "$$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ q_{\\pi_\\theta}(S,A) \\, \\nabla_\\theta \\log \\pi_\\theta (A|S) \\right]$$\n",
    "\n",
    "Con la esperanza $\\mathbf{E} [ * ]$ tomada sobre estados y acciones."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy Gradient sobre trayectorias\n",
    "\n",
    "La siguiente es una demostración de por que no es necesario saber cómo la política afecta los distintos estados.\n",
    "\n",
    "Sea la trayectoria de datos *zeta* $\\zeta = S_0,A_0,R_1,S_1,A_1,R_2,S_2,...$ con return $G(\\zeta)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sabemos que el return $G(\\zeta)$ es una muestra insesgada del Valor de $\\zeta$ \n",
    "\n",
    "$$\\nabla_\\theta J_\\theta (\\pi) = \\nabla_\\theta \\mathbf{E}[G(\\zeta)]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sobre lo cual podemos aplicar el score / REINFORCE / log-likelihood trick\n",
    "\n",
    "$$\\nabla_\\theta \\mathbf{E}[G(\\zeta)] = \\mathbf{E}[G(\\zeta) \\nabla_\\theta \\log p(\\zeta)]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Expandimos $\\nabla_\\theta \\log p(\\zeta)$, que es la probabilidad de obtener esta trayectoria en particular\n",
    "\n",
    "$$\\nabla_\\theta \\log p(\\zeta) = \\nabla_\\theta \\log \\, \\left[ \\, p(S_0) \\pi(A_0|S_0) p(S_1|S_0, A_0) \\pi(A_1|S_1) \\, ...\\, \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Logaritmo del producto es suma de los logaritmos\n",
    "\n",
    "$$= \\nabla_\\theta  \\left[ \\, \\log p(S_0) + \\log \\pi(A_0|S_0) + \\log  p(S_1|S_0, A_0) + \\log \\pi(A_1|S_1) \\, + \\, ...\\, \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Al aplicar la derivada con respecto a $\\theta$ (parámetros de la política), solo quedan los términos que la involucran\n",
    "\n",
    "$$= \\nabla_\\theta  \\left[ \\, \\log \\pi_\\theta(A_0|S_0) + \\log \\pi_\\theta(A_1|S_1) \\, + \\, ...\\, \\right]$$\n",
    "\n",
    "$$\\nabla_\\theta \\log p(\\zeta) = \\nabla_\\theta \\sum_{t=0} \\log \\pi_\\theta (A_t|S_t) $$\n",
    "\n",
    "Lo que indica que **los parámetros solo afectan las decisiones que tome el agente** (al seguir esa política) y no la dinámica del environment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Volviendo\n",
    "$$\\nabla_\\theta J_\\theta (\\pi) = \\mathbf{E}[G(\\zeta) \\nabla_\\theta \\log p(\\zeta)]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ =  \\mathbf{E}\\left[ G(\\zeta) \\, \\nabla_\\theta \\sum_{t=0} \\log \\pi (A_t|S_t) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Expandiendo el return $G(\\zeta)$ como la suma de los rewards\n",
    "\n",
    "> $$\\nabla_\\theta J_\\theta (\\pi) = \\mathbf{E}\\left[\\left( \\sum_{t=0} R_{t+1} \\right)\\left( \\nabla_\\theta \\sum_{t=0} \\log \\pi (A_t|S_t) \\right)\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Más general, el caso con discount factor $\\gamma$\n",
    "\n",
    "> $$\\nabla_\\theta J_\\theta (\\pi) = \\mathbf{E}\\left[\\left( \\sum_{t=0} \\gamma^t R_{t+1} \\right)\\left( \\nabla_\\theta \\sum_{t=0} \\log \\pi (A_t|S_t) \\right)\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Baselines\n",
    "\n",
    "Una forma de **reducir la varianza** de este tipo de objetivos es **usar la diferencia** entre el **reward** y una ***baseline*** en lugar de solamente el return anteriormente usado.\n",
    "\n",
    "De esta forma no haremos *updates* proporcionales al reward/return directamente, sino a la **diferencia** de este reward con respecto a la *baseline*, la cual es basicamente un **reward promedio esperado**.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En general, sea $b$ baseline, función que no dependa de las acciones (aunque puede depender de los estados)\n",
    "\n",
    "Expandimos $A_t$ de modo que ahora las acciones no son aleatorias, solo los estados\n",
    "$$\\mathbf{E} \\left[ b \\nabla_\\theta \\log \\pi(A_t|S_t) \\right] = \\mathbf{E} \\left[ \\sum_a \\pi(a|S_t) \\, b \\, \\nabla_\\theta \\log \\pi(a|S_t) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nuevamente, score function trick, pero en reversa\n",
    "\n",
    "$$= \\mathbf{E} \\left[  \\, b \\, \\nabla_\\theta \\sum_a \\pi(a|S_t) \\right]$$\n",
    "\n",
    "$$= \\mathbf{E} \\left[  \\, b \\, \\nabla_\\theta \\, 1 \\right]$$\n",
    "\n",
    "$$ = 0$$\n",
    "\n",
    "Esto es posible pues $b$ **no** depende de las acciones, por lo que podemos *moverlo* fuera de la sumatoria.\n",
    "\n",
    "Si dependiera, ésto **no** sería posible.\n",
    "\n",
    "Lo que lleva a dudar de la utilidad de esta *baseline*, pues sabemos que **los rewards dependen de las acciones tomadas**.\n",
    "\n",
    "Pero por **causalidad**, no dependen **de las que se tomarán**.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Volviendo a la demostracion anterior, sabíamos que\n",
    "\n",
    "> $$\\nabla_\\theta J_\\theta (\\pi) = \\mathbf{E}\\left[\\left( \\sum_{t=0} R_{t+1} \\right)\\left( \\nabla_\\theta \\sum_{t=0} \\log \\pi (A_t|S_t) \\right)\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Particularmente $\\sum_{t=0}^k R_{t+1}$ **no** depende de las acciones en tiempos **posteriores** $A_{k+1}, A_{k+2}, A_{k+3} ...$\n",
    "\n",
    "Reordeno sumatorias\n",
    "$$= \\mathbf{E}\\left[ \\sum_{t=0} \\nabla_\\theta \\log \\pi (A_t|S_t) \\sum_{i=0} R_{i+1} \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solo considero rewards $R_{i+1}$ **posteriores** a acciones $A_{t}$\n",
    "$$= \\mathbf{E}\\left[ \\sum_{t=0} \\nabla_\\theta \\log \\pi (A_t|S_t) \\sum_{i=t} R_{i+1} \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reescribo la última sumatoria como el valor $q$ de la política $\\pi$, pues está dentro de la esperanza\n",
    "> $$= \\mathbf{E}\\left[ \\sum_{t=0} \\nabla_\\theta \\log \\pi (A_t|S_t) q_\\pi(S_t,A_t) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que es exactamente el resultado de **Policy Gradient Theorem** (excepto por un factor de escalamiento en cuanto a cantidad de estados considerados)\n",
    "\n",
    "> $$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ q_{\\pi_\\theta}(S,A) \\, \\nabla_\\theta \\log \\pi_\\theta (A|S) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cada uno de los updates será ahora usando $\\nabla_\\theta \\log \\pi (A_t|S_t)$ de esta acción $A_t$ particular, multiplicado por el valor estimado que tendrá esta acción.\n",
    "\n",
    "De esta forma **podemos obtener muestras individuales** o por ***batches*** sin necesidad de completar la suma para todo $t$, y aún así tener un **gradiente válido** para utilizar en el algoritmo de actualización política."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Baselines, again\n",
    "\n",
    "Como fue mencionado anteriormente, usar *baselines* reduce la varianza de nuestro modelo.\n",
    "\n",
    "Por lo que podemos aplicarla (nuevamente) a nuestro objetivo, el resultado final del ***Policy Gradient Theorem***\n",
    "\n",
    "$$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ \\nabla_\\theta \\log \\pi_\\theta (A_t|S_t) \\,  q_{\\pi_\\theta}(S_t,A_t) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Una buena *baseline* es $\\mathbf{v}_{\\pi}(S_t)$, ya que no depende de las acciones y podemos restarla al valor de la acción\n",
    "\n",
    "$$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ \\nabla_\\theta \\log \\pi_\\theta (A_t|S_t) \\, \\left( q_{\\pi_\\theta}(S_t,A_t) - \\mathbf{v}_{\\pi_\\theta} (S_t) \\right) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Donde típicamente usamos **aproximaciones** y no los valores reales:\n",
    "\n",
    "* $\\mathbf{v}_w(s)$ se estima explícitamente (ej con on policy TD learning)\n",
    "\n",
    "\n",
    "* $q_{\\pi_\\theta}(S_t,A_t)$ se obtiene como una muestra $G_t^{(n)}$\n",
    "\n",
    "  pues\n",
    "  \n",
    "  $q_{\\pi_\\theta}(S_t,A_t) \\approx G_t^{(n)}$\n",
    "  \n",
    "   .\n",
    "  * Ejemplo de muestra (*sample*) con **1-step** return, para usar en lugar de $q_{\\pi_\\theta}(S_t,A_t)$:\n",
    "  \n",
    "    $q_{\\pi_\\theta}(S_t,A_t) \\approx G_t^{(1)} = R_{t+1} + \\gamma \\, \\mathbf{v}_w(S_{t+1}) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ambas aproximaciones juntas son exactamente el **1-step TD-error** o ***advantage***\n",
    "\n",
    "> $$R_{t+1} + \\gamma \\, \\mathbf{v}_w(S_{t+1}) - \\mathbf{v}_w(S_t)$$\n",
    "\n",
    "Reemplazando una vez más en el resultado del Policy Gradient Theorem con baseline:\n",
    "\n",
    "$$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ \\nabla_\\theta \\log \\pi_\\theta (A_t|S_t) \\, \\left( q_{\\pi_\\theta}(S_t,A_t) - \\mathbf{v}_{\\pi_\\theta} (S_t) \\right) \\right]$$\n",
    "\n",
    "> $$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ \\nabla_\\theta \\log \\pi_\\theta (A_t|S_t) \\, \\left( R_{t+1} + \\gamma \\, \\mathbf{v}_w(S_{t+1}) - \\mathbf{v}_w(S_t) \\right) \\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Terreno conocido\n",
    "\n",
    "El *critic* (la *value function*) está resolviendo ***Policy Evaluation*** para la política actual.\n",
    "\n",
    "Quiere conocer *el valor* de la política $\\pi_\\theta$ con parámetros actuales $\\theta$\n",
    "\n",
    "Soluciones a esta pregunta fueron exploradas en TPs anteriores:\n",
    "* Monte-Carlo policy evaluation\n",
    "* Temporal-Difference learning\n",
    "* n-step TD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Actor-Critic: Pseudocódigo e Implementación\n",
    "\n",
    "Haciendo uso de las herramientas matemáticas anteriores, podemos formular en pseudocódigo un agente de tipo ***Actor-Critic***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vanilla Actor-Critic\n",
    "\n",
    "* **Critic:** Actualiza los parámetros $w$ de $\\mathbf{v}_w$ usando ***1-step TD*** (podría ser n-step)\n",
    "* **Actor:** Actualiza los parámetros $\\theta$ de $\\pi_\\theta$ usando ***Policy Gradient***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**function** ADVANTAGE_ACTOR_CRITIC\n",
    "> `# Inicializar estado inicial y weights de ambas redes`\n",
    "> \n",
    "> Initialize $s$, $w$, $\\theta$\n",
    ">  \n",
    ">  **for** $t = 0,1,2,...$ **do**\n",
    ">\n",
    ">>    `# Elegir una accion a partir de politica pi`\n",
    ">>\n",
    ">>    Sample $A_t \\sim \\pi_\\theta(S_t)$\n",
    ">>\n",
    ">>    `# Tomar esa accion > recibir nueva observacion`\n",
    ">>\n",
    ">>    Sample $R_{t+1}$ and $S_{t+1}$\n",
    ">>\n",
    ">>    `# 1-step TD-error o Advantage function`\n",
    ">>\n",
    ">>    $\\delta_t = R_{t+1} + \\gamma \\, \\mathbf{v}_w(S_{t+1}) - \\mathbf{v}_w(S_t)$\n",
    ">>\n",
    ">>    `# Update a parametros del Critic con TD(0)`\n",
    ">>\n",
    ">>    $w \\leftarrow w + \\beta \\, \\delta_t \\nabla_w \\mathbf{v}_w(S_t)$\n",
    ">>\n",
    ">>    `# Update a parametros del Actor con Policy Gradient`\n",
    ">>\n",
    ">>    $\\theta \\leftarrow \\theta + \\alpha \\, \\delta_t \\, \\nabla_\\theta \\log \\pi_\\theta(A_t|S_t)$\n",
    ">\n",
    ">  **end for**\n",
    ">\n",
    ">  `# Update asincrónico a parámetros globales usando gradientes locales`\n",
    "\n",
    "**end function**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Siendo $\\alpha , \\beta$ step-sizes, denotados con símbolos diferentes para indicar que no necesariamente deben ser iguales."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Más formalmente, del paper: [***\"Asynchronous Methods for Deep Reinforcement Learning\"***](https://github.com/LecJackS/saved_models/blob/master/gym_pacman/resources/Asynchronous%20Methods%20for%20Deep%20Reinforcement%20Learning.pdf)\n",
    "\n",
    "![./img/A3C-pseudocode.png](./img/A3C-pseudocode.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Advantage Actor-Critic: Detalles de implementación\n",
    "\n",
    "En la práctica, Actor-Critic suele ser aplicado junto con otras caractéristicas que lo vuelven más **robusto y eficiente** con los datos, al que suele llamarse ***Advantage Actor-Critic***.\n",
    "\n",
    "* Es posible agregar una **representación** no solo del estado observado, sino algo con información del pasado.\n",
    "  \n",
    "  ej: Con una capa de ***LSTM***: agrega la representación\n",
    "  \n",
    "  $( S_{t-1}, O_t) \\rightarrow S_t$\n",
    "  \n",
    "  \n",
    "* Se mantienen las dos redes (funciones paramétricas) Value y Policy Functions:\n",
    "  \n",
    "  * $\\mathbf{v}_w: S \\rightarrow \\mathbf{v}$\n",
    "  \n",
    "  * $\\pi_\\theta: S \\rightarrow \\pi$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **Asynchronous Actor-Critic**\n",
    "\n",
    "  Usa **copias o variantes de la política** y las corre en varias instancias del simulador (ej Atari) con políticas $\\pi_\\theta^m$, donde $m$ es el índice que caracteriza a esta variante de política en particular, corriendo cada una en un proceso separado.\n",
    "  \n",
    "  $( S_{t-1}^m,O_t^m) \\rightarrow S_t$ para cada $m$ proceso\n",
    "  \n",
    "  De esta manera se tienen **más datos al mismo tiempo**, similares entre sí, pero que permiten capturar **más información** del ambiente.\n",
    "  \n",
    "  Policy gradient se aplica de la misma manera que antes, pero **el gradiente de cada proceso** se usa para actualizar **los pesos de un modelo central**.\n",
    "  \n",
    "  Usualmente se mantienen las políticas para todos los procesos, o en el caso contínuo, se samplean las acciones usando distintas distribuciones.\n",
    "  \n",
    "  Sigue manteniendo **una sola red para el Crítico** (Value Function).\n",
    "  \n",
    "  Recibe el nombre al utilizarlo junto con un grupo de ***parámetros central*** $\\theta^+$ al que cada ciertas iteraciones, cada una de estas copias corriendo por separado actualiza de manera asincrónica.\n",
    "  \n",
    "  Los modelos locales copian los pesos del modelo global **luego de cada episodio**, manteniendo una política actualizada.\n",
    "  \n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Sigue haciendo uso de **$n$-step TD loss** para $\\mathbf{v}_w$\n",
    "  \n",
    "  $$l(w) = \\frac{1}{2} \\left( G_t^{(n)} - \\mathbf{v}_w(S_t) \\right)^2 $$\n",
    "  \n",
    "  donde $G_t^{(n)} = R_{t+1} + \\gamma R_{t+2} \\, + \\, ... + \\, \\gamma^{n-1} [\\![ \\mathbf{v}_w(S_{t+n})]\\!]$\n",
    "  \n",
    "  con $[\\![ * ]\\!]$ indicando que debe detenerse el gradiente al usar bootstraping evaluando el ultimo valor en la NN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Se utiliza **una variante** de **n-step REINFORCE** ***loss*** para actualizar $\\pi_\\theta$\n",
    "  \n",
    "  Lenguajes como Tensorflow, Pytorch, etc, utilizan optimizadores que esperan cierto ***loss*** a minimizar\n",
    "  \n",
    "  En las demostraciones de arriba con *Policy Gradient*, obtuvimos un **gradiente**, un *update*:\n",
    "  \n",
    ">  $$\\nabla_\\theta J(\\theta) =  \\mathbf{E} \\left[ \\nabla_\\theta \\log \\pi_\\theta (A_t|S_t) \\, \\left( G_t^{(n)} - \\mathbf{v}_w(S_t) \\right) \\right]$$\n",
    "\n",
    "  En forma de update, lo escribimos como:\n",
    ">  $$\\theta \\leftarrow \\theta + \\alpha \\, \\delta_t \\, \\nabla_\\theta \\log \\pi_\\theta(A_t|S_t)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "por lo que debemos reescribir nuestro objetivo para que cuando el optimizador tome su gradiente, recupere (al derivar) el update que queremos\n",
    "\n",
    "> **Loss**\n",
    "> $$l(\\theta) = \\left[ G_t^{(n)} - \\mathbf{v}_w(S_t) \\right] \\log \\pi_\\theta (A_t, S_t)$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Simple demostración:**\n",
    "\n",
    "$\\left[ G_t^{(n)} - \\mathbf{v}_w(S_t) \\right]$ no depende de $\\theta$\n",
    "\n",
    "Derivamos\n",
    "$$l'(\\theta) = \\left[ G_t^{(n)} - \\mathbf{v}_w(S_t) \\right] \\frac{1}{\\pi_\\theta(A_t, S_t)} \\nabla_\\theta \\pi_\\theta(A_t, S_t)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mismo truco que antes: $\\nabla \\log y = \\frac{1}{y} \\nabla y$\n",
    "\n",
    "$$l'(\\theta) = \\left[ G_t^{(n)} - \\mathbf{v}_w(S_t) \\right] \\nabla \\log \\pi_\\theta(A_t, S_t)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* uso de **Optimizadores** para minimizar ***losses***\n",
    "\n",
    "  Teniendo ahora los *updates* en forma de *losses* para ambas funciones de Valor y Política, se pueden usar directamente los optimizadores de la librería/lenguaje usado (ej Adam optimizer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "> Fuente de gran parte de la sección de *Policy Gradient*:\n",
    ">\n",
    ">Reinforcement Learning 6: Policy Gradients and Actor Critics\n",
    ">\n",
    ">https://www.youtube.com/watch?v=bRfUxQs6xIM\n",
    ">\n",
    ">Hado van Hasselt - DeepMind\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Asynchronous Advantage Actor Critic (A3C) - Código\n",
    "\n",
    "Con los detalles de implementación mencionados, ya puede programarse y esperar buenos resultados usando valores estándards para los hiperparámetros.\n",
    "\n",
    "Para este algoritmo se utilizó el simulador de pacman anterior, *portado* al entorno de OpenAI Gym, que facilita en gran medida el manejo de transiciones y pruebas con el algoritmo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![input-to-nn-channel-combined](./img/snaps-0-1-2-3.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecutando las siguientes celdas puede entrenarse o testear un agente A3C con **varios procesos asincrónicos simultáneos**.\n",
    "\n",
    "Es importante notar que la cantidad de procesos es **una base clave** en este algoritmo, que **utiliza procesos de bajos recursos** que no precisan una GPU, y pueden ejecutarse en paralelo **en un simple CPU**.\n",
    "\n",
    "De esta manera se tienen updates de data iid casi al mismo tiempo, convirtiendo el proceso on-line de actualización de parámetros, en algo más cercano a **aprendizaje supervisado**.\n",
    "\n",
    "La **cantidad máxima** de procesos está **limitada por la relevancia de los gradientes** que puedan aportar, es decir, superada cierta cantidad de procesos (ej 32) los updates asincrónicos serán **con respecto a funciones que *ya* fueron actualizadas** varias veces, y por ende, el gradiente *antiguo* **no se corresonderá** con la mejor dirección para actualizar estas funciones.\n",
    "\n",
    "**Nota al márgen:** Este algoritmo (como DQN) fue diseñado tomando como referencia la **gran eficiencia con los datos de algoritmos de aprendizaje supervisado** y sus excelentes capacidades de convergencia (a partir de buenos datos), por lo que es correcto relacionarlos de esta forma.\n",
    "\n",
    "En `gym_pacman/tensorboard` pueden verse los *losses* de cada uno de los procesos a través del tiempo ejecutando desde una terminal\n",
    "\n",
    "> `tensorboard --logdir=./gym_pacman/tensorboard`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Training\n",
    "\n",
    "En las primeras 10 partidas entrenadas desde cero ya pueden verse buenas tendencias en el agente.\n",
    "\n",
    "Para interrumpir el entrenamiento, usar botón de ***stop kernel*** de la notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "start_time": "2019-07-19T17:06:28.778Z"
    }
   },
   "outputs": [],
   "source": [
    "# First restart kernel to load new simulator:\n",
    "import os\n",
    "os._exit(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T17:41:33.874320Z",
     "start_time": "2019-07-19T17:41:33.868280Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original directory:\n",
      " /home/jack/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C\n",
      "Moved to:\n",
      " /home/jack/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/gym_pacman\n"
     ]
    }
   ],
   "source": [
    "# Change dir to run python files in subdirectory ./gym_pacman\n",
    "import os\n",
    "#os.chdir('../')\n",
    "ORIGINAL_DIR = os.getcwd()\n",
    "try:\n",
    "    gym_pacman_dir = './gym_pacman'\n",
    "    os.chdir(gym_pacman_dir)\n",
    "    print(\"Original directory:\\n\", ORIGINAL_DIR)\n",
    "    print(\"Moved to:\\n\", os.getcwd())\n",
    "except:\n",
    "    print(\"Couldn't change to ./gym_pacman folder. Are you already there?\")\n",
    "    print(\"Current directory:\", os.getcwd())\n",
    "# Or use directly\n",
    "#os.chdir('/home/user/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/gym_pacman')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T17:08:12.885133Z",
     "start_time": "2019-07-19T17:07:25.358662Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Agent progress details are displayed on this jupyter notebook TERMINAL (not here)\n",
      "\n",
      "Getting number of NN inputs/outputs for layout random_mnih2016\n",
      "Loading previous weights for random_mnih2016... Done.\n"
     ]
    }
   ],
   "source": [
    "from train import train\n",
    "from argparse import Namespace\n",
    "args = Namespace(beta =0.01,\n",
    "                 gamma=0.99,\n",
    "                 tau=1.0,\n",
    "                 lr=1e-4,\n",
    "                 layout='random_mnih2016',\n",
    "                 load_previous_weights=True,\n",
    "                 num_processes=16,              # numero de procesos asincronicos\n",
    "                 num_processes_to_render=4,     # numero de procesos a visualizar\n",
    "                 use_gpu=False,\n",
    "                 max_actions=200,\n",
    "                 num_global_steps=5e6,\n",
    "                 num_local_steps=50,\n",
    "                 save_interval=50,\n",
    "                 saved_path='trained_models',\n",
    "                 log_path='tensorboard')\n",
    "print(\"Agent progress details are displayed on this jupyter notebook TERMINAL (not here)\\n\")\n",
    "train(args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Testing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El siguiente código usa un modelo ya entrenado por 24hs con step size de 1e-6 partiendo de un modelo entrenado por varias horas con step size de 1e-3.\n",
    "\n",
    "Los resultados no fueron los esperados, a pesar de que los últimos 10-15 días fueron usados específicamente para encontrar buenos hiperparámetros, usando dos computadoras con 8 y 6 nucleos cada una.\n",
    "\n",
    "Ésto se debe a una **mala generalización** de mi parte, partiendo de que al usar el mismo modelo para resolver Mario (a mi entender más complejo en todo sentido) se obtuvieron buenos resultados en 24-48 hs, como se ve en el repositorio del modelo usado de base, con resultados visuales bastante convincentes:\n",
    "\n",
    "![super-mario-demo.gif](https://raw.githubusercontent.com/vietnguyen91/Super-mario-bros-A3C-pytorch/master/demo/video_2_3.gif)\n",
    "\n",
    "https://github.com/vietnguyen91/Super-mario-bros-A3C-pytorch\n",
    "\n",
    "Creo que la mayor diferencia está dada por la **lentitud** del simulador de pac-man usado, que **solo permite su simulación en tiempo real**, lo que vuelve a todo el algoritmo **al menos un órden de magnitud más lento**, que para las 24-48 hs de antes, se volverían ahora 10-20 días.\n",
    "\n",
    "De todas maneras, pudo verse como **en las primeras horas** de entrenamiento, el agente mostraba **tendencia** a ir hacia el pellet en el mapa, y quedarse buscando en casilleros contiguos hasta dar con ella.\n",
    "\n",
    "Esta rápida tendencia dió una **intuición demasiado optimista** de que el problema podía ser resuelto en mucho menos tiempo, lo que **no** resultó de esa forma, y a pesar de ver ligeras mejoras (no tan claras), éstas llevaron mucho más tiempo que el esperado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-19T17:42:19.804385Z",
     "start_time": "2019-07-19T17:41:37.355597Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Agent progress details are displayed on this jupyter notebook TERMINAL (not here)\n",
      "\n",
      "Getting number of NN inputs/outputs for layout random_mnih2016-24hs\n",
      "Loading saved model: trained_models/gym-pacman_random_mnih2016-24hs\n",
      "File not found, downloading saved model...\n",
      "Download done.\n",
      "Max episode length reached. Reward: -1105.0\n",
      "Pacman died! Score: -512\n",
      "Pacman died! Score: -510\n",
      "Max episode length reached. Reward: -1220.0\n",
      "Pacman died! Score: -508\n"
     ]
    }
   ],
   "source": [
    "from test_agent import test\n",
    "from argparse import Namespace\n",
    "args = Namespace(layout='random_mnih2016-24hs',\n",
    "                 num_games_to_play=5,\n",
    "                 saved_path='trained_models')\n",
    "test(args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Acerca de la implementación\n",
    "\n",
    "Se siguió el modelo de [Mnih et al.](https://arxiv.org/abs/1602.01783 \"'Asynchronous Methods for Deep Reinforcement Learning' paper\") para la construcción del algoritmo, partiendo de una una [implementación similar ya programada](https://github.com/vietnguyen91/Super-mario-bros-A3C-pytorch \"vietnguyen91 repository\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![actor-critic-model-lstm](./img/actor-critic-model-lstm.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El modelo consta de:\n",
    "\n",
    "* **2 Convolutional layers**\n",
    "  \n",
    "  La primera convoluciona 16 filtros de 8x8 con *stride* 4\n",
    "  \n",
    "  La segund convoluciona 32 filstros de 4x4 con *stride* 2\n",
    "  \n",
    "  Pueden considerarse como features de *pixel space* a *shape/geometric space* \n",
    "\n",
    "\n",
    "* **1 LSTM layer**\n",
    "\n",
    "  Toma como entrada las *high level features* de las capas convolucionales con 2592 (32x9x9) salidas, y aplica un paso de LSTM devolviendo 256 valores\n",
    "  \n",
    "  Representa un **modelo** (*model*) aproximado del environment, que relaciona temporalmente las *features* convolucionadas.\n",
    "  \n",
    "  \n",
    "* **2 Linear layers**\n",
    "\n",
    "  .\n",
    "  \n",
    "  * 1 para el ***Actor*** con 256 entradas y 5 salidas (*número de acciones*) \n",
    "  \n",
    "    Representan el puntaje para cada acción posible\n",
    "  \n",
    "    Los 5 valores **no están acotados**.\n",
    "    \n",
    "    * Para obtener la política se aplica ***Softmax*** sobre ellos.\n",
    "    \n",
    "    * Para calcular la ***entropía*** se utiliza también ***Log-Softmax*** (pues es necesario log_policy)\n",
    "    \n",
    "  .\n",
    "  \n",
    "  * 1 para el ***Critic*** con 256 entradas y 1 sola salida \n",
    "  \n",
    "    Representa ***el valor*** del estado dado (siguiendo la política actual)\n",
    "    \n",
    "    Se utiliza tanto para estimar el valor del **estado actual**, como hacer *bootstraping* y estimar también el valor del **siguiente estado**.\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Modificaciones particulares:\n",
    "\n",
    "#### Input\n",
    "\n",
    "En el paper original se utiliza como input una secuencia de **4 frames *ordenados*** del simulador de Atari (con cierto skipping por su alto frame rate).\n",
    "\n",
    "Cada frame es reducido a escala de grises, y a un tamaño de 84x84 px.\n",
    "\n",
    "![input-to-nn-channel-0](./img/snaps-0.gif)\n",
    "\n",
    "Para este TP se implementó el mismo preprocesamiento de color (*channels*) y *tamaño* (*shape*) de entrada, pero los 4 frames **son el mismo**, rotado 90° 4 veces (sin skipping, pues el frame rate es mucho menor)\n",
    "\n",
    "![input-to-nn-channel-vertical-stack](./img/snaps-vertical.gif)\n",
    "\n",
    "El objetivo fue brindar más información en este aspecto al algoritmo, que en cada paso deberá usar **los mismos filtros** convolucionales para procesar **las 4 rotaciones** del frame.\n",
    "\n",
    "De esta forma se busca generalizar mejor al espacio del juego, y compensar posibles deficiencias del algoritmo en cuanto a **rotaciones**, que suelen ser un punto débil en modelos de *computer vision*.\n",
    "\n",
    "Detalles del código en: [./gym_pacman/src/env.py](./gym_pacman/src/env.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Dropout:\n",
    "\n",
    "Se agregaron capas de dropout entre  capas convolucionales y lineales originales para (de una forma muy general) **evitar *overfitting*** y no depender del tamaño del modelo.\n",
    "\n",
    "Ya que la data obtenida será en función de la política, que depende directamente del modelo, se decidió por usar un *rate* de **dropout aleatorio**, con valores **entre 0 y 0.2** para las **capas convolucionales** y **entre 0 y 0.6** para las **capas lineales**, a partir de una distribución uniforme.\n",
    "\n",
    "Se espera que dropout ayude a **estabilizar la *importancia*** de los pesos, pero que siga siendo posible tener un modelo mayor (dropout reducido) que genere un **comportamiento más apto**, y así, **mejor data** de la cual aprender.\n",
    "\n",
    "Detalles del código en: [./gym_pacman/src/model.py](./gym_pacman/src/model.py)\n",
    "\n",
    "Más sobre dropout en convolutional layers:\n",
    "[Analisys on the Dropout effect in Convolutional Neural Networks](https://github.com/LecJackS/saved_models/blob/master/gym_pacman/resources/Dropout_ACCV2016.pdf)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dive into code\n",
    "\n",
    "Los archivos *train.py* y *process.py* contienen la mayor parte del código correspondiente al algoritmo A3C.\n",
    "\n",
    "En los mismos **fue comentada cada linea de código** a modo puente entre la teoría mencionada anteriormente, y la manera práctica de implementarla.\n",
    "\n",
    "*train.py*: [./gym_pacman/train.py](./gym_pacman/train.py)\n",
    "\n",
    "*/src/process.py*: [./gym_pacman/src/process.py](./gym_pacman/src/process.py)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem to solve\n",
    "\n",
    "La principal limitación del simulador de pacman es que **solo puede ser simulado en tiempo real**.\n",
    "\n",
    "El modelo de A3C es bastante indicado ya que **permite jugar en paralelo varias partidas** al mismo tiempo, mientras que **aprovecha más eficientemente** los datos obtenidos.\n",
    "\n",
    "En cuanto a los niveles a resolver, se experimentó con variantes de distintos mapas de pacman, con distintas características:\n",
    "\n",
    "* Cantidad de pellets\n",
    "* Cantidad de fantasmas\n",
    "* Agresividad de fantasmas\n",
    "* Tamaño del mapa\n",
    "\n",
    "Se decidió por usar un generador de **mapas aleatorios cuadrados**, que modifica el órden del contenido en cada llamada, para menos importancia a la estructura del mapa (y evitar que se memorice) y más a las formas de resolverlo.\n",
    "\n",
    "La **cantidad de fantasmas** es un valor **aleatorio** entre 0 y 1.\n",
    "\n",
    "Similarmente la **agresividad** de cada uno es **aleatoria**.\n",
    "\n",
    "Se probó con tamaños de mapa aleatorios, pero **no se obtuvieron buenos resultados**, distinto a tamaños fijos donde pacman *aprendió* dinámicas de juego rápidamente al dirigirse en dirección a las pellets.\n",
    "\n",
    "La idea de agregar aleatorieidad a las variables fue para tener un **amplio rango de dificultades**, de modo que en un principio sea posible hayar soluciones a \"niveles\" con dificultades bajas, pero **manteniendo el *stream* data de observaciones de dificultades superiores** a modo de evitar overfitting o máximos locales de los cuales sea muy costoso (o imposible) salir.\n",
    "\n",
    "Se puede pensar como ***curriculum***, donde eventualmente el agente encuentre el orden de resolución más adecuado, haciendo uso de lo ya aprendido.\n",
    "\n",
    "Para modificar las diferentes variables de generación de mapas, utilizar: [./layout_params.json](./layout_params.json)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Estrategias de modelado\n",
    "\n",
    "Una de las mayores dificultades en el diseño del algoritmo fue determinar cuándo estaba funcionando, y cuándo no.\n",
    "\n",
    "Los resultados suelen tardar horas en aparecer, y los mismos **no son claros** indicativos de si estamos avanzando, estancados en un máximo local, o simplemente en una pésima política.\n",
    "\n",
    "Para ésto se verificó que:\n",
    "\n",
    "* las **entradas** a la red neuronal sean las correctas observando directamente cada matriz y sus transformaciones\n",
    "\n",
    "  Cada frame y rotación fue directamente exportado y guardado como imagen, que son las que se ven a continuación:\n",
    "  \n",
    "![input-to-nn-channel-combined](./img/snaps-0-1-2-3.gif)\n",
    "\n",
    "\n",
    "* en cada paso los valores estén en rangos *aceptables* a través del tiempo, imprimiendo:\n",
    "  * **Salida** de la red neuronal:\n",
    "    \n",
    "    * Probabilidades del *Actor*\n",
    "    \n",
    "    * Puntaje del estado del *Critic*\n",
    "    \n",
    "  * **Loss** utilizado para actualizar pesos, y sus componentes:\n",
    "  \n",
    "    * Actor loss\n",
    "    \n",
    "    * Critic loss\n",
    "    \n",
    "    * Entropy loss\n",
    "    \n",
    "    Estos últimos con la ayuda de ***tensorboard*** como visualizador en ***plots***.\n",
    "    \n",
    "    Se notó una reducción en los *spikes* a medida que avanzaba la cantidad de episodios.\n",
    "    \n",
    "    Aunque también dió indicios de como estos picos podrían estar contribuyendo a la divergencia del algoritmo, de la misma manera que lo haría un *step size* demasiado grande."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "center"
   },
   "source": [
    "![total-loss-plot.png](./img/total-loss-plot.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El mayor contribuyente de estos picos en el *loss* es la Value Function:\n",
    "  \n",
    "  Mientras que el *loss* del *Actor* está en el rango de los 200-300 máximo, el *loss* del *Critic* está un órden de magnitud por encima con ~5-10k\n",
    "    \n",
    "  Por eso se decidió poner un *tope* en el máximo valor de *loss* para el *Critic*, determinado como $\\frac{1}{step-size}$, y en *total loss* de $\\frac{2}{step-size}$\n",
    "    \n",
    "  Una razón de los picos resultó ser **descuentos temporales acumulados** en episodios demasiado largos (sin fantasma o fantasma casi random).\n",
    "  \n",
    "  Se agregó un límite a la duración máxima posible de un episodio, con un *castigo* de igual valor que si perdiera el juego (-500 puntos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Observaciones\n",
    "\n",
    "1. Entrenar una red convolucional (feature map) a medida que realizamos updates **luego de cada episodio** , desde *ruido*, y utilizando el **reward** ($G_t^{(n)}$) como objetivo parece ser un **enorme desperdicio de recursos**.\n",
    "  \n",
    "  Una primera observación **no puede decirnos mucho del valor, política o transiciones**, pero sí de **siguientes imágenes** que vaya a observar el agente, muy posiblemente con **la misma estructura visual**.\n",
    "  \n",
    "  Si el motivo de la red convolucional es generar una representación geométrica del estado observado, a modo de *facilitar* la estructura de los píxeles (matríces de números) enviados como entrada, por qué se actualizan estos pesos una sola vez por pasada (*step*)?\n",
    "  \n",
    "  Podrían tomarse los primeros 10-100 frames y entrenar las capas convolucionales con **aprendizaje no-supervisado** para generar filtros que generalicen a *visualizaciones* (representación en imágen del estado) similares. \n",
    "  \n",
    "  O si se prioriza mantener el diseño, entrenar las *convolutional layers* con anterioridad de **forma supervisada** con algún dataset con labels, o directamente, usar solo las primeras capas de un **modelo pre-entrenado**.\n",
    "  \n",
    "  Uno de los motivos de ésta decision, posiblemente esté ligada a que los filtros aprendidos por agentes en juegos como Atari, son **muy poco representativos** de las imágenes que observamos en el juego, por lo que no es necesario obtener filtros complejos, ya que alcanzaría con diferenciar un pixel con un brillo particular de los otros.\n",
    "  \n",
    "2. Replay buffer / Memoria. Similarmente a 1., hay poca eficiencia con el uso de datos.\n",
    "  \n",
    "  La capa LSTM da una noción de **estructura de tiempo** al modelo con respecto a los filtros de las convoluciones, pero **no es** el tipo de memoria **a partir de muestras reales**, sino una **estimación aproximada**.\n",
    "  \n",
    "  Usar replay buffer compensaría la falta de información al comienzo del aprendizaje, aumentando la velocidad de convergencia.\n",
    "  \n",
    "  Las razones dadas por los autores del paper de por qué no fue usado replay buffer en A3C son que se buscaba un agente **extrictamente on-policy**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusión\n",
    "\n",
    "El objetivo de este trabajo, como el título da un indicio, fue mostrar una secuencia de algoritmos en el que cada uno solucione ciertas falencias del anterior (para problemas grandes) hasta concluir con algo robusto como A3C, que hace uso tanto de una ***Value Function*** como de una ***Policy Function***.\n",
    "\n",
    "Lejos está de ser una lista extensiva, pero da una idea de qué tanto ha avanzado el área, al mismo tiempo que cuántos interrogantes faltan por resolver.\n",
    "\n",
    "He notado en el proceso de investigación, implementación y pruebas, que varios conceptos ganaron un nuevo protagonismo, mientras otros siguen formando parte como piezas de algo aún mayor.\n",
    "\n",
    "Todavía existe una gran dependencia en cuanto a *calibrar* los componentes iniciales.\n",
    "\n",
    "Por un lado, ésto se da por la **inmensa complejidad** de los problemas a resolver.\n",
    "\n",
    "Pero por otro, queda claro que aún falta **entender** lo que sucede detrás de ellos, y de qué forma pueden ser abordados.\n",
    "\n",
    "La tendencia actual en **Aprendizaje por Refuerzo** busca ser **más general** en cuanto a los problemas a resolver, al mismo tiempo que intenta ser **más eficiente con la data**, haciendo uso de los avances en hardware para obtener un panorama amplio de posibles candidatos, como también de distintas herramientas teóricas que permitan **avanzar en la mejor dirección**.\n",
    "\n",
    "Ideas generales sobre A3C siguien vigentes hoy en día, por su orientación hacia hardware solo con CPU (como son común data centers como tiene a su disposición Google), multiprocesos y estabilidad en cuanto a bias inductivo.\n",
    "\n",
    "Sistemas más actuales como [IMPALA con V-Trace](https://deepmind.com/blog/impala-scalable-distributed-deeprl-dmlab-30/) (off-policy) buscan ir aún más lejos aumentando y dividiendo los distintos procesos **en distintos CPUs**, y **optimizar de manera central con un GPU**, diminuyendo el tiempo de aprendizaje en dos o más ordenes de magnitud, generalizando a problemás más complicados (como laberintos en 3 dimensiones con toma de decisiones en desafíos a completar).\n",
    "\n",
    "Es un buen momento para sumergirse en **Reinforcement Learning**, aprovechando la posibilidad de poder **experimentar en hardware corriente**, conociendo la **dirección actual del research** en el área por los grandes actores, tanto en academia como en el sector privado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Resources\n",
    "\n",
    "Lista de recursos usados para este TP:\n",
    "\n",
    "### Papers and related work:\n",
    "\n",
    "https://github.com/LecJackS/saved_models/tree/master/gym_pacman/resources\n",
    "\n",
    "### Videos:\n",
    "\n",
    "Reinforcement Learning 5: Function Approximation and Deep Reinforcement Learning\n",
    "https://www.youtube.com/watch?v=wAk1lxmiW4c\n",
    "\n",
    "Reinforcement Learning 6: Policy Gradients and Actor Critics\n",
    "https://www.youtube.com/watch?v=bRfUxQs6xIM\n",
    "\n",
    "Reinforcement Learning 7: Planning and Models\n",
    "https://www.youtube.com/watch?v=Xrxrd8nl4YI\n",
    "\n",
    "The rest of the videos are also great:\n",
    "https://www.youtube.com/channel/UCP7jMXSY2xbc3KCAE0MHQ-A/videos\n",
    "\n",
    "### Books\n",
    "\n",
    "\"Reinforcement Learning: An Introduction\"\n",
    "Sutton and Barto 2nd edition\n",
    "http://incompleteideas.net/book/bookdraft2017nov5.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run it $\\downarrow$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T00:33:21.946092Z",
     "start_time": "2019-07-16T00:33:15.869209Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Couldn't change to ./cs188x_pacman folder. Are you already there?\n",
      "Current directory: /home/jack/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/cs188x_pacman\n"
     ]
    },
    {
     "ename": "SystemExit",
     "evalue": "0",
     "output_type": "error",
     "traceback": [
      "An exception has occurred, use %tb to see the full traceback.\n",
      "\u001b[0;31mSystemExit\u001b[0m\u001b[0;31m:\u001b[0m 0\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/jack/anaconda3/envs/pytorch/lib/python3.7/site-packages/IPython/core/interactiveshell.py:3304: UserWarning: To exit: use 'exit', 'quit', or Ctrl-D.\n",
      "  warn(\"To exit: use 'exit', 'quit', or Ctrl-D.\", stacklevel=1)\n"
     ]
    }
   ],
   "source": [
    "# Change dir to run python files in subdirectory ./cs188x_pacman again\n",
    "import os\n",
    "#os.chdir('../')\n",
    "try:\n",
    "    os.chdir(ORIGINAL_DIR)\n",
    "    gym_pacman_dir = './cs188x_pacman'\n",
    "    os.chdir(gym_pacman_dir)\n",
    "    print(\"Original directory:\\n\", ORIGINAL_DIR)\n",
    "    print(\"Moved to:\\n\", os.getcwd())\n",
    "except:\n",
    "    print(\"Couldn't change to ./cs188x_pacman folder. Are you already there?\")\n",
    "    print(\"Current directory:\", os.getcwd())\n",
    "# or use directly\n",
    "#os.chdir('/home/user/TP-Final-Procesos-Markovianos-para-el-Aprendizaje-Automatico-2019-1C/cs188x_pacman')\n",
    "\n",
    "from pacman import  readCommand, runGames\n",
    "prefs = ['--pacman',     'KeyboardAgent',\n",
    "         '--layout',     'originalClassic']\n",
    "args = readCommand(prefs)\n",
    "runGames(**args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Fourth and last week working on this project with only 2 slow and divergent A3C processes because GPU limitations, to realize that if turning of GPU and only use CPU, I can run more than 16 processes at once\n",
    "\n",
    "![monkey](https://media.giphy.com/media/l4FGFT5D4NKA9rGxy/giphy.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "it was fun :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.7.3"
  },
  "toc": {
   "base_numbering": "1",
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "341.967px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}