Capítulo 5. Evaluación de políticas con Monte Carlo

Otro de los métodos clásicos de aprendizaje por refuerzo es el método Monte Carlo, que permite una solución aproximada al aprendizaje basada en el muestreo estadístico a partir de la experiencia. A diferencia de la programación dinámica, este método se puede aplicar a entornos cuya dinámica no conocemos.

En este capítulo presentaremos una aproximación Monte Carlo tanto para estimar funciones de valor como para descubrir políticas óptimas. Se mostrarán sus implementaciones en Python usando el entorno blackjack de la librería Gym.

5.1 Métodos Monte Carlo

Monte Carlo versus programación dinámica

En el capítulo anterior presentamos una solución para un MDP llamada «programación dinámica basada en la ecuación de Bellman». Recuerde que la ecuación de Bellman nos permite definir una función de valor de forma recursiva y se puede resolver con el algoritmo Value Iteration.

Este método recorre todos los estados en cada iteración y, por ello, no es una opción para el aprendizaje cuando el espacio de estado es muy grande o infinito. Además —y muy importante—, la programación dinámica es un método model-based que requiere el conocimiento de la probabilidad de transición de estado P(s’|s,a).

Para poder superar estas limitaciones, tenemos los métodos Monte Carlo, que se basan en el aprendizaje a partir solo de la experiencia y pueden aplicarse en los entornos cuya dinámica no conocemos; es decir, se trata de métodos model-free. Aunque se requiere un modelo, este solo necesita generar transiciones de muestra (en lugar de las distribuciones de probabilidad completas de todas las posibles transiciones que se requieren para la programación dinámica).

Los métodos Monte Carlo son formas de resolver el problema del aprendizaje por refuerzo basadas en promediar los retornos de la muestra. Para asegurarnos de que los retornos estén disponibles, en este libro solo consideraremos usar Monte Carlo para tareas episódicas. Es decir, asumimos que la experiencia se divide en episodios y que todos los episodios terminan finalmente sin importar qué acciones se seleccionen. Y solo al final de un episodio se obtienen los retornos con los que se realizan las estimaciones de las funciones de valor.

Por tanto, las funciones de valor V y Q se pueden aproximar por medio de muestras. En otras palabras, todo lo que tenemos que hacer es reproducir una serie de episodios, recopilar sus retornos y promediarlos. Podemos ver los métodos Monte Carlo como técnicas estadísticas usadas para encontrar una solución aproximada a través de muestreo estadístico.

Es decir, los métodos Monte Carlo aproximan la esperanza matemática de una variable aleatoria mediante muestreo, de manera que cuanto mayor sea el tamaño de la muestra, mejor será la aproximación. En la sección 3.1 hemos presentado la esperanza matemática de una variable aleatoria X, 𝔼(X), como la suma de la probabilidad de cada posible suceso aleatorio multiplicado por el valor de dicho suceso. Representa la cantidad promedio que se «espera» como resultado de un experimento aleatorio que se repite muchas veces:

Pero en lugar de calcular el valor de una variable X de esta manera, los métodos Monte Carlos lo obtienen muestreando los valores de X para un conjunto N de veces y calculan el valor promedio de X, es decir, la media aritmética, puesto que es una variable cuyos valores aparecen todos con la misma probabilidad 1/N:

Cuanto mayor sea el valor de N, mejor será la aproximación de la variable X.

Estamos hablando en plural porque la aproximación Monte Carlo es muy útil y se aplica a varios cometidos. Pero, aunque permite tratar problemas model-free —a diferencia de la técnica de programación dinámica—, tiene la limitación de que solo se puede aplicar a tareas episódicas, como ya hemos comentado, donde la interacción se detiene cuando el agente encuentra un estado terminal.

Otra característica de los métodos Monte Carlo que se debe tener en cuenta es que solo nos dan un valor para los estados y acciones que el agente ha encontrado; por ello, si un estado o una acción nunca se han visitado en los episodios, se desconocerá su valor.

Tareas de predicción y control

Continuando con la estrategia de ir introduciendo gradualmente conceptos a lo largo del libro, ha llegado el momento de explicar que en aprendizaje por refuerzo distinguimos dos tipos de tareas: la tarea de predicción y la tarea de control.

Vamos a presentar ambos tipos de tareas en base al método Monte Carlo, pero también se pueden conseguir con métodos basados en programación dinámica —aunque no lo hayamos considerado en el capítulo anterior para poder mantener un relato más didáctico—.

Cuando usamos un método de aprendizaje para aprender funciones de valor dada una política, decimos que se trata de una tarea de predicción. En este caso, se da una política 𝜋 como entrada al algoritmo y este trata de calcular la función de valor V o Q utilizando la política dada. En esta tarea de predicción el objetivo es evaluar la política dada.

A diferencia de la tarea de predicción, en la tarea de control el algoritmo que se usará no recibirá ninguna política como entrada; precisamente el objetivo es encontrar la política óptima, que maximice el retorno. Para ello, el algoritmo comenzará inicializando una política aleatoria e intentará encontrar la política óptima de forma iterativa.

Debemos tener en cuenta que, en la tarea de predicción, en ningún momento se realiza un cambio en la política de entrada dada, que se mantiene como fija y es usada para calcular los valores V y Q a lo largo de las iteraciones del algoritmo. En cambio, en la tarea de control, la política va cambiando a medida que va iterando el algoritmo —y, con ello, la política con la que se calculan los valores V y Q en el algoritmo—.

En este capítulo presentaremos cómo utilizar el método Monte Carlo para realizar la tarea de predicción, y en el capítulo 6 se presentará cómo utilizar el método para realizar la tarea de control.

First-visit versus Every-visit

Hemos avanzado que, en la tarea de predicción, el algoritmo recibe una política y con ella calcula la función V o la función Q. Para estimar una función de valor, el algoritmo de predicción Monte Carlo recopila suficientes episodios (interacciones del agente con el entorno con la política dada) con los que calcula las estimaciones de los valores V o Q.

Puede suceder que en un episodio se visite el mismo estado más de una vez. O que desde un mismo estado se tome la misma acción, es decir, que se suceda un par estado-acción más de una vez en un mismo episodio. Esto nos lleva a tener dos versiones o categorías de algoritmo de predicción Monte Carlo: First-visit y Every-visit.

En el caso del método de predicción Monte Carlo First-visit, si el mismo estado (para el caso de la función V) o el mismo par estado-acción (para el caso de la función Q) se visita nuevamente en el mismo episodio, no se usa esa información para calcular el retorno. En cambio, el método de predicción Monte Carlo Every-visit es justo lo opuesto; en este caso se calcula el retorno para cada visita del estado o par estado-acción y se promedia los retornos calculados a partir de todas las visitas.

Estos dos métodos, Monte Carlo First-visit y Monte Carlo Every-visit,garantizan la convergencia a la verdadera función de valor. Pero, aunque son muy similares, tienen propiedades teóricas ligeramente diferentes que quedan fuera del ámbito de este libro (si se requiere más detalle, se puede consultar el libro de R. Sutton y A. Barto).

5.2 Algoritmo de predicción Monte Carlo

Visión global

Comenzamos considerando Monte Carlo para aprender la función de valor de estado para una política dada. Recordemos que el valor de un estado es el retorno esperado (suma de todas las recompensas futuras con descuento) a partir de ese estado. Entonces, una forma obvia de estimarlo a partir de la experiencia es, simplemente, promediar los retornos observados después de las visitas a ese estado. A medida que se observan más retornos, el promedio debería converger al valor esperado. Esta idea es la base de todos los métodos basados en Monte Carlo.

Pseudocódigo

El algoritmo de predicción Monte Carlo para calcular la función de valor de estado, en su versión First-visit, se estructura como se muestra en el pseudocódigo 5.1.

El algoritmo descrito recibe la política 𝜋 y el número de episodios que se deben generar (num_episodes) para calcular las estimaciones de los retornos. También recibe el factor de descuento para calcular el retorno a partir de las recompensas retardadas.

Con la tabla return_sum(s) se mantendrá la suma de los retornos de un estado que se ha obtenido en varios episodios. Con la tabla N(s) se mantiene un contador del número de veces que se ha visitado un estado dado. Ambas estructuras de datos se inicializan a cero para todos los estados.

A continuación, el algoritmo genera los episodios siguiendo la política recibida. Para cada episodio generado, el algoritmo itera; y para cada time step del episodio, se comprueba si es la primera vez que se visita un estado en este episodio. La versión de pseudocódigo para el algoritmo Every-visites la misma, pero sin el condicional «if»; es decir, el bloque de código siguiente se ejecutará una vez o cada vez respectivamente.

En este bloque de código se calcula el retorno Gt del estado en el que se encuentra en ese time step t con el que actualiza la entrada correspondiente de la tabla return_sum sumando el nuevo retorno calculado. Al mismo tiempo, se actualiza el contador de visitas N(s) para ese estado. Finalmente, se actualiza la función de valor de estado para ese estado calculando el promedio de los retornos recibidos hasta aquel momento para el estado dado mediante la operación return_sum(St)/N(St).

Pseudocódigo 5.1 Algoritmo de predicción Monte Carlo First-visit para calcular la función V.

5.3 Métodos de predicción Monte Carlo para la función V

Para mostrar el funcionamiento de este algoritmo, en esta sección vamos a programar cómo se puede calcular el valor de los estados usando el método Monte Carlo para un ejemplo concreto de entorno estocástico, basado en el clásico juego del blackjack.

En el GitHub del libro se encuentra, en forma de notebook, el código que se presenta en este libro, cuya organización está pensada para facilitar el relato de explicaciones de este capítulo (más que en el código en sí mismo). Por ello, hemos decidido sacrificar el programar el agente como una clase, como en el capítulo anterior.

Caso de estudio: Blackjack

Un buen ejemplo para mostrar cómo funcionan los métodos Monte Carlo en la práctica es la programación paso a paso de un agente que es capaz de jugar al popular juego de cartas blackjack utilizando el entorno Blackjack-v0[1] que nos ofrece la librería Gym que ya conocemos.

En este ejemplo vamos a enseñar a un agente a jugar al juego de blackjack. El blackjack es un ejemplo perfecto de problema episódico en el que un jugador (agente) gana, pierde o empata el juego. En este entorno Blackjack-v0 el agente no sabe de antemano cómo reacciona el crupier (que queda incluido dentro del entorno) a sus acciones (plantarse o pedir otra carta).

Vamos a implementar la versión Every-visit para este ejemplo. Pero, en realidad, ambas versiones (First-visit y Every-visit) arrojan los mismos resultados en este ejemplo, puesto que el mismo estado nunca se repite dentro de un episodio.

Reglas del juego blackjack

El blackjack es un juego de cartas propio de los casinos con una o más barajas inglesas sin los comodines. El juego consiste en que el valor de las cartas que se tienen al plantarse un jugador sume lo más próximo a 21 pero sin pasarse. El entorno Blackjack-v0de la librería Gym nos permite crear un entorno que simula el juego, pero con algunas simplificaciones que describimos a continuación.

Una de las primeras simplificaciones es que, en este entorno, el agente que representa al jugador (player) jugará él solo contra el crupier (dealer). En este entorno, las cartas numéricas suman el valor que aparece en la carta (de 2 a 10); las cartas J, K y Q valen 10; y el As (Ace) vale tanto 1 como 11, a elección del jugador, según la necesidad de no pasarse de 21.

Al empezar, ambas partes —el jugador y el crupier— reciben dos cartas. Las dos cartas del jugador están boca arriba, mientras que solo una de las cartas del crupier está boca arriba; por tanto, el agente solo sabe el valor de una de las dos cartas del crupier.

Si el jugador obtiene unas cartas con valor de 21 (un As y una carta de 10), se llama blackjack o 21 natural. En este caso, el jugador ya ha ganado (a menos que el crupier también tenga un 21 natural, en cuyo caso el juego acaba como un empate). Si el jugador no tiene un 21 natural, puede pedir cartas adicionales, una a una (acción de pedir), hasta que se detenga (acción de plantarse) o supere los 21 puntos.

Si el valor de las cartas del agente ha superado los 21 puntos, el agente pierde. Pero si se ha plantado, entonces le toca el turno de juego al crupier. El crupier se planta o coge más cartas de acuerdo con su estrategia, que son unas reglas fijas incluidas en la dinámica del entorno. Al final, el crupier muestra sus cartas. Entre el jugador (agente) y el crupier (entorno), gana quien obtenga un 21 natural (As + 10), o quien tenga la puntuación más alta de sus cartas sin pasarse de 21. Si ambos obtienen la misma puntuación, se empata.

En resumen, este es un juego perfecto para explicar Monte Carlo, que ya usaron R. Sutton y A. Barto de ejemplo en su libro. El jugar al blackjack se puede formular como un MDP finito episódico. Cada juego de blackjack es un episodio. Se otorgan recompensas de +1, -1 y 0 por ganar, perder y empatar, respectivamente. Todas las recompensas dentro de un juego son cero y no descontamos (gamma = 1); por lo tanto, estas recompensas terminales también son los retornos.

Los estados se definen a partir de las cartas de que dispone el jugador y de la carta boca arriba del crupier. El jugador puede tomar decisiones sobre la base de tres variables: la suma actual de sus cartas, el valor de la carta que muestra el crupier y si tiene o no un As utilizable entre sus cartas.

Entorno blackjack de la librería Gym

Veamos cómo se representa toda esta información descrita en el anterior apartado en un estado de este entorno Blackjack-v0. Para verlo, fácilmente podemos empezar invocando el método reset() de nuestro entorno, para conocer cómo es un estado de los que devuelve el entorno blackjack:

Como vemos, el estado se representa como una tupla de tres elementos. Su interpretación es:

  • El primer elemento indica el valor de la suma de las cartas del agente. En este ejemplo vemos que las cartas que en estos momentos tiene el agente suman 8.
  • El segundo elemento muestra el valor de la carta del crupier que está boca arriba. En concreto en este ejemplo es un 6.
  • El tercer elemento indica si el agente tiene o no un As utilizable. En este caso, con el False nos indica que el agente no dispone de un As utilizable.

Una vez que el jugador sabe el valor de sus cartas y el valor de la carta del crupier boca arriba, debe realizar una acción. Podemos investigar cuál es el espacio de acciones de este entorno con:

Vemos que el entorno permite realizar dos acciones:

  • La acción 0 indica que el jugador se planta y no pide más cartas (stick).
  • La acción 1 indica que el jugador continúa jugando y pide otra carta al crupier (hit).

Cada partida o mano de blackjack es un episodio. La parte final de la partida, en la que se decide quién ha ganado o si se ha empatado (en base a la segunda carta del crupier —o en base a todas las que haya podido coger—), se realiza dentro de la dinámica del entorno y se comunica el resultado al agente con la última recompensa. Las recompensas al final de la partida pueden ser:

  • +1.0 si ha ganado el agente (winning).
  • -1.0 si ha perdido el agente (losing).
  • 0.0 si se ha empatado (drawing).

Todas las recompensas dentro de una partida son 0.0 y consideraremos gamma = 1, como ya hemos avanzado. Por lo tanto, las recompensas terminales también son los retornos.

A continuación, hemos implementado un código sencillo que nos permite visualizar un episodio entero, donde se observa la interacción del agente con el entorno en cada time step, asumiendo de momento que el jugador realiza acciones aleatorias. Hemos recurrido al método sample() que nos ofrece el entorno:

En este caso, el jugador ha empezado una partida en la que ha recibido dos cartas que suman 14, y no dispone de ningún As. Siguiendo la política aleatoria que guía al agente, este ha decidido pedir otra carta con la acción 1. Con ello, ha conseguido que sus cartas sumaran 24 y, por tanto, ya se ha pasado de 21 y ha perdido la partida. Podemos comprobar que la interacción con el entorno es exactamente la misma que con el entorno Frozen-Lake mediante el método step(), que nos retorna los mismos cuatro valores. Le propongo que ejecute varias veces esta celda de código del notebook para familiarizarse con el entorno blackjack-v0 de Gym.

Ahora que hemos descrito cómo está diseñado el entorno de blackjack en Gym, y cómo es la interacción entre entorno y agente, podemos pasar a implementar uno de los algoritmos de predicción Monte Carlo.

Bucle de aprendizaje

En este apartado vamos a presentar un código que implementa el método de predicción Monte Carlo en su versión Every-visit, para estimar la función de valor de estado.

Para empezar, consideremos una política simple en la que el agente decide una acción basándose únicamente en su puntuación actual. Por ejemplo, imaginemos un jugador nuevo en el juego que decide que hasta que no llegue a 19 puntos no se planta. Podemos modelizar este jugador con un agente que aplique la siguiente política determinista:

Para generar episodios podemos hacerlo con la función generate_episode(), que permite obtener un episodio del juego con la política descrita:

Este código, que usaremos después en nuestro algoritmo de aprendizaje, devuelve una lista de tuplas con la secuencia de tuplas (estado, acción, recompensa) que componen un episodio. Es decir, episode[t][0], episode[t][1] y episode[t][2]corresponden al estado del time step t, la acción en el time step t y la recompensa en el time step t+1, respectivamente.

Por ejemplo, si queremos ver cómo el agente juega 10 partidas siguiendo esta política, lo podremos mostrar con las siguientes dos líneas de código que invocan a la función anterior:

Comencemos a programar un código guiados por el pseudocódigo 5.1. Primero, necesitamos inicializar los diccionarios N, return_sum y V. V es el diccionario donde V[s] es la estimación del valor del estado s. Por ejemplo, si una entrada V contiene:

significa que para el estado (4,7,False) su valor se estima en -0.38715.

Los diccionarios son una buena forma de almacenar datos y se accede a ellos por una clave. Pero, dado el tipo de claves que son los estados de nuestro ejemplo —en este caso tuplas—, usaremos defaultdict de Python, que funciona exactamente como un diccionario normal, pero se inicializa con una función que no tiene argumentos y proporciona el valor predeterminado para una clave inexistente. De esta manera, un defaultdict nunca generará un KeyErr. Para cualquier clave que no exista, se obtiene el valor predeterminado.

A continuación, mediante un bucle, el algoritmo recorre los num_episodes generados con la función generate_episode() que utiliza la política policy(). Recordemos que esta función nos retorna una lista de tuplas y, por ello, usaremos el comando zip para separar los elementos de la tupla en estados, acciones y recompensas:

Seguidamente, el algoritmo recorre los estados que aparecen en un episodio y actualiza las entradas correspondientes a estos estados en los diccionarios N, V y return_sum. Concretamente, se incrementa el valor correspondiente del diccionario N en +1y se agrega el retorno calculado en este time step en la entrada correspondiente del diccionario return_sum. A partir de aquí, usaremos estos diccionarios para actualizar el diccionario V que mantiene el valor estimado hasta el momento para cada uno de los estados hasta ahora visitados por el agente. A continuación, se muestra el código que realiza lo que acabamos de describir:

Mostramos también una visión global del código completo del método de predicción Monte Carlo expuesto en esta sección, que hemos agrupado en forma de función:

Ahora podemos invocar a esta función para aprender la función de valor de estado V. La función que hemos implementado, además de recibir como argumento el número de episodios, la política y el factor de descuento, también recibe el entorno y la función de generación de los episodios. Según se indica en el libro de R. Sutton y A. Barto, después de 500 000 episodios la función de valor está muy bien aproximada; por ello, hemos elegido este número de episodios:

Recordemos que en esta sección hemos mostrado el código para la versión de Every-Visit del método de predicción Monte Carlo. Para adaptarlo a la versión de First-Visit, simplemente hace falta añadir a la función anterior una línea de código que garantice que las actualizaciones de N, V y return_sum solo se realizan la primera vez que aparece el estado en el episodio. Para ello, solo hace falta añadir la siguiente línea de código donde indica el pseudocódigo 5.1, e indentar las 3 siguientes líneas de código:

Análisis de resultados

Para analizar el valor de los estados calculados por el código presentado, resulta muy útil poder visualizar estos estados de una forma gráfica, como ofrece el libro de R. Sutton y A. Barto. Para ello, hemos usado un código que quienes deseen inspeccionar encontrarán incluido en el código de este ejemplo que se encuentra en el GitHub del libro, basado en un código del GitHub de Udacity[2].

El resultado se muestra en la Figura 5.1, que presenta dos gráficos: el primero corresponde a los estados en los que se dispone de un As utilizable, y el segundo corresponde a los estados en los que no se dispone de un As utilizable. De esta manera, se puede representar un espacio 4D en dos de 3D. Cada uno de estos dos gráficos tiene tres ejes, y el eje el vertical es el que indica el valor del estado definido por el valor de las cartas del jugador y la carta boca arriba del crupier. La escala de color en el notebook(o escala de grises en la versión en blanco y negro del libro) debería facilitar la interpretación del valor correspondiente en el eje vertical de los puntos de la superficie.

Figura 5.1 Gráficos correspondientes a la visualización de la función de valor de los estados en el entorno Black-Jack-v0 siguiendo la política de pedir carta al crupier mientras la suma de las cartas sea inferior o igual a 19.

En este caso concreto, se representa el valor de los estados en el entorno Black-Jack-v0 cuando el agente usa la política determinista de seguir pidiendo carta al crupier mientras la suma del valor de las cartas sea inferior o igual a 19.

Sin entrar en los detalles de cada punto de las superficies que representan los aproximadamente 200 estados de este entorno en los gráficos, podemos extraer algunas conclusiones. Por ejemplo, a simple vista se observa que los estados con un As utilizable tienen más valor que sus estados homólogos sin el As.

En los gráficos se observa claramente que lo más relevante de esta política es que solo los estados en los que la suma del valor de las cartas es 20 o 21 disponen de un valor alto. Es decir, cuando la suma de nuestras cartas es 20 o 21, decidimos no pedir más cartas y, sin duda, tenemos posibilidades de ganar la partida.

También resulta lógico el valor de los estados en los que las cartas del jugador no suman más de 19 (y, por tanto, según la política el agente continúa pidiendo cartas), debido a que la probabilidad de pasarse de 21 es muy alta. Por ejemplo, donde observamos el valor más bajo de los estados es en los estados donde las cartas del jugador suman 19 y no tenemos un As. Si lo analizamos, podemos concluir que, independientemente de las cartas del crupier, tenemos un valor de estado muy bajo debido a que es muy probable que nos pasemos de 21 al coger una nueva carta; solo recibiendo un As o un 2 nos salvaríamos.

Aunque para mostrar cómo funciona el algoritmo de predicción Monte Carlo este ejemplo nos ha sido igualmente útil, propongo un ejemplo de jugador más «sensato» y más «conservador». Este jugador, en general (aunque dependerá un poco de la partida), piensa que debe pedir otra carta si la suma del valor de las cartas que tiene es 15 o menos; y considera que es demasiado peligroso aceptar una nueva carta.

Podemos modelizar este jugador con un agente que aplique una política estocástica que realice la acción de pedir otra carta si la suma de las que tiene es 15 o menos y que lo haga en un 90 % de las veces. Y, si la suma de las cartas es mayor que 15, que realice la acción de plantarse en un 90 % de las veces. Podemos expresar la política con la siguiente función:

La visualización del valor de los estados para este jugador se muestra en la Figura 5.2. Analizando visualmente este gráfico, se percibe rápidamente que cuanto más valor tiene la suma de las cartas del jugador, más valor tiene el estado, siendo el máximo cuando los estados comparten la suma de 21, puesto que es más probable que ganemos el juego en estos estados que en cualquier otro.

En estos mismos gráficos, podemos observar otros detalles. Por ejemplo, que cuando la carta del crupier boca arriba tiene el valor 1, vemos que siempre baja el valor de los estados. Esto es así porque el crupier dispone de un As, lo cual aumenta sus posibilidades de ganar (al poder canjearlo).

Otro detalle es que el valle intermedio en la superficie nos indica que la suma de los puntos de las cartas del jugador está en una zona donde no coger otra carta implica no sumar más puntos que el crupier pero, a su vez, si cogemos otra carta tenemos posibilidades de pasarnos de 21.

Para obtener diferentes vistas de la superficie, se puede cambiar el ángulo de visión de los gráficos simplemente modificando el argumento de la función ax.view.init() del código entre -90 y -180. Animo a quienes quieran analizar en más detalle las superficies de los gráficos y a que jueguen con este parámetro.

Pero de este primer análisis superficial de los resultados de estas dos políticas, nos viene la siguiente pregunta: ¿Cuál es la mejor política? Seguramente alguna que usa el resto de información de que disponemos, pero ¿cuál? Esto es precisamente lo que descubriremos en el siguiente capítulo, usando el método de control Monte Carlo ya mencionado. Pero, para ello, necesitamos calcular la función de valor Q. Veamos cómo podemos calcular la función de estado de los pares estado-acción con el método de predicción Monte Carlo.

Figura 5.2 Gráficos correspondientes a la visualización de la función de valor de los estados en el entorno Black-Jack-v0 siguiendo la política estocástica.

5.4 Métodos de predicción Monte Carlo para la función Q

Si el modelo de un entorno no está disponible, resulta particularmente útil, para encontrar una política, estimar los valores Q de los pares estado-acción. Los algoritmos Monte Carlo para esta tarea son esencialmente los mismos que los presentados para obtener valores de estado, excepto que ahora hablamos de visitas a un par estado-acción —en lugar de a un estado—. Se dice que un par estado-acción (s,a) se visita en un episodio si alguna vez se visita el estado s y se realiza la acción a desde ese estado. Veamos cómo se puede adaptar el anterior algoritmo Monte Carlo, que calcula el valor de los estados, para calcular los valores de los pares estado-acción.

Algoritmo

El algoritmo de predicción Monte Carlo First-visit para calcular la función Q se muestra en el pseudocódigo 5.2.

Pseudocódigo 5.2 Algoritmo de predicción Monte Carlo First-visit para calcular la función Q.

Si comparamos los pseudocódigos 5.1 y 5.2, podemos constatar que ambos tienen la misma estructura y que difieren básicamente en la estructura de datos (en el pseudocódigo 5.2 se almacenan los valores Q en vez de los valores V). Los valores V se mantienen en una tabla que tiene una fila para cada estado, mientras que los valores Q se mantienen en una tabla Q, que tiene una fila para cada estado y una columna para cada acción. Para aproximar un elemento de esta tabla Q, Q(s,a), se usa el retorno que se consiguió cuando el agente estaba en ese estado y eligió esa acción. Los pseudocódigos también difieren en las tablas N y return_sum, que pasan a tener dos dimensiones para almacenar la información para cada par estado-acción. Pero el resto de pseudocódigo se mantiene exactamente igual.

Bucle principal de aprendizaje

Veamos ahora cómo se implementa el algoritmo de predicción Monte Carlo Every-visit para calcular la función Q. Para ello, usaremos las mismas funciones auxiliares anteriores: policy() o generate_episode(). El código del algoritmo es equivalente al anterior pero, ahora, en vez de tener un diccionario V para guardar los valores de los estados, tendremos un diccionario Q para guardar los valores de los pares estado-acción. El código es el siguiente:

Como ya hemos indicado, en esta sección hemos mostrado el código para la versión de Every-visit MC method. Igual que presentamos en el caso de la estimación de la función V, la versión del método Monte Carlo First-visitsimplemente require añadir a la función anterior una línea de código que garantice que las actualizaciones de N, Q y return_sum solo se realizan la primera vez que aparece un determinado par estado-acción en el episodio. Para ello, solo hace falta añadir la siguiente línea de código e indentar las tres siguientes:

Una vez definida esta función, ya podemos invocarla para aprender la función Q con los mismos argumentos que usamos para aprender la función V de la sección anterior.

Análisis de resultados

Será interesante visualizar los valores de la función Q o su equivalente, el valor de los estados en función de esta función Q, y así poder comprobar que hemos aprendido lo mismo. Podemos obtener el valor del estado a partir del valor de los pares estado-acción, basándonos en esta fórmula presentada en el capítulo 3:

El siguiente código obtiene el valor del estado ponderando el valor de cada acción según la política estocástica que hemos usado:

Ahora ya podemos usar el mismo código de visualización de la función V de la sección anterior. El resultado se muestra en la Figura 5.3. Podemos ver que el resultado es aproximadamente (dada la estocasticidad del entorno) el mismo al de la Figura 5.2, que es lo que esperábamos.

Limitaciones del método

Una de las limitaciones de esta aproximación de calcular la función Q a partir del método de predicción Monte Carlo es que es posible que nunca se visiten algunos pares de estado-acción. Por ejemplo, si la política es determinista —como la primera política presentada en este capítulo—, para calcular la función V solo se dispone del cálculo de los retornos para una de las acciones de las que se realizan desde un estado, pero no de las otras acciones.

Sin retornos para promediar de algunas acciones, las estimaciones de Monte Carlo de estas acciones no las podremos conseguir. Este es un problema importante, puesto que el propósito de aprender la función Q en la tarea de control —que veremos en la siguiente sección— es ayudar a crear una política que elija la mejor acción de las disponibles en cada estado. Y para comparar alternativas, necesitamos tener estimado el valor de todas y cada una de las acciones de cada estado. Sin embargo, no tenemos forma de saber la estimación del valor de aquellas acciones que no hemos visitado. Esto es lo que conocemos como el problema de «mantener la exploración», que trataremos ampliamente en el siguiente capítulo.

Figura 5.3 Gráficos correspondientes a la visualización de la función de valor de los estados obtenidos a partir de la función Q en el entorno Black-Jack-v0 para la política estocástica.