{"cells":[{"cell_type":"markdown","metadata":{"id":"pyOKzVGWZgja"},"source":["Como se vio en clase, la idea detrás del aprendizaje por refuerzo es tan simple como atractiva:\n","aprender del ensayo y el error mediante la interacción con el entorno.\n","\n","Cada vez que el agente, o el entrenador, realiza una acción en el entorno se proporciona una recompensa o una penalización.\n","\n","La tarea del agente es aprender indirectamente, a partir de los refuerzos, a elegir la secuencia de acciones que producen mayor acumulación de refuerzo.\n","\n","\n","El objetivo principal de este notebook es demostrar, en un entorno simplificado, cómo se pueden utilizar las técnicas de aprendizaje por refuerzo para abordar un problema.\n","\n","#### Vamos a utilizar el problema del taxi autonomo introducido por [Dietterich2000].\n","\n","El problema conciste en recoger a un pasajero en un lugar y dejarlo en otro, ocupandose de lo siguiente:\n"," * Dejar al pasajero en la ubicación correcta.\n"," * Tomar el mínimo tiempo posible para dejar al pasajero.\n"," * Cuidar las normas de seguridad y tráfico.\n","\n","![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGkAAAB5CAYAAAA6VA+hAAAABHNCSVQICAgIfAhkiAAAABl0RVh0U29mdHdhcmUAZ25vbWUtc2NyZWVuc2hvdO8Dvz4AAAAmdEVYdENyZWF0aW9uIFRpbWUAbWFyIDI5IG5vdiAyMDIyIDEzOjE5OjE2r8TNtwAACnFJREFUeJztnW1wVNUZx393d0M2CRuSLAmJJAKGUUo0iFIaIjoacAqxaJWqdbAy4tCOUqHTgRkJjBOTqkiLUq3UtOVDraEdrW9ERbTOBOVFKlKgVYJBAZNNNtkku0uSzWaz2dsPG+hCk2zYvbubszm/T/ty9jln7/+e55zzPPfcqxQVFalIRjW6WDdAEhwpkgBIkQRAiiQAUiQBCCqSPnMmxbMmY1Si0Zz4R0mcTGFxAVn6kf8mqEgJ+SUsKy3AJEXSBCV1JqXLSshPHPlvpLsTACmSACj/H3FQMM1fzeblV2MYeK8oKupAqf6GnVRW1mBRQTHdyJrND1BgAPDRuLOSippGzhtUsindUM6dU/wO2FtXzfpna3EE1Gi49iG2rioiEUB1ULvlMapP9Ac0J3wbQduJnun3Psm6hWb/Wdt3iJdWV/G5F01sKNmLKSu/i6kD45CiKKjnDqj3OK+sf449jqEDP4OIBEqSmZwMIwqQWHgfa+eeYdv2/dhVwOOkxdaFF0BJJn1SKufcq7e7jbbOgH+GgRTzREwJA289Tlo7evAF1pWYRla6vy7ox9Vh46wHbW0EbSckmDIxp5wbzd04Why4VY1sGExkTkplHKCkzWPFqmkc2rKDo25A7cVubcPlY0gMg32o9rTTZPG/Nua5UT1OWpos2C42pLqwW11DW8dLd7uV7mFKqL0OWqzDFNDCRtB2Ql+nDWtnhGx4O7FZ/F/oPE48qht7swXL8ObOI8ckARjU3UlGF7InCYAUSQCkSAIgRRIAKZIASJEEIIhICsnFq9m2YTHZMY2CG5i1YitP3Z3PJUT4RyVK1iLKtq3hhpSRH9BBIw7B0THlh+VsXDIZHSo+Xx+u9ga+3Ps2r773BfZhQhzxiwGz41ZubyxipisNxWDjdHotNXn7OGMIbykaokh+fLY9VL3wARaMZFxxE0t/vIqH+yt5elczY2uFrGDquI81J2fQmvMmVVc00eudyFTHleR6lNiKhLebtmYrzT5otlgZP6uYFVd/h7TdzQG9yUDSBBNGXw/OTjcx62Q6I6YJSeh6O3G6vMHLX4oN9XJKGuagm/gHtud9QQ8ATTSkHtOg4VpNHBQD4/O+x3VT9fh6PXgDTxx9Pndu3Mwzv1jApBiOa0rOrfzymc2U3T4t5HFtKBuKewYz3G7qMk4MCKQtYfUkXfYiNlQtAhQUnYLqOs37uz+na2z5OvSeDNJwcGycP4elP3sPTxy/iTT6seVs5VeXn6I/iI3hCG9MatvL9hf/QbPxMuYu+T7pB6p480TPheNR/wl2rFvJjnAq0gDVUsMTP62Jig3f+N08f80x5n39MLM1OGHDc3feLlotFhrqP+PNP+8j9UcPsiC2c/WY0D/OjoMJZHj8TlDVOWlNbsGp18alaLaY9bXvZ/exTBbffv1FVxYZSEk3Y05Lju0aR59MmtlMekoYzmMIG6rxOHXGJK6y53MJFwGNGA0jDr3U1e6ja/YPuCU3QA59PneUbeLpR28hK5YTh+wFrHl6E48tCWPiMJQNpYHa3CPobPfzoGU2V7iyyXVex5Vubf6wpmGh/oa97Pkmi5LbrmP8mPJ6Ppzmv/Db6Qfxdizlkf+UsbZ+PskT3qb6stNhTRog5ImDjzNvPc7P3rr44zY++vUjfBT42ZiZOHixZbzDnzLeCauOwZABVgGQIgmAPjc3tzxYIZ+zkfpvO/AEKxgx/FPZbutJTtncQscFFVTo6+DMV42cHWGMTF4tJADhBVglABw4UDjs9/PmhRdolWOSAMjMbJQJJTMre5IASJEEIAoiGUiakE66yRjbM0JnxJSezoTkMOZKWtgIpdqI1zAGMrORRro7AYh8vx0zAdbIIXuSAERl4hDvmdlIE5WJQ9xnZiOMdHcCICcOUbYRCrInCYAUSQCCuDuVvoaDvPtxO13Rac8Q9GP91/t85OkQOisLQHc9n7xr51vPyP+JzMwKgHR3AiBI0i9+kEm/OEWKJACCJP00sCGTfsOgRdJPAxsy6SeJKEHWSQrJxY/ym1vqqXhqF1a5ogobJWsR68uvYs+659nXPbIDKnuSAAiS9NPAhkz6DYMWST8NbMiknySiyIlDlJEThzhFiiQAgmzHjB/kdsw4Rbo7AZAiCUAUMrOjZCulPp+7n9zKQ4Wx3cstM7NxihRJAAQRKY62dIZSbVRrC5U42tIZCmKINMYR47Y1cbQzIxRkTxIAQUSKoy2dISCGSHG0pTMUxBBpjCMnDpeAnDhIhkSKJABRyMyOkpvcKqDQS+vpeqwx3FsqM7NxinR3AiCTflEmak/H1GWv5IblDzLetZvDf6ygxa0C40greZl5c/NwH1vL3vcO0BeK8Wijm8rSig2U5ugAFZ/XzVlrPZ+99ypvHGweFVdIheTufC2vUV/ngJQFTJ89FQVg/ELyZ+WB9win9h8UQ6Dz+GitfZHHN2zk8crnqD6sp2jFz1kybXTcOzm0MUl10LL/b5ztN5A65ydkGceRNud+shKh5+h2Gh1aPwMz8km/vs52mq1Wmhu/5vCuT/jKN5EpeSlc4JRES/qpbW9Q/2UbpCwgf/4Kpl87BTyfcvLTI4T4gNChiWbSTzGSPWc203Q2zjR0X7BkiFXSL/RTQu2idX819hlryPjuclC9dH26naZOER/XrCPntjJ+vxjQ6dB72zn81xfYeSrcx1NpQ3j91r6T+n/fw9zrL4Oej6n/5/HIPOw34rE7H20fV/G7D5vwGVKYNHMhdy9dyR1Nm/j7V+7zpQSN3fVg/+YoXhXU5gO094i7Lg4ck4588DI1J7K4ecE1JMW6YQizmI120s+H16uSkJRMQuAYKJN+wxCFpF+CyUxOdjY5udMouOlebivU0VBXT2eAc4hV0k+MfFLE0ZF18yoqblbx+Tx0tzVyfNc2XtvdNCrurxe2SL6TFXy4qUKLtgxNJCcOvtO8vnElr4+gqKATB0k0kCIJgEz6Rb0ZMukXl0h3JwBSJAGQIglAUJH0mTMpnjUZo7ybsSYoiZMpLC4g6xJCFkFFSsgvYVlpASYpkiYoqTMpXVZCfuLIfyPdnQBIkQRgkHWSgmn+ajYvv3ogsKegKCrqQKn+hp1UVtZgUUEx3ciazQ9QYADw0bizkoqaxv8tWJVsSjeUc+cUvwP21lWz/tlaHAE1Gq59iK2rikgEUB3UbnmM6hMBGVENbARtJ3qm3/sk6xaa/Wdt3yFeWl3F5wHXAYRjQ8leTFn5XUwdGIcURUE9d0C9x3ll/XPscQy9XB10MaskmcnJMKIAiYX3sXbuGbZt349dBTxOWmxd/usYlGTSJ6Vyzr16u9to6wy8wsFAinkipoSBtx4nrR09F2RvlcQ0stKNAxd89OPqsHH2gtCGBjaCthMSTJmYU86N5m4cLQ7cqkY2DCYyJ6UyDlDS5rFi1TQObdnBUTeg9mK3tuEaJvowaBRc7WmnyeJ/bcxzo3qctDRZsF1sSHVht7qGto6X7nYr3cOUUHsdtFiHKaCFjaDthL5OG9bOCNnwdmKz+L/QeZx4VDf2ZguW4c2dR45JAiBjdwIge5IASJEE4L8Xde2YjjAtUAAAAABJRU5ErkJggg==)\n","\n","La figura muestra un entorno representado por una cuadrícula de 5 X 5, donde se encuentra el taxi (t). Hay cuatro espacios especialmente ubicados, marcados como R, B, G, Y. En cada episodio, el taxi comienza en un lugar elegido al azar. Hay un pasajero en uno de los cuatro lugares (elegido al azar), y ese pasajero desea ser transportado a una de las cuatro ubicaciones (también elegida al azar). \n","El taxi debe ir a la ubicación del pasajero, recojerlo, ir a la ubicación de destino, y dejar al pasajero allí. \n","El episodio finaliza cuando el pasajero es dejado en la ubicación de destino.\n","\n","Hay seis **acciones** que puede tomar el agente en un estado dado:\n","    - (a) cuatro acciones de navegación que mueven el taxi: norte, sur, este u oeste\n","    - (b) dos acciones con los pasajeros: recogida y arribo\n","\n","\n","El agente recibe 20 puntos por una entrega exitosa y pierde 1 punto por cada paso a seguir. También hay una penalización de 10 puntos por acciones ilegales de recogida y arribo. \n","\n","\n","\n","\n","\n","[Dietterich2000]\tT Erez, Y Tassa, E Todorov, \"Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition\", 2011.\n"]},{"cell_type":"markdown","metadata":{"id":"ousFORKDZgjX"},"source":["# Aprendizaje por refuerzo "]},{"cell_type":"markdown","metadata":{"id":"O69pCsGWZgje"},"source":["### Implementación:\n","\n","Utilizaremos la biblioteca OpenAI Gym, la cuál ofrece diferentes entornos para probar un agente. La biblioteca se encarga de la API para proporcionar toda la información que requeriría el agente, como posibles acciones, recompenzas y estado actual. De esta forma solo necesitamos enfocarnos en la parte del algoritmo para el agente.\n","\n","Primero instalamos gym, ejecutando la siguiente celda:"]},{"cell_type":"code","execution_count":48,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":7252,"status":"ok","timestamp":1685719015744,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"Ug7DXOPeZgjg","outputId":"83655f5f-c181-48ef-f4b0-e735865fc384"},"outputs":[{"output_type":"stream","name":"stdout","text":["Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n","Requirement already satisfied: cmake in /usr/local/lib/python3.10/dist-packages (3.25.2)\n","Requirement already satisfied: gymnasium in /usr/local/lib/python3.10/dist-packages (0.28.1)\n","Requirement already satisfied: scipy in /usr/local/lib/python3.10/dist-packages (1.10.1)\n","Requirement already satisfied: numpy>=1.21.0 in /usr/local/lib/python3.10/dist-packages (from gymnasium) (1.22.4)\n","Requirement already satisfied: jax-jumpy>=1.0.0 in /usr/local/lib/python3.10/dist-packages (from gymnasium) (1.0.0)\n","Requirement already satisfied: cloudpickle>=1.2.0 in /usr/local/lib/python3.10/dist-packages (from gymnasium) (2.2.1)\n","Requirement already satisfied: typing-extensions>=4.3.0 in /usr/local/lib/python3.10/dist-packages (from gymnasium) (4.5.0)\n","Requirement already satisfied: farama-notifications>=0.0.1 in /usr/local/lib/python3.10/dist-packages (from gymnasium) (0.0.4)\n"]}],"source":["!pip3 install cmake gymnasium scipy"]},{"cell_type":"code","execution_count":49,"metadata":{"executionInfo":{"elapsed":35,"status":"ok","timestamp":1685719015745,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"_bnXy_V818yh"},"outputs":[],"source":["# Una funcion de ayuda para imprimir el estado de nuestro mundo\n","def print_env(env):\n","  env_str = env.render()\n","  print(env_str)"]},{"cell_type":"markdown","metadata":{"id":"GoqwyoXpZgji"},"source":["Una vez instalado, podemos cargar el entorno y mostrarlo:"]},{"cell_type":"code","execution_count":50,"metadata":{"executionInfo":{"elapsed":31,"status":"ok","timestamp":1685719015745,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"NjAhSdw8Zgji","colab":{"base_uri":"https://localhost:8080/"},"outputId":"c3559ed9-da9f-49be-8007-0ef8b4505633"},"outputs":[{"output_type":"stream","name":"stdout","text":["+---------+\n","|\u001b[35mR\u001b[0m: | : :G|\n","| : | : : |\n","| : :\u001b[43m \u001b[0m: : |\n","| | : | : |\n","|Y| : |\u001b[34;1mB\u001b[0m: |\n","+---------+\n","\n","\n"]}],"source":["from IPython.display import clear_output\n","from time import sleep\n","import numpy as np\n","import gymnasium as gym\n","\n","seed = 1\n","\n","env = gym.make(\"Taxi-v3\", render_mode='ansi').env\n","env.reset(seed = seed)\n","\n","print_env(env)"]},{"cell_type":"markdown","metadata":{"id":"soZwpEusZgjj"},"source":["La interfaz principal de la biblioteca Gym es *env*. \n","Los siguientes son métodos útiles de *env*:\n","   * env.reset - Restablece el entorno y devuelve un estado inicial aleatorio.\n","   * env.step(acción) - Avanza el entorno por un paso de tiempo y retorna:\n","         - observation: observaciones del entorno\n","         - reward: si la acción fue beneficiosa o no\n","         - terminated: indica si recogió y dejó con éxito a un pasajero, también llamado 'episode'\n","         - truncated: si termino la ejecución por otros motivos (p.e. se ejecutaron más pasos que el límite) - no usado en este ejemplo\n","         - info: información adicional como el rendimiento y la latencia para fines de depuración - no usado en este ejemplo\n","   * env.render -  Renderiza una imagen del entorno, es útil para visualizar el entorno\n","\n","\n","Introduciendose más en el ambiente:"]},{"cell_type":"code","execution_count":51,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":23,"status":"ok","timestamp":1685719015745,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"zIP8B8qMZgjk","outputId":"d7b2773c-15d6-45c6-fb04-5428ed23e203"},"outputs":[{"output_type":"stream","name":"stdout","text":["+---------+\n","|\u001b[35mR\u001b[0m: | : :G|\n","| : | : : |\n","| : :\u001b[43m \u001b[0m: : |\n","| | : | : |\n","|Y| : |\u001b[34;1mB\u001b[0m: |\n","+---------+\n","\n","\n","Action Space Discrete(6)\n","State Space Discrete(500)\n"]}],"source":["env.reset(seed=seed) # restablece el entorno y devuelve un estado inicial aleatorio\n","print_env(env) # renderiza un cuadro\n","\n","print(\"Action Space {}\".format(env.action_space))\n","print(\"State Space {}\".format(env.observation_space))\n"]},{"cell_type":"markdown","metadata":{"id":"dZKmjdjSZgjl"},"source":["Según lo verificado por las \n","\n","*   List item\n","*   List item\n","\n","impresiones, tenemos un espacio de acción de tamaño 6 y un espacio de estado de tamaño 500: \n","\n","25 plazas, 5 ubicación para el pasajero (contando las cuatro estaciones y el taxi) y los 4 destinos -> 25 x 5 x 4 = 500.\n","\n","* El rectángulo de color representa el taxi,  amarillo es cuando va sin pasajero y verde con un pasajero.  \n","* '|' representa una pared que el taxi no puede cruzar.\n","* R, G, Y, B son las posibles ubicaciones de recogida y destino. La letra azul representa la ubicación actual de recogida de pasajeros, y la letra púrpura es el destino actual.\n","\n","\n","Se necesita  una forma de identificar un estado de manera única, esto se realiza mediante la asignación de un número único a cada estado posible, y el aprendizaje por refuerzos aprenderá a elegir un número de acción de 0-5 donde:\n"," \n","* 0 = sur\n","* 1 = norte\n","* 2 = este\n","* 3 = oeste\n","* 4 = pickup\n","* 5 = dropoff\n","\n","El aprendizaje por refuerzo aprenderá el mapeo estado - acción óptimo, es decir, el agente explora el entorno y toma acciones basadas en las recompensas definidas en el entorno.\n","\n","La acción óptima para cada estado es la acción que tiene la mayor recompensa acumulativa a largo plazo.\n","\n","Recordar que el taxi se encuenetra en la fila 3, columna 1,  el pasajero está en la ubicación 2 y nuestro destino es la ubicación 0.\n"]},{"cell_type":"code","execution_count":52,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":19,"status":"ok","timestamp":1685719015746,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"Bcmm4vqWLvGZ","outputId":"452191a8-b0a8-425e-a178-682dcb144609"},"outputs":[{"output_type":"stream","name":"stdout","text":["+---------+\n","|\u001b[35mR\u001b[0m: | : :G|\n","| : | : : |\n","| : :\u001b[43m \u001b[0m: : |\n","| | : | : |\n","|Y| : |\u001b[34;1mB\u001b[0m: |\n","+---------+\n","\n","\n","252\n"]}],"source":["starting_state, info = env.reset(seed = seed)\n","print_env(env)\n","print(starting_state)"]},{"cell_type":"markdown","metadata":{"id":"V2BWvaShZgjo"},"source":["### La tabla de recompensas"]},{"cell_type":"markdown","metadata":{"id":"5vQRLnsDZgjp"},"source":["Cuando se crea el entorno,  se crea también una tabla de transiciones y recompensas inicial llamada **P**. Podemos pensar en ella como una matriz que tiene el número de estados como filas y el número de acciones como columnas.\n","\n","Como cada estado está en esta matriz, podemos ver los valores de recompensa predeterminados asignados al estado:"]},{"cell_type":"code","execution_count":53,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":14,"status":"ok","timestamp":1685719015746,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"dl23O9_NZgjq","outputId":"e8d29e34-3c57-4a1a-f497-f4a3a606f0a6"},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{0: [(1.0, 352, -1, False)],\n"," 1: [(1.0, 152, -1, False)],\n"," 2: [(1.0, 272, -1, False)],\n"," 3: [(1.0, 232, -1, False)],\n"," 4: [(1.0, 252, -10, False)],\n"," 5: [(1.0, 252, -10, False)]}"]},"metadata":{},"execution_count":53}],"source":["env.P[starting_state]"]},{"cell_type":"markdown","metadata":{"id":"BCYnw-lCZgjq"},"source":["El diccionario tiene la estructura:\n","\n","               acción: [(probabilidad, proximo estado, recompensa, done)]\n","\n","Donde:\n","* 0-5 corresponde a las acciones que puede tomar el taxi en el estado actual.\n","* La probabilidad es siempre 1\n","* El siguiente estado es el estado en el que estaríamos si tomamos la acción en este índice del diccionario,\n","* Todas las acciones de movimiento tienen una recompensa de -1 y las acciones de recogida / devolución tienen una recompensa de -10 en este estado en particular. Si estamos en un estado donde el taxi tiene un pasajero y está en el destino correcto veríamos una recompensa de 20 en la acción de devolución (5).\n","* 'done' se usa para decirnos cuándo hemos dejado con éxito a un pasajero en la ubicación correcta. Cada entrega exitosa es el final de un episodio.\n","\n","\n"]},{"cell_type":"markdown","metadata":{"id":"d2hw9RyDZgjr"},"source":["## Resolviendo el entorno sin aprendizaje por refuerzo\n","\n","Veamos qué sucedería si tratamos de utilizar la fuerza bruta para resolver el problema.\n","\n","Dado que tenemos nuestra tabla **P** para recompensas predeterminadas en cada estado, podemos intentar que nuestro taxi navegue solo utilizando esa información.\n","\n","Crearemos un bucle que se ejecutará hasta que un pasajero llegue a un destino (un episodio), o en otras palabras, cuando la recompensa recibida sea 20. \n","\n","El método *env.action_space.sample()* selecciona automáticamente una acción aleatoria del conjunto de todas las posibles acciones.\n","\n","Veamos qué pasa:\n"]},{"cell_type":"code","execution_count":54,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":12,"status":"ok","timestamp":1685719015747,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"8UsFqtDxZgjs","outputId":"d88bf1f4-1f35-4326-c670-21a39f733883"},"outputs":[{"output_type":"stream","name":"stdout","text":["Timesteps taken: 535\n","Penalties incurred: 172\n"]}],"source":["env.reset(seed = seed)\n","\n","epochs = 0\n","penalties, reward = 0, 0\n","\n","frames = [] # for animation\n","\n","terminated = False\n","truncated = False\n","\n","while not terminated and not truncated:\n","    action = env.action_space.sample() #  selecciona una acción aleatoria del conjunto de todas las posibles acciones\n","    state, reward, terminated, truncated, info = env.step(action)\n","\n","    if reward == -10:\n","        penalties += 1\n","    \n","    # Put each rendered frame into dict for animation\n","    frames.append({\n","        'frame': env.render(),\n","        'state': state,\n","        'action': action,\n","        'reward': reward\n","        }\n","    )\n","\n","    epochs += 1\n","    \n","    \n","print(\"Timesteps taken: {}\".format(epochs))\n","print(\"Penalties incurred: {}\".format(penalties))\n"]},{"cell_type":"code","execution_count":55,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":7396,"status":"ok","timestamp":1685719023135,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"NKZMSasSZgjs","outputId":"314a367a-69c8-4499-a904-b4f00753563c"},"outputs":[{"output_type":"stream","name":"stdout","text":["+---------+\n","|\u001b[35m\u001b[34;1m\u001b[43mR\u001b[0m\u001b[0m\u001b[0m: | : :G|\n","| : | : : |\n","| : : : : |\n","| | : | : |\n","|Y| : |B: |\n","+---------+\n","  (Dropoff)\n","\n","Timestep:  535\n","State:  0\n","Action:  5\n","Reward:  20\n"]}],"source":["def print_frames(frames):\n","    for i, frame in enumerate(frames):\n","        clear_output(wait=True)\n","        print(frame['frame'])\n","        print('Timestep: ',i + 1)\n","        print('State: ',frame['state'])\n","        print('Action: ',frame['action'])\n","        print('Reward: ',frame['reward'])\n","        sleep(.01)\n","        \n","print_frames(frames)"]},{"cell_type":"markdown","metadata":{"id":"iMy4xIXiZgjt"},"source":["Como se ve, para entregar solo un pasajero el agente le muchisimos pasos y realiza muchas devoluciones incorrectas. Esto se debe a que no estamos aprendiendo de la experiencia pasada. Podemos ejecutar esto una y otra vez, y nunca se optimizará, el agente no recuerda qué acción fue la mejor para cada estado, que es exactamente lo que el aprendizaje por refuerzo hará.\n","\n","\n","## Utilizando aprendizaje por refuerzo\n","\n","Q-learning permite al agente usar las recompensas del entorno para aprender con el pasar del tiempo la mejor accion a tomar en un estado dado. \n","\n","En el entorno del taxi tenemos la tabla de recompensas P de la que el agente aprenderá. Buscará recibir una recompensa por tomar una acción en el estado actual y luego actualizará el Q-value para recordar si esa acción fue beneficiosa.\n","\n","Los valores almacenados en la tabla se denominan Q-values y se asignan a una combinación (estado, acción).\n","\n","Un Q-value para una combinación particular de estado-acción es representativo de la \"calidad\" de una acción tomada en ese estado. Los mejores Q-values implican mejores posibilidades de obtener mayores recompensas.\n","\n","Por ejemplo, si el taxi se enfrenta a un estado que incluye a un pasajero en su ubicación actual, es muy probable que el Q-values para la recogida sea más alto en comparación con otras acciones, como el descenso o el norte.\n","\n","Los Q-values se inicializan a un valor arbitrario, y a medida que el agente se expone al entorno y recibe diferentes recompensas al ejecutar diferentes acciones, los Q-value se actualizan utilizando la ecuación:\n","\n","\n","$$ Q({\\small state}, {\\small action}) \\leftarrow (1 - \\alpha) Q({\\small state}, {\\small action}) + \\alpha \\Big({\\small reward} + \\gamma \\max_{a} Q({\\small next \\ state}, {\\small a})\\Big)$$\n","\n","\n","\n","donde:\n","\n","- $\\alpha$ es el learning rate $(0 < \\alpha \\le 1)$,  el grado en que los Q-values se actualizan en cada iteración.\n","- $\\gamma$ es el factor de descuento $(0\\le \\gamma \\le 1)$, determina cuánta importancia queremos dar a futuras recompensas. Un valor alto para el factor de descuento (cercano a 1) genera la adjudicación efectiva a largo plazo, mientras que un factor de descuento de 0 hace que nuestro agente considere solo una recompensa inmediata."]},{"cell_type":"markdown","metadata":{"id":"4j_a8iicZgju"},"source":["Se le asigna, o actualiza, el Q-value para un estado y  una acción primero tomando los pesos (1−α) de los viejos Q-value, y luego se le suma el resultado aprendido. \n","\n","El valor aprendido es una combinación de la recompensa por tomar la acción actual en el estado actual y la recompensa máxima, con descuento, del siguiente estado en el que estaremos una vez que tomemos la acción actual.\n","\n","Básicamente, estamos aprendiendo la acción adecuada para tomar en el estado actual al observar la recompensa para el par estado - acción actual, y las recompensas máximas para el siguiente estado. Esto eventualmente hará que nuestro taxi considere la ruta con las mejores recompensas.\n","\n","El  Q-value de un par  estado-acción es la suma de la recompensa instantánea y la recompensa futura con descuento (del estado resultante). La forma en que almacenamos los  Q-value para cada estado y acción es a través de una \n","Q-table\n","\n","La  Q-table es una matriz donde tenemos una fila para cada estado (500) y una columna para cada acción (6). Primero se inicializa a 0, y luego los valores se actualizan con el entrenamiento. \n","\n","Tenga en cuenta que la Q-table tiene las mismas dimensiones que la tabla de recompensas, pero tiene un propósito completamente diferente.\n","\n","\n","## Resumiendo el proceso de Q-Learning\n","\n","*  Inicializar la  Q-table con cero.\n","*  Comenzar explorando acciones: para cada estado, seleccionar una de todas las posibles acciones para el estado actual (S).\n","*  Cambiar al nuevo estado (S') como resultado de la acción (a).\n","*  Para cada acción posible desde el estado (S') seleccionar la que tenga el mayor Q-value.\n","*  Actualizar los valores de  Q-table utilizando la ecuación.\n","*  Setear el próximo estado como estado siguiente.\n","*  Si se alcanza el estado objetivo, luego se repite el proceso.\n","\n","#### Aprovechar los valores aprendidos\n","\n","Después de una exploración aleatoria de acciones los  Q-values tienden a converger sirviendo al agente como una función de valor-acción que puede aprovechar para elegir la mejor acción de un estado dado.\n","\n","Existe una compensación entre la exploración (elegir una acción aleatoria) y la explosión (elegir acciones basadas en Q-values ya aprendidos). Queremos evitar que la acción tome siempre la misma ruta y posiblemente se sobreajuste, por lo que presentaremos otro parámetro llamado $\\epsilon$\n","\n","En lugar de simplemente seleccionar la mejor acción de Q-values, a veces favoreceremos explorar más el espacio de acción. Un valor más bajo de épsilon produce episodios con más penalizaciones (en promedio), lo cual es esperable porque estamos explorando y tomando decisiones aleatorias.\n","\n","\n"]},{"cell_type":"markdown","metadata":{"id":"nXNz5nFlZgju"},"source":["## Implementar Q-learning \n","\n","### Entrenando el agente\n","\n","Primero se inicializa con cero la Q-table a una matriz de 500 x 6."]},{"cell_type":"code","execution_count":56,"metadata":{"id":"h1S8hrW7Zgjv","executionInfo":{"status":"ok","timestamp":1685719023135,"user_tz":180,"elapsed":7,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"}}},"outputs":[],"source":["q_table = np.zeros([env.observation_space.n, env.action_space.n])"]},{"cell_type":"markdown","metadata":{"id":"KiQv4gMEZgjv"},"source":["Ahora se crea el algoritmo de entrenamiento que actualizará esta Q-table mientras el agente explora el entorno durante muchos episodios.\n","\n","En la primera parte de \"while not done\" se decide si se elige una acción aleatoria o aprovechar los Q-values ya calculados. Esto se hace simplemente usando el valor épsilon y comparándolo con la función random.uniform(0, 1), que devuelve un número arbitrario entre 0 y 1.\n","\n","Ejecutamos la acción elegida en el entorno para obtener el siguiente estado (naxe_state) y la recompensa (reward) de realizar la acción. Después de eso, calculamos el valor Q-value para las acciones correspondientes a next_state, y con eso, podemos actualizar fácilmente nuestro Q-value a new_q_value."]},{"cell_type":"code","execution_count":57,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":14759,"status":"ok","timestamp":1685719037888,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"Fcewl3h2Zgjv","outputId":"0db3ef64-3127-4554-bfc9-2aba7325d714"},"outputs":[{"output_type":"stream","name":"stdout","text":["Episode:  9900\n","Training finished.\n","\n","CPU times: user 12.6 s, sys: 564 ms, total: 13.2 s\n","Wall time: 15.5 s\n"]}],"source":["%%time\n","\"\"\"Training the agent\"\"\"\n","\n","import random\n","from IPython.display import clear_output\n","\n","# Hyperparameters\n","alpha = 0.1\n","gamma = 0.95\n","epsilon = 0.1\n","\n","# For plotting metrics\n","all_epochs = []\n","all_penalties = []\n","\n","for i in range(1, 10000):\n","    state, info = env.reset()\n","    epochs, penalties, reward, = 0, 0, 0\n","    terminated = False\n","    truncated = False    \n","    while not terminated and not truncated:\n","        if random.uniform(0, 1) < epsilon:\n","            action = env.action_space.sample() # Explore action space\n","        else:\n","            action = np.argmax(q_table[state]) # Exploit learned values\n","\n","        next_state, reward, terminated, truncated, info = env.step(action) \n","        old_value = q_table[state, action]\n","        next_max = np.max(q_table[next_state])\n","        \n","        new_value = (1 - alpha) * old_value + alpha * (reward + gamma * next_max)\n","        q_table[state, action] = new_value\n","\n","        if reward == -10:\n","            penalties += 1\n","\n","        state = next_state\n","        epochs += 1\n","        \n","    if i % 100 == 0:\n","        clear_output(wait=True)\n","        print('Episode: ', i)\n","\n","print(\"Training finished.\\n\")"]},{"cell_type":"code","execution_count":58,"metadata":{"id":"gVUCpolYbbFT","executionInfo":{"status":"ok","timestamp":1685719037890,"user_tz":180,"elapsed":29,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"}}},"outputs":[],"source":["state, info = env.reset()"]},{"cell_type":"markdown","metadata":{"id":"gmyD8rzGZgjw"},"source":["Ahora que la Q-table se ha establecido en más de 100,000 episodios, veamos cuáles son los Q-values en el estado de nuestra ilustración:"]},{"cell_type":"code","execution_count":59,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":24,"status":"ok","timestamp":1685719037891,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"BgPR_YOeZgjx","outputId":"08658b1e-abb2-4ec6-82f2-4f6766195e0e"},"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([-2.49312614, -3.10309204,  2.75200369, -1.91342681, -7.93290877,\n","       -6.91803769])"]},"metadata":{},"execution_count":59}],"source":["q_table[starting_state]"]},{"cell_type":"markdown","metadata":{"id":"cxnKVaWKZgjx"},"source":["## Evaluar al agente\n","\n","Vamos a evaluar el desempeño del agente. No necesitamos explorar más acciones, por lo que ahora la siguiente acción siempre se selecciona utilizando el mejor Q-value:"]},{"cell_type":"code","execution_count":60,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"elapsed":19,"status":"ok","timestamp":1685719037892,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"},"user_tz":180},"id":"5hO1FZV1Zgjx","outputId":"9f68fa65-71c6-470e-f92e-11e89004d908"},"outputs":[{"output_type":"stream","name":"stdout","text":["Results after  100 episodes:\n","Average timesteps per episode:  12.0\n","Average penalties per episode:  0.0\n"]}],"source":["\"\"\"Evaluate agent's performance after Q-learning\"\"\"\n","\n","total_epochs, total_penalties = 0, 0\n","episodes = 100\n","\n","for _ in range(episodes):\n","    state, info = env.reset(seed = seed)\n","    epochs, penalties, reward = 0, 0, 0\n","    \n","    terminated = False\n","    truncated = False\n","    while not terminated and not truncated:\n","        action = np.argmax(q_table[state])\n","        state, reward, terminated, truncated, info = env.step(action)\n","\n","        if reward == -10:\n","            penalties += 1\n","\n","        epochs += 1\n","\n","    total_penalties += penalties\n","    total_epochs += epochs\n","\n","print('Results after ',episodes, 'episodes:')\n","print('Average timesteps per episode: ',total_epochs / episodes)\n","print('Average penalties per episode: ',total_penalties / episodes)"]},{"cell_type":"markdown","metadata":{"id":"jsmviDs6Zgjy"},"source":["## Hiperparámetros y  optimizaciones\n","\n","\n","Los valores de `alpha`, `gamma`, y `epsilon` estan basados en la intución y en algunos \"hit and trial\", pero hay mejores formas de encontrar buenos valores.\n","\n","Idealmente los tres deberían disminuir con el tiempo dado que a medida que el agente continúa aprendiendo, en realidad acumula antecedentes más resistentes:\n","* $\\alpha$ debería disminuir a medida que continua obteniendo una base de conocimiento cada vez mayor.\n","* $\\gamma$ a medida que se acerque más y más al límite, su preferencia por la recompensa a corto plazo debería aumentar, ya que no estará lo suficientemente cerca como para obtener la recompensa a largo plazo, lo que significa que su gama debería disminuir.\n","* $\\epsilon$ a medida que se desarrolla la estrategia, se tiene menos necesidad de exploración y más explotación para obtener más utilidad de la política, por lo que a medida que aumentan los ensayos, epsilon debería disminuir.\n","\n","\n","## Tuneando los  hiperparámetros\n","\n","Modifique los hiperparametros analizando que significa cada uno y como varían los resultados"]},{"cell_type":"code","execution_count":61,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"VYc6T-uKZgjy","executionInfo":{"status":"ok","timestamp":1685719046461,"user_tz":180,"elapsed":8583,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"}},"outputId":"d5b4a5c9-46bd-4951-deb9-96c0fa82a3c3"},"outputs":[{"output_type":"stream","name":"stdout","text":["Episode:  10000\n","Training finished.\n","\n","CPU times: user 8.09 s, sys: 586 ms, total: 8.67 s\n","Wall time: 8.62 s\n"]}],"source":["%%time\n","\"\"\"Training the agent\"\"\"\n","\n","import random\n","from IPython.display import clear_output\n","\n","# Hyperparameters\n","alpha = 0.1\n","gamma = 0.95\n","epsilon = 0.1\n","\n","# For plotting metrics\n","all_epochs = []\n","all_penalties = []\n","\n","for i in range(1, 10001):\n","    state, info = env.reset()\n","    epochs, penalties, reward, = 0, 0, 0\n","    terminated = False\n","    truncated = False    \n","    while not terminated and not truncated:\n","        if random.uniform(0, 1) < epsilon:\n","            action = env.action_space.sample() # Explore action space\n","        else:\n","            action = np.argmax(q_table[state]) # Exploit learned values\n","\n","        next_state, reward, terminated, truncated, info = env.step(action) \n","        \n","        old_value = q_table[state, action]\n","        next_max = np.max(q_table[next_state])\n","        \n","        new_value = (1 - alpha) * old_value + alpha * (reward + gamma * next_max)\n","        q_table[state, action] = new_value\n","\n","        if reward == -10:\n","            penalties += 1\n","\n","        state = next_state\n","        epochs += 1\n","        \n","    if i % 100 == 0:\n","        clear_output(wait=True)\n","        print('Episode: ',i)\n","\n","print(\"Training finished.\\n\")"]},{"cell_type":"code","execution_count":62,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"RBjh7_GkZgjz","executionInfo":{"status":"ok","timestamp":1685719046463,"user_tz":180,"elapsed":30,"user":{"displayName":"martin Llofriu","userId":"03446141341826292689"}},"outputId":"c6d8cb58-f64b-4251-afcf-40cc623abead"},"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([-0.91585906, -0.8754543 ,  2.75200369,  0.02984505, -7.54017364,\n","       -7.23887159])"]},"metadata":{},"execution_count":62}],"source":["q_table[starting_state]"]}],"metadata":{"colab":{"provenance":[]},"kernelspec":{"display_name":"Python 3 (ipykernel)","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.10"}},"nbformat":4,"nbformat_minor":0}