Capítulo 4. Programación dinámica

En este capítulo introducimos el algoritmo Value Iteration como máximo exponente de la programación dinámica, que pone en valor la ecuación de Bellman presentada en el capítulo anterior. Es muy conveniente empezar entendiendo los fundamentos de la programación dinámica, puesto que es la base de muchos de los algoritmos de aprendizaje por refuerzo que se aproximan a la solución del problema de forma incremental.

Empezaremos el capítulo con ejemplos que, de forma gradual, irán introduciendo las principales ideas que hay detrás de este método. Una vez explicado el algoritmo del método, pasaremos a mostrar cómo funciona en la práctica con una implementación en Python para resolver el problema del entorno Frozen-Lake. Aprovecharemos el ejemplo práctico para continuar introduciendo conceptos mediante un análisis más detallado del comportamiento del agente. Finalmente, usaremos el mismo ejemplo para mostrar técnicas que se pueden emplear para estimar la función de transición y la función de recompensa del entorno, cuando estas no son visibles para el agente.

4.1 Método Value Iteration

Programación dinámica

La programación dinámica, o Dynamic Programming (DP), fue introducida por primera vez por Richard E. Bellman en la década de 1950. El término «dinámica» significa que el problema tiene componentes secuenciales o temporales, y «programación» se refiere a una política de optimización. En resumen, la programación dinámica proporciona un marco general para problemas dinámicos complejos dividiéndolos en subproblemas.

Un ejemplo ilustrativo de la idea subyacente en este método puede ser la serie de Fibonacci[1], donde cada número en la secuencia de Fibonacci es la suma de los dos anteriores, comenzando desde 0 y 1. Por ejemplo, se puede calcular el cuarto número de la serie F4 = F3 + F2, como F4 = (F2 + F1) + F2 reutilizando la solución del subproblema anterior F2 = F1 + F0.

Ahora bien, la DP requiere un conocimiento completo del entorno que queremos resolver (requiere conocer el modelo de recompensa y, sobre todo, el modelo de transición; es decir, la función de recompensas R y la función de transición P del MDP). Pero, a menudo, tenemos un conocimiento limitado del entorno en el aprendizaje por refuerzo, y no conocemos esta información. Podemos decir que se trata de un método model-based, tal como hemos presentado en el primer capítulo.

Otra limitación de la DP es que una de las propiedades que debe cumplir el problema para poder aplicar este método es que su solución se pueda descomponer en soluciones a sus subproblemas. La superposición de estos subproblemas implica que el número de subproblemas debe ser finito. En resumen, cuando pensamos en resolver un problema con DP, asumimos que el conjunto de estados y el conjunto de acciones son ambos finitos, y que se da un modelo perfecto del entorno.

No obstante, a pesar de estas limitaciones para su aplicabilidad, la DP proporciona un marco fundamental para aprender a interactuar con el MDP de forma incremental, ya que la mayoría de los algoritmos de aprendizaje por refuerzo intentan aproximarse de esta manera a la resolución del problema. Por este motivo, este método es uno de los primeros capítulos de cualquier libro académico sobre RL.

En resumen, la DP, en lugar de resolver un problema complejo como un todo, divide el problema en subproblemas y, luego, para cada subproblema, calcula y almacena la solución. Si aparece el mismo subproblema repetido, este no se calcula; en su lugar, se usa la solución ya calculada. El algoritmo que usa esta aproximación en el caso de RL se llama Value Iteration y es el que presentaremos en este capítulo[2].

Cómo aprender recursivamente

Antes de empezar a describir el método Value Iteration, mostraremos con un par de ejemplos la idea que hay detrás del método. Estos ejemplos nos servirán para irnos familiarizando con la función V y con la función Q, que nos acompañarán a partir de ahora en todos los métodos que se presenten en este libro.

Consideremos un entorno estocástico muy simple, llamado «cruz», como el que se muestra en la Figura 4.1. Tenemos un estado inicial 0 rodeado por cuatro estados (1, 2, 3 y 4), cuyo valor de estado podemos suponer que ya hemos podido calcular previamente. En concreto, sus valores respectivos son V(1)=+1, V(2)=+2, V(3)=+3 y V(4)=+4.

Como se intuye, se ha simplificado el ejemplo para poder centrar la atención en cómo podemos calcular el valor del estado 0, es decir, V(0). Veremos que de los estados más allá de los cuatro estados adyacentes al estado 0 no nos hace falta información, dado que sabemos el valor de cada uno de estos estados. Es decir, las celdas que hay a partir de las celdas 1, 2, 3 y 4 (que se indican con las celdas recortadas en la Figura 4.1) no son relevantes para nuestro caso de estudio.

Desde el estado 0, a cada estado se llega con las acciones 1, 2, 3 y 4, respectivamente. Para continuar simplificando el ejemplo, asumimos que es un caso de recompensa retrasada y, por tanto, la recompensa se recibe cuando se llega al estado terminal. Así pues, en todas las acciones que nos llevan desde el estado inicial 0 a sus adyacentes la recompensa es 0.

Como hemos indicado que se trata de un entorno estocástico, un detalle muy relevante de la dinámica de este entorno «cruz» es que cada acción se comporta con una cierta aleatoriedad, de la misma manera que en el entorno resbaladizo de Frozen-Lake. En concreto hay 1/3 de probabilidad de que la acción nos lleve a la celda esperada, pero hay 1/3 de probabilidad de que «resbalemos» hacia la izquierda, con relación a la celda objetivo de la acción, y 1/3 de probabilidad de que «resbalemos» hacia la derecha. Para continuar con un caso de estudio simple, consideramos un factor de descuento 𝛾 = 1.

Figura 4.1 Representación gráfica del entorno «cruz». Se resalta el estado inicial, en el centro, y los estados que tiene adyacentes. Con las celdas recortadas se indica que hay más celdas a partir de las celdas 1, 2, 3 y 4, pero el detalle de su geometría no es relevante para el caso que estamos considerando.

Resumamos de manera más visual, en la Figura 4.2, la transición entre estados que permiten las acciones del entorno «cruz» que acabamos de presentar. En la figura se observan las cuatro acciones que se pueden realizar desde el estado inicial, con las respectivas posibles transiciones que cada una de ellas permite, debido a la estocasticidad del entorno. Esta representación gráfica resume toda la descripción anterior sobre el entorno y nos facilitará seguir las explicaciones del ejemplo.

Por otro lado, definimos para este ejemplo que el agente se guía por una política estocástica que da la misma probabilidad a todas las acciones que se pueden realizar desde un estado. Es decir, en este ejemplo, de 4 acciones que se pueden realizar desde el estado 0, el agente puede realizar cada una de ellas con la misma probabilidad del 25%.

Figura 4.2 Representación de la transición entre estados con sus acciones y valores de estado del entorno «cruz».

Definido el comportamiento (estocástico) del entorno y de la política (estocástica) que sigue el agente, la pregunta es: ¿cuál es el valor del estado V(0)?

Dado que estamos ante una política estocástica, el valor de V(0) lo podemos calcular según la fórmula

, introducida en el capítulo anterior. Tenemos los valores de

, pero debemos calcular los valores Q de las respectivas acciones. Lo podemos hacer guiados por la Figura 4.2. Recordemos que la recompensa para las acciones es 0 y que gamma es 1. Podemos concluir que:

𝑄(0, 0) = 1/3 × 𝑉(1) + 1/3 × 𝑉(2) + 1/3 × 𝑉(3)

𝑄(0, 1) = 1/3 × 𝑉(2) + 1/3 × 𝑉(3) + 1/3 × 𝑉(4)

𝑄(0, 2) = 1/3 × 𝑉(1) + 1/3 × 𝑉(3) + 1/3 × 𝑉(4)

𝑄(0, 3) = 1/3 × 𝑉(1) + 1/3 × 𝑉(2) + 1/3 × 𝑉(4)

Sustituyendo los valores de los estados 1, 2, 3 y 4, de cuyo valor ya disponemos, resultan los siguientes valores para la función Q:

𝑄(0, 0) = 1/3 × 1 + 1/3 × 2 + 1/3 × 3 = 2

𝑄(0, 1) = 1/3 × 2 + 1/3 × 3 + 1/3 × 4 = 3

𝑄(0, 2) = 1/3 × 1 + 1/3 × 3 + 1/3 × 4 = 2.67

𝑄(0, 3) = 1/3 × 1 + 1/3 × 2 + 1/3 × 4 = 2.33

Ahora ya tenemos toda la información y podemos aplicar la fórmula anterior para calcular el valor del estado 0:

V(0) = 0.25 × 𝑄(0, 0)+ 0.25 × 𝑄(0, 1)+ 0.25 × 𝑄(0, 2) + 0.25 × 𝑄(0, 3) = 2.5

Ahora bien, ¿cómo podemos abordar este problema en el caso de que no se conociesen los valores de los estados 1, 2, 3 y 4? De lo explicado en el capítulo anterior, seguro que intuye que la ecuación de Bellman nos puede ayudar en hacer estos cálculos de «forma recursiva», es decir, aplicar la misma estratégia para calcular antes V(1), V(2), V(3) y V(4) a partir de sus celdas adyacentes, y así sucesivamente.

La simplificación del ejemplo deliberadamente ha evitado que apareciera un bucle en las transiciones, permitiendo así calcular el valor de un estado a partir del valor de sus estados adyacentes. Sin embargo, la presencia de un bucle impide este enfoque propuesto y debemos hacerlo de otra manera. Veamos cómo se puede tratar el caso de un bucle, nuevamente con un entorno simple para podernos centrar en la idea que hay detrás de la solución. Este nuevo entorno lo llamaremos «bucle de dos estados», y está compuesto por dos estados (1 y 2), que presentan el diagrama de transición de estados y recompensas del entorno que se muestra en la Figura 4.3.

Figura 4.3 Representación gráfica del entorno «bucle de dos estados» con sus transiciones entre estados y sus recompensas correspondientes.

En este ejemplo, solo tenemos dos posibles transiciones: del estado 1 solo podemos realizar una acción que nos lleve al estado 2 con recompensa +1, y del estado 2 solo podemos realizar una acción que nos devuelva al estado 1 con una recompensa +2. Entonces, la «vida» de nuestro agente se mueve en una secuencia infinita de estados debido al bucle infinito entre los dos estados. En este entorno, ¿cuál es el valor de ambos estados?

Supongamos que tenemos un factor de descuento γ<1, pongamos que γ = 0.9. Recordemos del capítulo anterior que el valor óptimo del estado se puede obtener con la siguiente fórmula:

Pero en nuestro entorno «bucle de dos estados», dado que solo hay una acción disponible en cada estado, nuestro agente no tiene opciones y, por lo tanto, podemos simplificar la fórmula anterior de la siguiente manera:

Por ejemplo, si partimos del estado 1, la secuencia de estados será [1, 2, 1, 2, 1, 2, …]. Y, dado que cada transición del estado 1 al estado 2 recibe una recompensa de +1 y cada transición hacia atrás recibe una recompensa de +2, la secuencia de recompensas será [+1, +2, +1, +2, +1, +2,…]. Por tanto, la fórmula anterior para el estado 1 se convierte en:

Estrictamente hablando, es imposible calcular el valor exacto de nuestro estado V*(1), pero con un factor de descuento γ = 0.9, la contribución de una nueva acción disminuye con el tiempo. Por ejemplo, para el time step t = 37 el resultado de la fórmula es 14.7307838, para el time step t = 50 el resultado es 14.7365250, y para el time step t = 100 el resultado es 14.7368420. Eso significa que podemos detener el cálculo en algún punto (por ejemplo, en t = 50) y aun así obtener una buena estimación de la función V, en este caso V (1) = 14.736.

Algoritmo Value Iteration

Los ejemplos anteriores nos permiten ver la esencia de un procedimiento más general para calcular el valor óptimo de un estado, llamado «algoritmo de Value Iteration» (VI). Esto nos permite calcular numéricamente y de forma recursiva los valores de los estados de los MDP, con probabilidades de transición y recompensas conocidas.

Básicamente, el algoritmo Value Iteration calcula el valor óptimo de un estado mejorando iterativamente la estimación de V(s). Para ello, el algoritmo VI empieza inicializando el valor de todos los estados a valores aleatorios. Sabemos que la función de valor se puede calcular realizando la acción que maximiza la función Q, según la fórmula siguiente:

El algoritmo calcula el valor Q para todos los pares estado-acción a partir de aquel estado. Seleccionamos el valor máximo de Q como el valor del estado V(s).

El método de VI requiere formalmente un número infinito de iteraciones para converger y para obtener la función de valor óptimo. En la práctica, en el ejemplo anterior de entorno «bucle de dos estados», hemos mostrado que podemos detenernos una vez que la función de valor del estado cambia solo una pequeña cantidad en una iteración del ciclo de entrenamiento.

Se garantiza que el método VI converge a los valores óptimos según la literatura del tema[3] y, aunque hay diferentes criterios para finalizar el bucle[4], para el objetivo práctico de este libro en el ejemplo que presentaremos en la siguiente sección simplemente fijaremos un umbral de recompensa que calcularemos a partir de unos episodios de prueba. Esta aproximación nos permite «jugar» más fácilmente con el código, dado que podemos limitar los tiempos de ejecución simplemente relajando el umbral y, a la vez, visualizar, como mostraremos, gráficos a partir de las recompensas que serán útiles para el propósito didáctico de este libro.

El siguiente pseudocódigo resume el algoritmo que implementaremos y explicaremos en detalle en la siguiente sección:

Pseudocódigo 4.1 Algoritmo Value Iteration.

4.2 Implementación del método Value Iteration

En esta sección presentamos cómo implementar el método Value Iteration para resolver el entorno Frozen-Lake. Mostraremos paso a paso el código que puede encontrar en el GitHub del libro para irlo ejecutando en Colab a medida que va avanzando en la lectura.

Recordemos que, en el entorno de Frozen-Lake, el objetivo del agente es alcanzar el estado objetivo «G» desde el estado inicial «S», sin visitar agujeros indicados por «H». Si el agente llega al estado «G», le asignamos una recompensa de 1, y si visita cualquier otro estado le asignamos una recompensa de 0.

Comenzaremos el código importando las librerías requeridas. En concreto, además de importar la librería gym que ya hemos presentado en anteriores capítulos, nos bastará con importar la librería matemática numpy. También al principio definiremos algunas variables que serán usadas a lo largo del código, como el factor de descuento GAMMA o la variable ENV_NAME, para especificar el entorno concreto del paquete gym que usaremos. De esta manera, podremos realizar pruebas de nuestro algoritmo con más de un entorno (veremos más adelante que proponemos usar, en este capítulo, además de FrozenLake-v0, el FrozenLake8x8-v0).

La clase Agent

De la misma manera que hicimos en el capítulo 2, crearemos una clase Agent que mantendrá todos los datos y el código correspondiente al agente, como por ejemplo el método select_action(). Para ello, en el constructor crearemos las estructuras de datos que nos mantendrán la información del agente. En concreto, la más importante será el diccionario V, que mantiene el valor de los estados. Lo especificaremos de la siguiente forma:

Como puede ver, también creamos un entorno env en el constructor del agente, que se utilizará para obtener los tamaños del espacio de estados y el espacio de acciones pero, sobre todo, para acceder a la función de transición del entorno que requeriremos en este método VI.

El siguiente método del agente, calc_action_value, calcula la función Q para un par estado-acción, aplicando la ecuación de Bellman presentada en el capítulo anterior, concretamente como

Es importante notar que la función de probabilidad requerida en la fórmula se obtiene de la función de transición del entorno self.env.P[state][action]]. Volveremos con este detalle más adelante.

A continuación, se describe el código para este método:

Para seleccionar la mejor acción a partir de un estado dado, el agente usa el método select_action, que se sirve del método calc_action_value que acabamos de presentar. El código correspondiente a este método de la clase Agent es el siguiente:

El código de este método es bastante simple; básicamente itera sobre todas las acciones posibles que se pueden realizar desde un estado dado en el entorno y calcula el valor para cada acción. Finalmente devuelve la acción con el valor de la función Q más grande.

Nos queda programar el método Value Iteration siguiendo el pseudocódigo presentado en la sección anterior. Hemos considerado programarlo como un método más de la clase Agent, el método value_iteration():

Mirando el código, puede ver que codifica un time step del pseudocódigo presentado. Concretamente, recorre todos los estados del entorno actualizando su valor (que mantiene en la variable del agente V) con el valor máximo de los posibles valores Q de las acciones disponibles desde ese estado dado.

Bucle de entrenamiento

Después de presentar la clase Agent y sus métodos, pasemos a describir el bucle de entrenamiento que hemps decidido implementar en este ejemplo didáctico. La lógica general de nuestro algoritmo de entrenamiento es simple; ejecutaremos los siguientes pasos:

1. Con el método value_iteration se realiza un time step sobre todos los estados, actualizando la tabla V que contiene los valores de los estados.

2. Luego se prueban varios episodios completos para verificar las mejoras usando la tabla V de valores de estado acabada de actualizar.

3. Si la recompensa promedio para esos episodios de prueba está por encima del umbral que nos hemos marcado, entonces dejamos de entrenar.

Veamos cada uno de estos pasos. El primer paso se realiza simplemente llamando al método value_iteration() del agente.

La función Python en el código que corresponde al segundo punto de los anteriores, que realiza una prueba para ver cómo va el aprendizaje de los valores de estado V a partir de las recompensas que se reciben con unos episodios de prueba, es la siguiente:

El anterior código simplemente crea un número de episodios determinados (que hemos definido en la variable TEST_EPISODES) y calcula la recompensa obtenida en media por cada episodio.

Finalmente, a continuación se muestra el código correspondiente al bucle de entrenamiento que utiliza el método y la función acabados de describir:

En la variable REWARD_THESHOLD se concreta el umbral de recompensas que se desea conseguir. Con un propósito didáctico podemos ir modificándolo y viendo cómo se comporta el entrenamiento.

Ahora bien, si lo que perseguimos es conseguir unos valores V óptimos, podemos poner un umbral mucho más alto, o cambiar la condición para poder detener el bucle una vez que la función de valor del estado V cambia solo una pequeña cantidad de una iteración a otra del ciclo de entrenamiento (en este caso deberíamos crear un método nuevo del agente, dado que la información de la tabla V es interna al agente).

En resumen, la lógica general de nuestro código es simplemente un bucle que se repetirá hasta que el agente logre el rendimiento esperado (en nuestro ejemplo, un umbral). Primero llama al método que ejecuta el método Value Iteration y, a continuación, se realiza una comprobación de las mejoras en el entrenamiento del agente.

Para monitorizar el bucle de entrenamiento, de momento hemos añadido un código que nos imprime información por pantalla (con un simple print()) cada vez que el bucle de entrenamiento mejora los resultados:

4.3 Análisis del comportamiento del agente

Una vez entrenado el agente, podemos usar este mismo ejemplo para continuar introduciendo nuevos conocimientos mediante el análisis de su comportamiento en varios aspectos. Veamos algunos de ellos.

Política del agente

Una vez calculada la función de valor con el algoritmo VI para los estados del entorno, que consideramos adecuada — puesto que permite superar el umbral de recompensas que nos hemos marcado — , podemos observar cómo esto se traduce en una política, es decir, en qué acciones el agente realizará en cada estado. Para ello, hemos definido la función extract_policy(), mostrada a continuación:

Esta función calcula los valores Q usando el método calc_action_value() del agente que la función ha recibido como parámetro. Después de calcular la función Q, podemos extraer la política seleccionando la acción que tiene el valor Q máximo para cada estado.

Si asumimos que el método Value Iteration hizo suficientes iteraciones del bucle de entrenamiento, dado que estamos calculando la función Q usando la función V óptima, la política extraída de la función Q será la política óptima.

Notemos que se trata de un ejemplo de política determinística, en la que se mapea cada uno de los estados a una acción en particular, en contraposición con una política estocástica en la que el agente puede realizar diferentes acciones desde un mismo estado. Otra cosa es que el agente haya ido cambiando su política durante el proceso de aprendizaje, es decir, haya ido variando las acciones que realizaba en cada estado a medida que avanzaba el proceso de aprendizaje. Recordemos que el agente ha partido de una política aleatoria, donde la probabilidad de todas las acciones es uniforme, y a medida que ha ido entrenándose ha ido mejorando su política.

Quizás nos ayude poder «visualizar» la política. Para ello, hemos creado la función de soporte print_policy(), que muestra por pantalla qué acción realizará el agente si sigue la política que se le pasa como argumento a esta función. Además de mostrar la matriz con el valor de la acción por cada estado, se muestra una representación de la dirección que indica la acción con los caracteres «<», «>», «^» y «v», que nos puede resultar más intuitiva. En relación con el párrafo anterior, donde hacíamos referencia a que la política iba cambiando a medida que el agente aprendía, cabe decir que esto se puede comprobar usando esta función en el bucle de entrenamiento cada cierto número de time steps. Al ejecutar el código de la función que se muestra a continuación, se muestra la política que sigue nuestro agente una vez finalizado el entrenamiento.

Viendo la política determinista que resulta del entrenamiento, puede sorprender la acción que se realiza en algunos estados. Por ejemplo, que la acción en el estado inicial 0 sea ir a la izquierda, o que en el estado 4 también sea ir a la izquierda. Pero si lo analizamos con un poco más de detalle, podemos comprobar que es la única acción que nos asegura no caer en el agujero del estado 5. Estudiemos con más detalle esta casuística, ya que nos ayudará a ir asentando los conocimientos básicos.

Recuerde que al analizar las probabilidades de transición del entorno estocástico almacenadas en la matriz env.env.P, las posibles transiciones asociadas con cada acción en el entorno son de un 33% de probabilidad de que nuestra acción se ejecute sin modificaciones, pero hay un 33% de probabilidad de que «resbalemos» hacia la izquierda en relación a la celda objetivo de la acción, y un 33% de probabilidad de que «resbalemos» hacia la derecha (es decir, acabando en alguna celda diferente de la que el agente quería).

En el ejemplo que estamos considerando, si el agente está en el estado 0 y selecciona la acción «izquierda» (acción 0), se aplica la función de transición almacenada en env.env.P[0][0], que indica todas las transiciones posibles desde ese par estado-acción a los siguientes estados, junto con las recompensas esperadas. Recordemos su valor:

Es decir, en un 33% de probabilidad puede pasar al estado 4, y en cualquier otro caso se queda en el estado 0.

Cuando el agente está en el estado 4 y selecciona la acción «izquierda» (acción 0), se aplica la función de transición indicada en env.env.P[4][0], que almacena todas las transiciones posibles desde ese par estado-acción a los siguientes estados, junto con las recompensas esperadas:

Interpretando esta información, comprobamos que tiene un 33% de probabilidad de volver al estado 0, un 33% de probabilidad de quedarse en el estado 4, y un 33% de probabilidad de pasar al estado 8.

Tratemos de expresar gráficamente esta información en la Figura 4.4; así nos resultará más fácil comprender las decisiones del agente. Las flechas oscuras indican la acción seleccionada por el agente y las blancas indican las acciones reales que se realizan en un 33% de probabilidades cada una de ellas.

Puede observar que, si el agente selecciona la acción «izquierda» en estos dos estados, nunca puede caer en el agujero del estado 5. Por ello, el agente seleccionará repetidamente estas acciones a pesar de poder quedarse yendo y viniendo varias veces entre los estados 0 y 4. Pero en algún momento llegará al estado 8 habiendo evitado seguro caer en el agujero del estado 5.

Es decir, a la hora de tomar decisiones el agente no solo tiene en cuenta las direcciones hacia las que quiere ir, sino que también tiene en cuenta las direcciones de las que quiere huir. Por eso en estos dos estados la política es seleccionar la acción «izquierda», aunque a primera vista pueda sorprendernos.

Figura 4.4 Representación gráfica del entorno Frozen-Lake. Se indican las acciones seleccionadas (flechas oscuras) y las acciones posibles (flechas blancas) para los estados 0, 4 y 8.

Continuemos con el ejemplo. Una vez el agente llega al estado 8, observamos que opta por querer «retroceder» al estado 4, del que viene. Veamos ahora la función de transición para este estado:

Nuevamente, si nos fijamos en la Figura 4.4, se entiende claramente que es una estrategia para poder garantizar no caer en el agujero del estado 12, y que tarde o temprano llegará al estado 9.

Lo hemos explicado a este nivel de detalle para repasar el funcionamiento de los entornos estocásticos y cómo esta estocasticidad influye en las políticas de los agentes, cuyo objetivo es obtener la máxima recompensa acumulada o retorno (que en este entorno Frozen-Lake solo se obtiene al final, cuando se llega al estado 15).

Debemos notar que, como no hay ningún tipo de penalización por tardar más o menos en conseguir este objetivo, la recompensa es cero para cualquier acción, y el gamma es igual a 1. El agente puede aprovechar este hecho para tratar de evitar caer en estados agujero, como hemos explicado, sin preocuparse en hacerlo rápido. Pero, en este entorno Frozen-Lake, ¿podemos evitar todos los agujeros?

Episodios que genera el agente

También podemos visualizar episodios por pantalla, con un código simple como el que se lista a continuación:

Como ejemplo, en la Figura 4.5 se muestra la salida por pantalla de una ejecución de este código. Podemos observar, en este caso concreto de episodio, lo que comentábamos en el anterior apartado: que durante los primeros 13 time steps el agente está yendo y viniendo entre los estados 0, 4 y 8. Pero al final, cuando ya llega al estado 9, es capaz de llegar rápido al estado final.

Le propongo que genere varios episodios reejecutando el mismo código y que observe el comportamiento del agente. Seguro que en alguna de las ejecuciones podrá observar cómo no podemos garantizar no caer en un agujero. Por ejemplo, siguiendo la política que el agente ha aprendido en nuestro ejemplo, un 33% de veces desde el estado 9 pasa al estado 10 y desde este estado puede llegar al estado 6.

Figura 4.5 Ejemplo de episodio generado por nuestro agente.

Una vez el agente se encuentra en el estado 6, es imposible evitar totalmente el riesgo de caer en un agujero, como sí conseguíamos en los estados que hemos analizado en detalle en el apartado anterior. El motivo es claro: no hay acción posible desde el estado 6 que no incluya riesgo de caer en uno de los agujeros que tiene en ambos lados (estados 5 y 7). Las acciones de «izquierda» o «derecha» tienen el 33% de probabilidades de enviarnos directamente a estos estados 5 y 7, respectivamente. Y las acciones «arriba» o «abajo» aún tienen más riesgo (un 33% a cada estado).

Por tanto, si nos propusiéramos entrenar nuestro agente de manera que consiguiera recompensas con un umbral muy alto, probablemente el bucle de entrenamiento del algoritmo Value Iteration se convertiría en un bucle infinito. ¿Lo podríamos monitorizar mediante los print() que hemos puesto en el código mostrado anteriormente? Seguramente, pero la información con tantas líneas por pantalla podría resultar abrumadora. Veamos, a continuación, algunas alternativas. De paso, presentaremos una herramienta muy útil para monitorizar los procesos de aprendizaje de nuestros agentes.

Análisis con TensorBoard

Seguro que ya ha pensado que visualizar la evolución del aprendizaje del agente con un gráfico, en lugar de mostrar por pantalla la recompensa media de los episodios prueba y el time step (como hacemos en el código mostrado), sería mucho mejor. En realidad, ya ha visto que en el código del GitHub hay líneas adicionales de código que no hemos comentado y que hacen referencia a algo llamado «TensorBoard».

TensorBoard[5] es una herramienta de visualización en el ecosistema de TensorFlow[6] de Google, que se puede usar para representar gráficamente métricas cuantitativas de diferente índole. En este apartado describiremos las características mínimas que necesitaremos para empezar a utilizar esta librería para visualizar la evolución del aprendizaje del agente. Sin duda, podríamos haber optado por usar un gráfico construido con la popular librería Python matplotlib[7], pero en realidad TensorBoard es una herramienta que resulta esencial para monitorizar redes neuronales y, por ende, modelos de aprendizaje por refuerzo profundo. Por este motivo hemos considerado oportuno introducirla desde un principio, porque será muy útil en el futuro.

Para usar TensorBoard solo se necesita importar tensorboard de torch.utils — en concreto, SummaryWriter, la clase principal — para registrar datos que sean consumidos y visualizados por TensorBoard:

Hemos optado por usar PyTorch[8], que ofrece compatibilidad con TensorBoard, puesto que cuando usemos redes neuronales para los agentes lo haremos con la librería PyTorch en lugar de TensorFlow[9]. En la documentación oficial[10] se pueden encontrar detalles de su funcionalidad.

A continuación, se indica el fichero donde se registrará toda la información que queremos visualizar. Lo hacemos con el argumento en el momento de crear un objeto de la clase SummaryWriter:

Podemos hacer que algo quede registrado invocando a métodos del objeto writer, como add_scalar():

En este caso se trata de valores escalares, suficiente para nuestro propósito. Pero con TensorBoard podemos tratar con otros tipos de datos, como histograma, imagen, gráfico, etc.

Para indicar que se ha finalizado el registro de información, se invoca el método close() del objeto:

Con todo lo dicho, el bucle de entrenamiento desde el que iremos guardando la recompensa de los episodios de prueba quedará así:

Para poder visualizar los gráficos con toda la información almacenada, debemos cargar primero las extensiones de TensorBoard en Colab. Lo podemos hacer del siguiente modo:

Ya podemos lanzar TensorBoard indicándole en el flag — logdir el directorio donde se encuentran los datos que queremos visualizar:

Si ha seguido estos pasos, podrá visualizar por pantalla un gráfico equivalente al mostrado en la Figura 4.6.

Figura 4.6 Gráfico obtenido con TensorBoard, que visualiza la evolución del proceso de aprendizaje medido con la recompensa media obtenida por los episodios de prueba a lo largo de los time steps requeridos para el entrenamiento.

Le sugiero que practique con TensorBoard viendo, por ejemplo, cómo con diferentes ejecuciones del mismo código se obtienen diferentes resultados. En la Figura 4.7 se muestran tres ejecuciones del mismo código. Como podemos observar, el número de timesteps que se requieren para llegar a una solución puede variar bastante, dado que estamos tratando con un entorno estocástico.

Figura 4.7 Comparación de tres ejecuciones del mismo agente con el mismo entorno Frozen-Lake, donde se observa que la estocasticidad del entorno comporta que se requiera diferente número de time steps para llegar a la solución del problema.

Esperamos que con este ejemplo de uso de TensorBoard pueda empezar a generar estos gráficos para los próximos algoritmos que iremos presentando. Le dejamos explorar por su cuenta las diferentes opciones del «cuadro de mando» que ofrece TensorBoard.

Comportamiento del agente en un entorno más complejo

Recordemos que la librería Gym proporciona varios entornos con los que podemos experimentar. Uno de ellos es una versión del entorno Frozen-Lake de dimensiones más grandes, con 64 estados en forma de cuadrícula de 8 x 8. En la Figura 4.8 se muestra una imagen de este entorno, donde el tipo de cada una de las celdas se indica con la misma codificación que en el entorno Frozen-Lake anterior.

Figura 4.8 Representación del entorno FrozenLake8x8-v0, de la librería gym.

Para poder probar en este nuevo entorno todo el código hasta ahora presentado en este capítulo de libro, solo hace falta instanciar la variable ENV_NAME con el nuevo nombre:

Si intenta realizar nuevas ejecuciones en Colab, verá que esta versión más grande del entorno de Frozen-Lake requiere más time steps para ser resuelta. Además, a través de los gráficos obtenidos con TensorBoard, la mayoría de las veces el entorno de mayor tamaño tarda más a tener el primer episodio exitoso y poder empezar a aprender, y esto se observa en el lento aumento de recompensas.

4.4 Estimación de la función de transición y recompensas

En la práctica, recordemos que el método de Value Iteration tiene varias limitaciones. En primer lugar, el espacio de estados debe ser discreto y lo suficientemente pequeño para realizar múltiples iteraciones en todos los estados. Este no es un problema para nuestros dos entornos de Frozen-Lake vistos hasta ahora, pero representa una importante limitación para poder aplicar Value Iteration a muchos problemas reales.

Otro problema práctico esencial surge del hecho de que para actualizar la ecuación de Bellman, el algoritmo requiere conocer la probabilidad de las transiciones y la recompensa por cada transición del entorno. ¿Podemos, en nuestro caso de estudio del entorno de Frozen-Lake, continuar utilizando el método Value Iteration si no tenemos acceso a la función de transición? Veremos que sí, y lo presentaremos no tanto por su posible aplicabilidad — ya que veremos que, a menudo, no es fácil poder estimar tan ajustadamente esta información — sino para volver a revisar una vez más conceptos fundamentales y facilitar la asimilación de estos conocimientos tan esenciales para poder avanzar en el estudio del aprendizaje por refuerzo.

A mitad de camino entre Model-Based y Model-Free

Recordemos que en nuestro ejemplo con el entorno de Frozen-Lake, el agente usa la estructura de datos «interna» env.env.P. Hacer esto es válido a efectos didácticos, para explicar el método Value Iteration, que como hemos dicho es fundamental porque forma parte del corpus de conocimientos del área de aprendizaje por refuerzo. Pero en un paradigma model-free, que es la forma más habitual de modelizar los entornos reales, no tenemos acceso a esta información. En este caso, el agente observa el estado, decide una acción y solo entonces obtiene la siguiente observación y recompensa por la transición, pero no conoce esta información de antemano.

Afortunadamente, en determinados tipos de escenario podemos disponer de la historia de la interacción del agente con el entorno y, a partir de esta historia, se puede calcular una estimación de las recompensas y transiciones. Veamos a continuación cómo podemos hacerlo en nuestro ejemplo de entorno Frozen-Lake.

Estimar recompensas es la parte más fácil, ya que las recompensas se pueden usar tal como están. Necesitamos recordar qué recompensa obtuvimos en la transición de s a s’ utilizando la acción a. Aunque en este caso del entorno de Frozen-Lake no es relevante, ya que solo tenemos una recompensa al final del episodio. Pero lo codificaremos igualmente de esta manera para mostrar cómo hacerlo y mantener el código lo más general posible para que pueda ser usado para otros problemas.

También puede resultar fácil estimar las transiciones; por ejemplo, manteniendo contadores para cada tupla en la experiencia del agente, (s,a,r’,s’), y normalizando estos contadores posteriormente. Por ejemplo, podemos crear una tabla simple que mantenga los contadores de las transiciones experimentadas. La clave de esta tabla puede ser compuesta por «estado+acción», (s,a), y los valores de cada entrada son la información sobre los estados de destino, s’, y un contador, c, que nos indica las veces que hemos llegado a cada uno de los estados destino.

Veamos un ejemplo concreto para explicarlo más fácilmente. Imaginemos que, durante la experiencia del agente, en un estado dado so ha ejecutado una acción a varias veces y termina c1 veces en el estado s1 y c2 veces en el estado s2. La cantidad de veces que hemos cambiado a cada uno de estos estados se almacena en nuestra tabla de transiciones experimentadas. Es decir, la entrada (s0, a) de la tabla contiene la información {s1:c1, s2:c2}.

Una vez tenemos esta información, es fácil usar esta tabla para estimar las probabilidades de nuestras transiciones. La probabilidad de que la acción anos lleve del estado s0 al estado s1 es c1/(c1+ c2) y la probabilidad de que la acción nos lleve del estado s0 al estado s2 es c2/(c1+ c2). Por ejemplo, imaginemos que desde un estado s0 el agente realiza la acción a diez veces. De ellas, 4 veces lleva el entorno al estado s1, y 6 veces al estado s2. Para este ejemplo en particular, la entrada en la tabla correspondiente a (s0, a) contendría {s1:4,s2:6}. Y de esta información se deriva que la probabilidad de transición del estado s0 al estado s1 es 4/10, es decir, 0.4, y la del estado s0 al estado s2 es 6/10, es decir, 0.6.

En el momento en que el agente dispone de estas estimaciones — en la siguiente sección veremos cómo lo consigue — , ya puede aplicar el algoritmo de Value Iteration para aprender la política a seguir para resolver el problema.

Implementación de un agente que usa estimaciones

A continuación, presentaremos el código adicional requerido, en relación con el ejemplo programado en la sección anterior, para implementar la versión de agente basada en la estimación de la función de transición y la recompensa.

Las principales estructuras de datos adicionales creadas en el constructor de la nueva clase Agent que mantendrán la información del agente son:

  • rewards: un diccionario con la clave compuesta por «source state + action + target state». El valor se obtiene de la recompensa inmediata.
  • transits: una tabla a modo de diccionario que mantiene contadores de las transiciones experimentadas. La clave de acceso está compuesta por «state + action», y el valor es otro diccionario que mapea el estado de destino en un recuento de veces que lo hemos visto.
  • V: este diccionario que mapea el estado a un valor calculado de la función V es el mismo diccionario que el del código del ejemplo anterior.
  • state: estado en que se encuentra el agente en este momento.

Ahora el entorno env, que se crea dentro del constructor de la clase Agent, será usado también para obtener estas muestras de experiencias a partir de las que sacaremos las estimaciones de las recompensas y la función de transición. Para implementar esta versión de la clase Agent importaremos también el paquete collections, que usaremos para las tablas de rewards y transitsque hemos descrito.

En resumen, el código del constructor de la clase Agent ahora será:

La lógica general de nuestro algoritmo de entrenamiento es equivalente al algoritmo anterior. Hasta que no se alcance el objetivo de recompensa deseado, ejecutaremos el mismo bucle anterior, excepto que antes de ejecutar el método de Value Iteration, el agente debe realizar unas cuantas interacciones entre el agente y el entorno para rellenar las estructuras de datos rewards y transits, con las que estimará las recompensas y la función de transición. Esto se realizará en el método play_n_random_steps(), que reproduce N time steps de interacción con el entorno, rellenando las tablas de reward y transits con experiencias aleatorias. A continuación, se detalla el código de esta función que se ha incluido como un método más del agente:

Podemos ver en el código que no necesitamos esperar al final del episodio para comenzar a aprender; simplemente realizamos N pasos y recordamos sus resultados. Esta es una de las diferencias entre métodos de aprendizaje, como veremos en otros capítulos, ya que algunos requieren episodios completos para aprender.

El método calc_action_value() en esta implementación del agente se diferencia bastante de la implementación del agente en la sección anterior, ya que no puede obtener el valor Q como antes, sino que ahora calcula el valor de una acción a partir de los datos de las tablas de transits, rewarddel agente. A continuación, se muestra el código que lo implementa:

En este código, primero, de la tabla de transits, extraemos los contadores de transición para el estado y la acción que el método recibe como argumentos. Sumamos todos los contadores para obtener el recuento total de veces que hemos ejecutado la acción del estado. Luego, iteramos por cada estado destino en el que ha llegado el agente por esta acción y se calcula su contribución al valor total. A partir de aquí se calcula la probabilidad (contador individual dividido por el contador total), que es la estimación a la función de transición que usaremos en la ecuación de Bellman. Destacamos en negrita esta línea del código para que vea la equivalencia con la implementación en el agente anterior. Este valor es igual a la recompensa inmediata más el valor descontado para el estado destino y multiplica esta suma por la probabilidad de esta transición. Agregamos el resultado de cada iteración a una variable action_value, la variable que se devolverá.

Para seleccionar la mejor acción de un estado dado, tenemos el mismo método select_action() que en la implementación del agente anterior, pero ahora se usa el nuevo método calc_action_value() que acabamos de describir para tomar la decisión.

Y aquí llegamos al método principal, el método Value Iteration, con la misma implementación que en el anterior agente, pero en este caso antes de iterar debe llamar al método self.play_n_random_steps()para poder actualizar los datos de las tablas del agente antes de aplicar una nueva iteración del método Value Iteration:

Evaluación del agente que usa estimaciones

Puede practicar con el código completo en GitHub listo para ser ejecutado en Colab. Debido a la estocasticidad del entorno, para diferentes ejecuciones obtendremos diferentes comportamientos. Pero como puede ver en la Figura 4.9, obtenida de una ejecución de ambas implementaciones de los agentes para el entorno de Frozen-Lake, es importante resaltar que el nuevo agente puede aprender a partir de las estimaciones.

Figura 4.9 Comparativa del comportamiento del aprendizaje de las dos implementaciones de agente, la primera con acceso a la función de transición del entorno de Frozen-Lake (que acaba antes) y la segunda que estima la función de transición a partir de interacciones de prueba.

Aunque los resultados que se muestran en el gráfico de la Figura 4.9 son dos ejecuciones concretas y sabemos que, dada la estocasticidad del entorno, estas pueden variar mucho, estos los consideraremos como representativos para explicar la diferencia en general del comportamiento en el aprendizaje entre ambas implementaciones.

Por un lado, podemos ver que la versión de agente basado en estimaciones requiere más time steps para aprender el mismo umbral de recompensas. Otra característica que nos encontramos en general, y que se observa en esta ejecución en concreto, es que a la versión basada en estimaciones al principio le cuesta más encontrar unos valores para V — los valores de estado — a partir de los cuales poder aprender.

Como ya hemos mostrado que usar el entorno FrozenLake8x8-v0 más grande consistía simplemente en cambiar una sola línea de código, hemos reproducido la Figura 4.9 con este nuevo entorno, como se muestra en la Figura 4.10. En este caso se ven más acrecentadas las dos cuestiones que apuntábamos en el anterior párrafo: requerir más time steps y, a su vez, tardar más en encontrar unos valores iniciales de la función de valor V para poder empezar a aprender. De todas maneras, debemos insistir en que estamos ante un entorno estocástico y que en ambos casos pueden variar los gráficos entre diferentes ejecuciones del mismo algoritmo. Pero sí que, en general, la política obtenida será la misma. Es decir, tardaremos más o menos, pero llegaremos a la solución deseada.

Figura 4.10 Reproducción de la Figura 4.9 para el entorno Frozen-Lake8x8-v0 con la comparativa del comportamiento del aprendizaje de las dos implementaciones de agente, la primera con acceso a la función de transición del entorno de Frozen-Lake (que acaba mucho antes) y la segunda que estima la función de transición a partir de interacciones de prueba.

Antes de avanzar al siguiente capítulo, le proponemos experimentar un poco con estos códigos en Colab para familiarizarse con ellos. Proponemos que, además de cambiar el tamaño del entorno en ENV_NAME, experimente con diferentes valores de los hiperparámetros, como son GAMMA, TEST_EPISODE, REWARD_GOAL o N.

Recuerde que poner los conocimientos en práctica es la mejor manera de ir asentándolos.

Calcular directamente la función Q

Hemos llegado al final del capítulo en el que hemos mostrado diferentes aspectos y usos del método Value Iteration para que se pueda familiarizar y adquirir una buena base de los conceptos fundamentales del aprendizaje por refuerzo y, de esta manera, pueda avanzar con comodidad en los próximos capítulos.

Hay aspectos que no hemos considerado, como por ejemplo cómo usar el método de Value Iteration para aprender los valores de las acciones en lugar de los valores de los estados, como hemos hecho en este capítulo. En realidad el método no difiere significativamente; simplemente, en vez de mantener una tabla V con los valores estimados de los estados, el agente debe mantener una tabla Q con los valores de los pares estado-acción. En consecuencia, en esta implementación el método calc_action_value() ya no haría falta puesto que los valores ya están almacenados.

Pero hemos considerado que, para el propósito de este libro, no hace falta tratar todas las posibles versiones del método y que con lo explicado cubrimos los objetivos de revisar los fundamentos básicos para iniciarnos con comodidad en los métodos de Monte Carlo en el siguiente capítulo.

REFERENCIAS DEL CAPÍTULO:

[1] Véase https://es.wikipedia.org/wiki/Sucesión_de_Fibonacci. [Consultado: 16/01/2021].

[2] En los libros clásicos de RL se presenta el algoritmo Value Iteration como un método para buscar la política óptima a través de encontrar las funciones de valor óptimas, y centran su explicación en la optimalidad. En este libro, sin querer quitar valor a este aspecto del método — que lo tiene — , hemos considerado más conveniente introducir este algoritmo solo para aprender el valor de los estados, reforzando de esta manera el relato global que guía el contenido de este libro, para ir introduciendo los conceptos y los algoritmos fundamentales de forma gradual y práctica, facilitando así el aprendizaje ordenado de todos y cada uno de los conocimientos fundamentales de RL.

[3] Richard S. Sutton and Andrew G. Barto, (2018). Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, Section 4.4 Value Iteration.http://www.incompleteideas.net/book/first/ebook/node44.html

[4] Williams RJ, Baird III LC; (1993). Analysis of some incremental variants of policy iteration: first steps toward understanding actor-critic learning systems. Technical Report. NU-CCS-93–11. Northeastern University, College of Computer Science. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.5377&rep=rep1&type=pdf

[5] Véase https://www.tensorflow.org/tensorboard [Consultado: 16/01/2021].

[6] Véase https://www.tensorflow.org [Consultado: 16/01/2021].

[7] Véase https://matplotlib.org [Consultado: 16/01/2021].

[8] Véase https://pytorch.org [Consultado: 16/01/2021].

[9] Se ha considerado PyTorch pero se podría haber usado TersorFlow; ambos middleware son actualmente suficientemente populares y robustos.

[10] Véase https://pytorch.org/tutorials/intermediate/tensorboard_tutorial.html[Consultado: 16/01/2021].