1_Aprendizaje_Por_Refuerzo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import display, HTML\n",
    "display(HTML(\"<style>.container { width:80% !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.- Aprendizaje por Refuerzo (Reinforcement Learning)\n",
    "\n",
    "\n",
    "* El ***Reinforcement Learning*** (en Español: Aprendizaje por Refuerzo) es un tipo de ***Aprendizaje Automático***, mediante el cual un ***Agente*** (robot, software, etc.) aprende a comportarse en un ***Entorno*** realizando ***Acciones*** y viendo los resultados de esas acciones por medio de ***Recompensas*** positivas o negativas en función de la acción realizada.\n",
    "\n",
    "\n",
    "* El interés por el *Aprendizaje por Refuerzo* esta creciendo en los últimos años debido a los grandes resultados que se están obteniendo con este tipo de aprendizaje automático en áreas como la conducción automática, juegos de estrategia como el Ajedrez o el Go, videojuegos, etc.\n",
    "\n",
    "\n",
    "* En este notebook vamos a ver los siguientes puntos:\n",
    "<span></span><br>\n",
    "    1. [¿Qué es el Aprendizaje por Refuerzo? - Ciclo de Vida](#M1)\n",
    "<span></span><br>\n",
    "    2. [Elementos y Terminología en el Aprendizaje por Refuerzo](#M2)\n",
    "<span></span><br>\n",
    "    3. [Explorar vs Explotar](#M3)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3.1 [Analogía: Aprendizaje por Refuerzo vs \"Vida Real\"](#M31)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3.2 [Exploración](#M32)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3.3 [Explotación](#M33)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3.4 [Cuando Explorar o Explotar](#M34)\n",
    "<span></span><br>\n",
    "    4. [Ecuación de Bellman: Programación dinámica](#M4)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4.1 [Ecuación de Bellman](#M41)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4.2 [Estrategia](#M42)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4.3 [Recompensas parciales](#M43)\n",
    "<span></span><br>\n",
    "    5. [Q-Function: State-Action Value Function](#M5)\n",
    "<span></span><br>\n",
    "    6. [Q-Table](#M6)\n",
    "<span></span><br>\n",
    "    7. [Algoritmos](#M7)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7.1 [Q-Learning](#M71)\n",
    "    <span></span><br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7.2 [SARSA Learning](#M72)\n",
    "\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "## <a name=\"M1\">1.- ¿Qué es el Aprendizaje por Refuerzo? - Ciclo de Vida</a>\n",
    "\n",
    "\n",
    "* El ***Aprendizaje por Refuerzo*** es un tipo de ***Aprendizaje Automático*** mediante el cual un ***Agente*** que ***vive*** en un ***Entorno*** es capaz de percibir un ***Estado***.\n",
    "\n",
    "\n",
    "* El ***Agente*** puede realizar una serie de ***Acciones*** en cada ***Estado*** y estas acciones conllevan diferentes ***Recompensas*** positivas o negativas en función de la acción realizada.\n",
    "\n",
    "\n",
    "* El ***Agente*** tomas las ***Acciones*** basándose en una ***Política*** que tiene ***Aprender*** con el objetivo de ***maximizar las recomensas*** que obtiene por sus acciones.\n",
    "\n",
    "\n",
    "* Por hacer un símil con los aprendizajes supervisado y no supervisado, podemos considerar la ***Política*** como el ***Modelo del Aprendizaje por Refuerzo***.\n",
    "\n",
    "\n",
    "* El proceso del Aprendizaje por Refuerzo sería el siguiente:\n",
    "<span></span><br><br>\n",
    "    1. **<span style=\"font-size:18px\">Acción</span>**: El ***agente*** basandose en su ***estado*** ($S_t$) y su ***política*** toma la decisión de realizar una determinada ***acción***.\n",
    "<span></span><br><br>\n",
    "    2. **<span style=\"font-size:18px\">Recompensa</span>**: Al realizar la ***acción*** el agente ***evalua su estado*** ($S_{t+1}$) y recibe una ***recompensa*** (positiva o negativa)\n",
    "<span></span><br><br>\n",
    "    3. **<span style=\"font-size:18px\">Estado</span>**: Tras realizar la ***acción el estado cambia*** ($S_t = S_{t+1}$).\n",
    "<span></span><br><br>\n",
    "    4. **<span style=\"font-size:18px\">Política</span>**: En función de la ***recompensa*** obtenida el agente ***modifica (o no) su política***.\n",
    "\n",
    "\n",
    "* El ***esquema*** del proceso del ***aprendizaje por refuerzo*** es el siguiente:\n",
    "\n",
    "\n",
    "<img src=\"./imgs/001_RL.png\" style=\"width: 600px;\"/>\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "## <a name=\"M2\"> 2.- Elementos y Terminología en el Aprendizaje por Refuerzo</a>\n",
    "\n",
    "\n",
    "* Dentro del Aprendizaje por refuerzo tenemos los siguientes elementos:\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Agente</span>**: Es un Ente que esta viviendo en un entorno y realiza una serie de acciones para cambiar el estado del entorno.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Entorno</span>**: Sistema que el agente puede percibir e interactual sobre él.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Estados</span>**: Conjunto finito de posiciones del entorno donde puede encontarse el agente.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Acciones</span>**: Conjunto finito de ópciones que tiene el agente para modificar su estado.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Recompensa</span>**: Valor que recibe el agente por la realización de una determinada acción.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Política</span>**: Modelo que sigue el agente para la toma de acciones.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Función de estado</span>**: (Value function) Función que calcula el valor de estar en un determinado estado del entorno. Esta función indica lo bueno o malo que es para el agente estar en un estado.\n",
    "<span></span><br><br>\n",
    "    + **<span style=\"font-size:18px\">Q-Table</span>**: Tabla que guarda para cada estado y cada una de las posibles acciones a realizar en el estado, un valor que nos permite decidir cual de las posibles acciones nos devolverá una mejor recompensa. En otras palabras, en la QTable se guarda la política.\n",
    "\n",
    "|Estado|Acción|Valor|\n",
    "|---|---|---|\n",
    "|(0,0)|Arriba|0,0|\n",
    "|(0,0)|Abajo|0,5|\n",
    "|(0,0)|Izquierda|0,0|\n",
    "|(0,0)|Derecha|0,6|\n",
    "|(0,1)|Arriba|0,0|\n",
    "|(0,1)|Abajo|2,3|\n",
    "|(0,1)|Izquierda|0,1|\n",
    "|(0,1)|Derecha|4,7|\n",
    "|...|...|...|\n",
    "|(n,m)|Arriba|3,6|\n",
    "|(n,m)|Abajo|0,0|\n",
    "|(n,m)|Izquierda|7,2|\n",
    "|(n,m)|Derecha|0,0|\n",
    "\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "\n",
    "## <a name=\"M3\">3.- Explorar vs Explotar</a>\n",
    "\n",
    "\n",
    "### <a name=\"M31\">3.1.- Analogía: Aprendizaje por Refuerzo vs \"Vida Real\"</a>\n",
    "\n",
    "* Supongamos un hipotético caso en el que *tenemos que aprender* de nuevo a *ir desde nuestro trabajo a casa* y no disponemos de mapas ni de GPS para obtener el camino más corto. \n",
    "\n",
    "\n",
    "<img src=\"./imgs/002_RL.png\" style=\"width: 200px;\"/>\n",
    "\n",
    "\n",
    "* Para *resolver por primera vez esta tarea* empezaremos recorriendo una calle y cuando lleguemos a una intersección *tomaremos una decisión sobre que calle coger* para llegar a casa. Como es la primera vez que nos enfrentamos a esta tarea tendremos que ir *tomando decisiones al azar* sobre que calle coger hasta que lleguemos a casa. Este primer día habremos aprendido un camino para llegar a casa aunque este no sea ni de lejos el más corto.\n",
    "\n",
    "\n",
    "<img src=\"./imgs/003_RL.png\" style=\"width: 200px;\"/>\n",
    "\n",
    "\n",
    "* El segundo día que nos enfrentemos a esta tarea ya *tendremos un conocimiento previo de como llegar a casa*, así que podemos *seguir el mismo camino que el día anterior* (camino muy largo) o seguir algunas partes del camino que tomamos el día anterior e investigar otros caminos *tomando decisiones al azar sobre que caminos seguir* para aprender nuevas rutas.\n",
    "\n",
    "\n",
    "<img src=\"./imgs/004_RL.png\" style=\"width: 200px;\"/>\n",
    "\n",
    "\n",
    "* Si hacemos esta tarea muchos dias, al final conseguiremos aprender un camino muy corto (no necesariamente el más corto) para llegar a casa y ya no nos será necesario tomar decisiones al azar sobre que camino seguir.\n",
    "\n",
    "\n",
    "<img src=\"./imgs/005_RL.png\" style=\"width: 200px;\"/>\n",
    "\n",
    "\n",
    "* Esta tarea que acabamos de explicar es un ejemplo de como resolver un problema con aprendizaje por refuerzo en el que un ***Agente=Persona*** realiza una serie de ***Acciones=Decisiones*** en un ***Entorno=Ciudad*** para obtener una ***Recompensa=Llegar a casa***. \n",
    "\n",
    "\n",
    "* Esta ***Recompensa será mayor cuanto menos tiempo se tarde en llegar a casa*** y por tanto hay que ***Aprender*** una ***Politica*** que nos permita determinar que calle coger para llegar a casa lo antes posible.\n",
    "\n",
    "\n",
    "* En esta analogía aparecen dos conceptos muy interesantes dentro del Aprendizaje por Refuerzo como son la ***Exploración*** y la ***Explotación***.\n",
    "\n",
    "\n",
    "### <a name=\"M32\">3.2.- Exploración</a>\n",
    "\n",
    "\n",
    "* La ***Exploración*** es la tarea que consiste en ***visitar y recopilar información de todos los estados*** del entorno. Esto se consigue ***tomando acciones de manera aleatoria*** sin tener en cuenta el conocimiento que se tiene sobre los estados del entorno.\n",
    "\n",
    "\n",
    "* Dada la analogía anterior, el primer día en el que tenemos que ir del trabajo a casa, estaremos *Explorando* las calles de la ciudad ya que no tenemos ningún conocimiento sobre los caminos a tomar para llegar a casa.\n",
    "\n",
    "\n",
    "### <a name=\"M33\">3.3.- Explotación</a>\n",
    "\n",
    "\n",
    "* La ***Explotación*** es la tarea que consiste en ***realizar la mejor acción que se puede tomar dado el conocimiento actual del problema*** (la Política).\n",
    "\n",
    "\n",
    "* Dada la analogía anterior, cuando ya llevemos muchos dias llendo a casa, estaremos *Explotando* el conocimiento que ya tenemos sobre las calles de la ciudad ya que sabremos el camino de regreso a casa de memoria.\n",
    "\n",
    "\n",
    "\n",
    "### <a name=\"M34\"> 3.4.- Cuando Explorar o Explotar</a>\n",
    "\n",
    "\n",
    "* Es evidente que ***la primera vez*** que nos enfrentamos al problema vamos a tener que ***explorar*** ya que el ***conocimiento actual*** que tenemos ***sobre el problema es nulo***.\n",
    "\n",
    "\n",
    "* Según vayamos iterando con el entorno debemos de ir ***disminuyendo nuestra exploración y aumentando la explotación*** del conocimiento adquirido ya que este será cada vez mayor.\n",
    "\n",
    "\n",
    "* La lógica nos puede decir que llegado un determinado momento del problema ya *no será necesario explorar el entorno y dedicarnos solo a explotar el conocimiento* que tenemos y por tanto seguir siempre el mismo camino a casa. \n",
    "\n",
    "\n",
    "* Esta última suposición (que bien pudiera parecer lógica) es erronea ya que en este tipo de problemas ***siempre debemos de explorar aunque sea poco*** ya que es posible que existan caminos más cortos para llegar a casa y que por no explorar de vez en cuando, nunca nos veamos en la situación de poder descubrir un nuevo camino.\n",
    "\n",
    "\n",
    "* Supongamos en el ejemplo visual anterior en el que el primer día tomamos la decisión de ir hacia abajo y como desde el primer día sabemos que tomando la decisión de ir hacia abajo llegamos a casa, solo conseguiremos uno de los mejores camino que se puede obtener (camino rojo) para llegar a casa tomando como primera decisión la de ir hacia abajo. Si nunca exploramos el entorno y nunca tomamos como primera decisión la de ir hacia la derecha, nunca vamos a conseguir uno de los mejores caminos (camino verde) para llegar a casa.\n",
    "\n",
    "\n",
    "<img src=\"./imgs/006_RL.png\" style=\"width: 200px;\"/>\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "\n",
    "## <a name=\"M4\">4.- Ecuación de Bellman: Programación dinámica</a>\n",
    "\n",
    "\n",
    "* La ***ecuación de Bellman*** (Richard Bellman) es conocida como la ecuación de programación dinámica que es una condición necesaria para la optimalidad asociada con el método de la optimización matemática conocida como ***programación dinámica***. \n",
    "\n",
    "\n",
    "* La ***programación dinámica*** viene de las palabras ***programación*** que en matemáticas viene a significar ***optimizar un programa*** (en Aprendizaje por Refuerzo consiste en optimizar una política) y  por otro lado la palabra ***dinámica*** significa que ***el problema tiene un componente secuencial o temporal***. \n",
    "\n",
    "\n",
    "* Haciendo una gran abstracción, definimos la programación dinámica como un método de optimización para problemas secuenciales.\n",
    "\n",
    "\n",
    "* La programación dinámica divide el problema en sub-problemas y los resuelve, uniendo luego estos sub-problemas para encontrar la solución general.\n",
    "\n",
    "\n",
    "* Para usar la programación dinámica deben de cumplirse dos propiedades:\n",
    "<span></span><br><br>\n",
    "    + ***Sub-estructura óptima***: Para que se cumpla esta propiedad debe cumplirse el principio de optimalidad, lo cual significa que el problema se puede resolver si se parte en 2 o más sub-problemas y las soluciones óptimas para esos sub-problemas al unirlos dan como resultado la solución óptima a todo el problema.\n",
    "<span></span><br><br>\n",
    "    + ***Sub-problemas superpuestos***: Para que se cumpla esta propiedad, los sub-problemas deben ser similares, debido a que si se comportan de la misma manera su respuesta termina siendo bastante parecida y por lo tanto la solución se encuentra más rápidamente. Para que se cumpla esta propiedad los sub-problemas se deben repetir.\n",
    "    \n",
    "    \n",
    "### Procesos de Decisión de Markov\n",
    "\n",
    "\n",
    "* En la teoría de la probabilidad y en estadística, un ***proceso de Márkov*** (Andréi Márkov), es un ***fenómeno aleatorio dependiente del tiempo*** para el cual se cumple una propiedad específica: ***la propiedad de Márkov***. \n",
    "\n",
    "\n",
    "* ***La propiedad de Márkov*** dice que ***la probabilidad condicional sobre el estado presente, futuro y pasado del sistema son independientes***; o dicho de otra manera, para ciertos procesos estocásticos (aleatorios) la ***distribución de probabilidad del valor futuro de la variable aleatoria solo depende del valor en el presente, independientemente de todo lo que ha ocurrido en el pasado***; es decir, que carecen de memoria.\n",
    "\n",
    "\n",
    "* Esta propiedad es muy interesante para el Aprendizaje por Refuerzo ya que la acción que tomemos en un estado del problema será independiente a las acciones que hayamos tomado en el pasado.\n",
    "\n",
    "\n",
    "\n",
    "### <a name=\"M41\"> 4.1.- Ecuación de Bellman</a>\n",
    "\n",
    "\n",
    "* La ecuación de Bellman (en una de sus diferentes formas) define el valor de estar en un estado $S_t$ como:\n",
    "\n",
    "\n",
    "$$V(s_t) = \\underset{a}{max} (R(s_t,a) + \\gamma \\cdot V(s_{t+1}))$$\n",
    "\n",
    "\n",
    "* Siendo:\n",
    "    + $R(s_t,a)$: Recompensa por tomar la acción '$a$' desde el estado actual $S_t$.\n",
    "    + $V(s_{t+1})$: Valor del estado al que nos moveríamos ($s_{t+1}$) si tomasemos la acción '$a$'.\n",
    "    + $\\gamma$: Factor de descuento. Se utiliza para penalizar el número de movimientos.\n",
    "    \n",
    "    \n",
    "* Veamos a continuación un ejemplo en el que calcularemos los valores de los estados. Supongamos el siguiente tablero en el que queremos obtener la recompensa máxima que se obtiene en el estado $[4,4]$ con 100 puntos pero también podemos obtener una recompensa negativa de -100 puntos si caemos en el estado $[4,3]$:\n",
    "\n",
    "\n",
    "<img src=\"./imgs/007_RL.png\" style=\"width: 300px;\"/>\n",
    "\n",
    "\n",
    "* Si en un primer momento partimos desde el estado inicial $[1,1]$ donde todos los valores de los estados están sin calcular;es decir que tienen valor $0$, y realizamos una exploración de todos los estados, solo podemos obtener con valor distinto de $0$ la posición $[3,4]$:\n",
    "\n",
    "<img src=\"./imgs/008_RL.png\" style=\"width: 800px;\"/>\n",
    "\n",
    "* En una segunda iteracción ya podemos calcular el valor de dos estados más que tendrán valor distinto de $0$:\n",
    "\n",
    "<img src=\"./imgs/009_RL.png\" style=\"width: 800px;\"/>\n",
    "\n",
    "* Tras varias iteracciones, podemos calcular el valor de todos los estados:\n",
    "\n",
    "<img src=\"./imgs/010_RL.png\" style=\"width: 300px;\"/>\n",
    "\n",
    "\n",
    "\n",
    "### <a name=\"M42\"> 4.2.- Estrategia</a>\n",
    "\n",
    "\n",
    "* Una vez que tenemos calculado el valor de cada uno de los estados, debemos de tomar un conjunto de acciones que nos lleven a obtener la recompensa máxima, siendo esta recompensa de valor igual a 100 en el ejemplo propuesto.\n",
    "\n",
    "\n",
    "* Para ello debemos de seguir un plan de actuación y uno de ellos puede ser el de movernos hacia el estado adyacente que mayor valor de estado ($V(S_t)$) tenga. De esta manera conseguiremos un conjunto de acciones que nos lleven a la recompensa máxima.\n",
    "\n",
    "\n",
    "* Siguiendo el ejemplo anterior, podemos tomar diferentes conjuntos de acciones para obtener la recompensa, siendo algunas de ellas las marcadas en la siguiente imagen: \n",
    "\n",
    "\n",
    "<img src=\"./imgs/011_RL.png\" style=\"width: 300px;\"/>\n",
    "\n",
    "\n",
    "\n",
    "### <a name=\"M43\">4.3.- Recompensas parciales</a>\n",
    "\n",
    "\n",
    "* Como podemos observar en el ejemplo anterior, solo vamos a obtener una recompensa negativa o positiva si caemos en las casillas $[3,4]$ o $[4,4]$ respectivamente.\n",
    "\n",
    "\n",
    "* Por otro lado también podemos intuir que cuantas más acciones realicemos más vamos a tardar en llegar \"a casa\", por lo que parece lógico penalizar de alguna manera el número de paso (o acciones) a realizar ya que cuantos menos pasos demos antes llegaremos a casa.\n",
    "\n",
    "\n",
    "* En el ejemplo anterior siempre vamos a tener la misma recompensa \"al llegar a casa\" (100 puntos) independientemente de que realicemos 6 acciones o infinitas acciones, por tanto parece lógico aplicar algún tipo de penalización por cada acción tomada que no sea la que nos devuelva la recompensa final.\n",
    "\n",
    "\n",
    "* Por tanto a la hora de calcular la recompensa, le restaremos un determinado valor que lo podemos denominar como \"penalización por acción\", quedando la función de valor de estado como:\n",
    "\n",
    "\n",
    "$$V(s_t) = \\underset{a}{max} (R(s_t,a) - Penalty + \\gamma \\cdot V(s_{t+1}))$$\n",
    "\n",
    "\n",
    "* Dado el ejemplo anterior y dando un valor de $-1$ a la penalización tendríamos como primeros valores de estados los siguientes:\n",
    "\n",
    "\n",
    "<img src=\"./imgs/012_RL.png\" style=\"width: 800px;\"/>\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "## <a name=\"M5\"> 5.- Q-Function: State-Action Value Function</a>\n",
    "\n",
    "\n",
    "* La ***Q-Function*** es una función que indica al agente cuanto de bueno o de malo es tomar una determinada acción en un estado concreto usando una política $\\pi$.\n",
    "\n",
    "\n",
    "* En un primer momento vamos a definir la Q-Function como:\n",
    "\n",
    "\n",
    "$$Q^{\\pi}(s_t, a) = R(s_t,a) + \\gamma \\cdot \\underset{a}{max} Q(s_{t+1},{a}')$$\n",
    "\n",
    "* Siendo:\n",
    "    + $R(s_t,a)$: Recompensa por tomar la acción '$a$' desde el estado actual $s_t$.\n",
    "    + $Q(s_{t+1},{a}')$: Valor de la función Q en el estados $s_{t+1}$ tomando la acción ${a}'$.\n",
    "    + $\\gamma$: Factor de descuento. Se utiliza para penalizar el número de acciones tomadas.\n",
    "    \n",
    "    \n",
    "* Definimos $Q(s, a)$ como la recompensa por tomar la acción $a$ en el estado $s$ más el valor máximo que puede tomar $Q$ en el nuevo estado tras tomar una de las posibles acciones ${a}'$, multiplicado por un factor de descuento.\n",
    "\n",
    "\n",
    "* Como podemo observar $Q(s, a)$ antes de tomar la acción tendrá un valor $X$ y tras aplicar la acción, tendrá otro valor ${X}'$ con lo cual tenemos una diferencia del valor de $Q(s, a)$ denominada como \"***Diferencia Temporal***\" que viene dada por:\n",
    "\n",
    "\n",
    "$$TD(a,s) = (R(s_t,a) + \\gamma \\cdot \\underset{a}{max} Q(s_{t+1},{a}')) - Q(s_t, a)$$\n",
    "\n",
    "\n",
    "* Vemos entonces que $TD(a,s)$ es el valor de $Q(s, a)$ de \"***después de tomar la acción***\" menos el valor de $Q(s, a)$ de \"***antes de tomar la acción***\"; por tanto al ir tomando acciones, los valores de $Q(s, a)$ se van modificando y cuantas más acciones realicemos más información vamos adquiriendo del entorno; es decir, que ***cuantas más acciones realicemos más aprendemos***. Según esta afirmación podemos intuir que si la diferencia temporal tiene valor $0$ es que no hemos aprendido nada al aplicar esa acción.\n",
    "\n",
    "\n",
    "* Como lo que nos interesa es ir aprendiendo lo buenas o malas que son las acciones que el agente puede tomar en los diferentes estados del entorno, tenemos que ir modificando poco a poco los valores de $Q(s, a)$; por lo que tenemos que combinar el valor actual de $Q(s, a)$ con un nuevo valor de $Q(s, a)$ tras la realización de una nueva acción.\n",
    "\n",
    "\n",
    "* Para ello modificaremos el valor de $Q(s, a)$ de la siguiente manera:\n",
    "\n",
    "$$\\widehat{Q}(s, a) = Q(s, a) + \\alpha \\cdot TD(a,s)$$\n",
    "\n",
    "\n",
    "* Siendo:\n",
    "    + $\\widehat{Q}(s, a)$:El nuevo valor de $Q(s, a)$\n",
    "    + $Q(s, a)$: El antiguo valor de $Q(s, a)$\n",
    "    + $TD(a,s)$: La diferencia temporal: $Q(s, a)_{\"despues\"}-Q(s, a)_{\"antes\"}$\n",
    "    + $\\alpha$: Factor de aprendizaje (Learning Rate) que indica \"*cuanto*\" queremos aprender en cada acción.\n",
    "\n",
    "\n",
    "* De esta manera en cada acción no sustituimos o \"machacamos\" el valor de $Q(s, a)$, si no que lo vamos modificando poco a poco según vayamos iterando en nuestro problema.\n",
    "\n",
    "\n",
    "* Con todo esto podemos concluir que la \"***Q-Function***\" quedaría definida de la siguiente manera:\n",
    "\n",
    "<span style=\"font-size:20px\">\n",
    "$$\\widehat{Q}(s, a) = Q(s, a) + \\alpha \\cdot \\left [ R(s,a) + \\left (\\gamma \\cdot \\underset{{a}'}{max} Q({s}',{a}') \\right ) - Q(s,a) \\right ]$$\n",
    "</span>\n",
    "\n",
    "\n",
    "* Siendo:\n",
    "    + $\\widehat{Q}(s, a)$:El nuevo valor de $Q(s, a)$\n",
    "    + $Q(s, a)$: El antiguo valor de $Q(s, a)$ o valor actual.\n",
    "    + $\\alpha$: Factor de aprendizaje (Learning Rate) que indica \"*cuanto*\" queremos aprender en cada acción.\n",
    "    + $R(s,a)$: Recompensa por tomar la acción '$a$' desde el estado actual $s$.\n",
    "    + $\\gamma$: Factor de descuento.\n",
    "    + $\\underset{{a}'}{max} Q({s}',{a}')$: Valor de $Q(s, a)$ tras tomar la mejor acción posible.\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "## <a name=\"M6\">6.- Q-Table</a>\n",
    "\n",
    "\n",
    "* Como ya definimos anteriormente, una ***Q-Table es una tabla*** que guarda ***para cada estado y para cada una de las posibles acciones*** a realizar en el estado, ***un valor que nos permite decidir cual de las posibles acciones nos devolverá (a corto o largo plazo) una mejor recompensa***.\n",
    "\n",
    "\n",
    "* En un primer momento en el que no sabemos nada del entorno, la Q-Table estará inicializada con algún valor por defecto (por ejemplo a cero) e iremos rellenando los valores de la Q-Table según vayamos explorando el entorno.\n",
    "\n",
    "\n",
    "* La Q-Table puede tener la siguiente forma, Guardando un determinado valor para cada estado del entorno y para cada una de las acciones que se pueden tomar en el estado:\n",
    "\n",
    "\n",
    "|Estado|Acción1|Acción2|Acción3|Acción4|\n",
    "|---|---|---|---|---|\n",
    "|(0,0)|0,0|0,5|0,0|0,6|\n",
    "|(0,1)|0,0|2,3|0,1|4,7|\n",
    "|(1,0)|0,1|6,4|0,0|8,9|\n",
    "|...|...|...|...|...|\n",
    "|(n,m)|3,6|0,0|7,2|0,0|\n",
    "\n",
    "\n",
    "* Esta ***Q-Table*** la vamos calculando con la ***Q-Funtion*** según va interactuando el agente con el problema.\n",
    "\n",
    "$$\\widehat{Q}(s, a) = Q(s, a) + \\alpha \\cdot \\left [ R(s,a) + \\left (\\gamma \\cdot \\underset{{a}'}{max} Q({s}',{a}') \\right ) - Q(s,a) \\right ]$$\n",
    "\n",
    "\n",
    "* Haciendo un símil con otro tipo de aprendizajes, la ***Q-Table es el modelo*** del Aprendizaje por Refuerzo ya que los valores que hay en esta tabla se tienen que ir calculando según el agente va interactuando con el problema y por otro lado es utilizada para la toma de acciones con la *Q-Funtion*.\n",
    "\n",
    "\n",
    "* La *Q-Table* no solo se guarda en formato tabular si no que dependiendo del problema puede ser guardada en otras estructuras como por ejemplo en una Red Neuronal.\n",
    "\n",
    "\n",
    "\n",
    "<hr>\n",
    "\n",
    "\n",
    "\n",
    "## <a name=\"M7\">7.- Algoritmos</a>\n",
    "\n",
    "\n",
    "* Existen diferentes algoritmos a utilizar en el Aprendizaje por Refuerzo siendo algunos de estos los siguientes:\n",
    "\n",
    "    + Q-Learning\n",
    "    + SARSA-Learning\n",
    "    + Deep Q Learning\n",
    "    + Asynchronous Advantage Actor-Critic Algorithm (A3C)\n",
    "    + Monte Carlo\n",
    "    + Etc.\n",
    "    \n",
    "    \n",
    "* Dado el número de algoritmo existente, vamos a explicar 2 de los algoritmo más populares y sencillos de entender en el Aprendizaje por refuerzo como son el \"*Q-Learning*\" y el \"*SARSA-Learning*\"\n",
    "\n",
    "\n",
    "\n",
    "### <a name=\"M71\">7.1.- Q-Learning</a>\n",
    "\n",
    "\n",
    "* Q-learning es una técnica de aprendizaje por refuerzo que tiene como objetivo aprender una estrategia que le diga a un agente qué acción tomar bajo qué circunstancias. \n",
    "\n",
    "\n",
    "* Para ello utiliza la ***Q-Function*** definida como: \n",
    "\n",
    "\n",
    "<span style=\"font-size:20px\">\n",
    "$$\\widehat{Q}(s, a) = Q(s, a) + \\alpha \\cdot \\left [ R(s,a) + \\left (\\gamma \\cdot \\underset{{a}'}{max} Q({s}',{a}') \\right ) - Q(s,a) \\right ]$$\n",
    "</span>\n",
    "\n",
    "\n",
    "* Siendo:\n",
    "    + $\\widehat{Q}(s, a)$:El nuevo valor de $Q(s, a)$\n",
    "    + $Q(s, a)$: El antiguo valor de $Q(s, a)$ o valor actual.\n",
    "    + $\\alpha$: Factor de aprendizaje (Learning Rate) que indica \"*cuanto*\" queremos aprender en cada acción.\n",
    "    + $R(s,a)$: Recompensa por tomar la acción '$a$' desde el estado actual $s$.\n",
    "    + $\\gamma$: Factor de descuento.\n",
    "    + $\\underset{{a}'}{max} Q({s}',{a}')$: Valor de $Q(s, a)$ tras tomar la mejor acción posible.\n",
    "    \n",
    "    \n",
    "* Cabe destacar que este algoritmo puede aprender la estrategia optimizando la recompensa a corto o largo plazo; es decir, que puede aprender a moverse al siguiente estado con mayor recompensar (estrategia a corto plazo) o puede moverse de tal manera que tenga en cuenta maximizar la recompensa final (estrategia a largo plazo) aunque esto le suponga no realizar el movimiento más prometedor dado un estado.\n",
    "\n",
    "\n",
    "* Para definir que tipo de estrategia tomar, usamos el hiperparámetro $\\gamma$ (factor de descuento) que tendrá que tener un valor de $0$ o cercano a $0$ si queremos tomar una estrategia a corto plazo y un valor de $1$ o cercano a $1$ si decidimos tomar una estrategia a largo plazo.\n",
    "\n",
    "\n",
    "* El Pseudocódigo de este algoritmo es el siguiente:\n",
    "\n",
    "\n",
    "<img src=\"./imgs/013_qlearning.png\" style=\"width: 500px;\"/>\n",
    "\n",
    "\n",
    "* En este algoritmo podemos observar los siguiente:\n",
    "    1. El agente se ejecutara un número determinado de veces (episodios)\n",
    "    2. Cada vez que se ejecute, el agente partirá del estado inicial $S$ por lo que hay que inicializar el entorno\n",
    "    3. Para cada ejecución, el agente calculará los valores de las acciones que puede tomar en cada uno de los estados con la Q-Function y actualizará el valor $Q(s,a)$ en la Q-Table.\n",
    "    4. El agente en cada estado puede realizar las acciones de dos formar:\n",
    "        + Explorando: Selecciona una acción al azar\n",
    "        + Explotando: Selecciona la mejor acción entre todas las posibles\n",
    "    5. El algoritmo se ejecuta hasta que el agente llegue al estado final.\n",
    "    \n",
    "    \n",
    "* Para determinar si el agente tiene que explorar o explotar en un determinado estado se define un parámetro conocido como \"greedy control\" ($\\in$) que no es más que la definición de una probabilidad de explotación o exploración; por ejemplo, si definimos $\\in=0.1$, un 10% de las veces exploraremos y un 90% de las veces explotaremos el conocimiento adquirido por el sistema.\n",
    "\n",
    "\n",
    "\n",
    "## <a name=\"M72\"> 7.2.- SARSA Learning</a>\n",
    "\n",
    "\n",
    "* El SARSA-learning (State–action–reward–state–action) es una técnica de aprendizaje por refuerzo similar al Q-learning, con la diferencia de que en la Q-función no selecciona el valor máximo esperado $\\underset{{a}'}{max} Q({s}',{a}')$, si no que selecciona la acción que hubiesemos tomado en ese nuevo estado ${s}'$.\n",
    "\n",
    "\n",
    "* Veamos como queda la función de Estado-Acción: \n",
    "\n",
    "\n",
    "<span style=\"font-size:20px\">\n",
    "$$\\widehat{Q}(s, a) = Q(s, a) + \\alpha \\cdot \\left [ R(s,a) + \\left (\\gamma \\cdot Q({s}',{a}') \\right ) - Q(s,a) \\right ]$$\n",
    "</span>\n",
    "\n",
    "\n",
    "* Siendo:\n",
    "    + $\\widehat{Q}(s, a)$:El nuevo valor de $Q(s, a)$\n",
    "    + $Q(s, a)$: El antiguo valor de $Q(s, a)$ o valor actual.\n",
    "    + $\\alpha$: Factor de aprendizaje (Learning Rate) que indica \"*cuanto*\" queremos aprender en cada acción.\n",
    "    + $R(s,a)$: Recompensa por tomar la acción '$a$' desde el estado actual $s$.\n",
    "    + $\\gamma$: Factor de descuento.\n",
    "    + $Q({s}',{a}')$: Valor de la mejor acción que hubiesemos tomado en el nuevo estado ${a}'$\n",
    "    \n",
    "    \n",
    "* El Pseudocódigo de este algoritmo es el siguiente:\n",
    "\n",
    "\n",
    "<img src=\"./imgs/014_sarsa.png\" style=\"width: 500px;\"/>\n",
    "\n",
    "\n",
    "* Como se puede observar en el Pseudocódigo la diferencia fundamental frente al Q-Learning es que se selecciona la mejor acción a tomar en el estado actual (igual que en Q-Learning) pero en la función se toma como valor $Q({s}',{a}')$ el valor de la acción que se tomaría en el estado en el que nos moveríamos a continuación; es decir, como si viesemos el valor que tendríamos si tomasemos dos acciones.\n",
    "\n",
    "\n",
    "* Esta diferencia hace que el SARSA-Learning obtenga por lo general mejores resultados que el Q-Learning.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "\n",
    "\n",
    "# Referencias\n",
    "\n",
    "* ***Reinforcement Learning: An Introduction*** de Richard S. Sutton y Andrew G. Barto<br>https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf\n",
    "\n",
    "\n",
    "* ***Introducción al aprendizaje por refuerzo profundo: Teoría y práctica en Python*** de Jordi Torres.\n",
    "\n",
    "\n",
    "* ***Hands-On Reinforcement Learning with Python*** de Sudharsan Ravichandiran.\n",
    "\n",
    "\n",
    "* ***Deep Reinforcement Learning Hands-On*** de Maxim Lapan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "\n",
    "*Este Notebook ha sido desarrollado por **Ricardo Moya García** y registrado en Safe Creative como ***Atribución-NoComercial-CompartirIgual***.*\n",
    "\n",
    "\n",
    "<a href=\"https://www.safecreative.org/work/2005103928037\" xmlns:cc=\"http://creativecommons.org/ns#\" rel=\"cc:license\"><img src=\"https://resources.safecreative.org/work/2005103928037/label/standard-72\" style=\"border:0;\" alt=\"Safe Creative #2005103928037\"/></a>"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}