Capítulo 6. Obtención de políticas óptimas

En el anterior capítulo hemos aprendido cómo un agente puede seguir una política para interactuar con el entorno durante muchos episodios y, luego, usar los resultados de esta interacción para estimar la función de valor de los pares estado-acción, es decir, la función Q. Ahora la pregunta es: ¿cómo podemos usar esta función Q en la búsqueda de una política óptima?

En este capítulo mostraremos cómo se puede obtener una política óptima usando el método Monte Carlo, solucionando así el problema de «exploración» al disponer de la estimación del valor de todos los pares estado-acción. Se implementará un algoritmo para encontrar la política óptima en el entorno blackjack descrito en el anterior capítulo.

Acabaremos el capítulo mostrando mejoras del método, que permiten aprender sin tener que esperar hasta el final de un episodio para obtener el retorno real antes de poder actualizar y realizar mejoras en la estimación de la función de valor con el aprendizaje por diferencia temporal. Se presentarán dos métodos concretos de este tipo de aprendizaje, SARSA y Q-Learning.

6.1 Dilema exploración-explotación

Exploración versus explotación

Uno de los desafíos que surgen en el aprendizaje por refuerzo, y no en otros tipos de aprendizaje, es el compromiso entre exploración y explotaciónde las acciones que toma un agente. Para obtener una gran recompensa, un agente de aprendizaje por refuerzo prefiere acciones que ha probado en el pasado y que sabe que son efectivas para obtener buenas recompensas.

Si el agente mantiene estimaciones de los valores de todas las acciones, en cualquier time step hay al menos una acción cuyo valor estimado es mayor. A estas las llamamos acciones greedy. Una estrategia greedy consiste en elegir siempre la acción con mayor retorno estimado. Cuando el agente selecciona una de estas acciones, decimos que el agente está explotando su conocimiento actual de los valores de las acciones.

Pero, paradójicamente, para descubrir potenciales mejores acciones, el agente tiene que probar acciones que no haya seleccionado anteriormente, y renunciar a elegir la mejor acción de entre las que conoce. En este caso decimos que el agente está explorando, porque esto le permite mejorar su estimación del valor de una acción no greedy.

Por tanto, parece razonable pensar que el agente tiene que explotar lo que ya ha experimentado para obtener buenas recompensas a sus acciones, pero también tiene que explorar para hacer mejores selecciones de acción en el futuro. El dilema exploración-explotación es la necesidad de equilibrar estos dos requisitos en competencia, donde un agente debe encontrar una forma de actuar de manera que aproveche al máximo su conocimiento actual (explotación) y, a su vez, consiga adquirir más conocimientos del entorno (exploración).

En el capítulo anterior vimos que una de las limitaciones de usar el método de predicción Monte Carlo para calcular la función Q es que es posible que algunos pares estado-acción nunca se visiten, impidiendo de esta manera tenerlos en cuenta en la tarea de control donde se buscará la política óptima. En la literatura nos referimos a este hecho como problema de «mantener la exploración» (maintaining exploration en inglés).

Una forma de solucionar este problema es especificando que los episodios comiencen en un par estado-acción y que cada par tenga una probabilidad distinta de cero de ser seleccionado como comienzo. Esto garantiza que todos los pares de estado-acción serán visitados un número infinito de veces en el límite de un número infinito de episodios. A esto lo llamamos «el supuesto de exploring starts». A veces es útil, pero no se puede confiar en él en general, particularmente cuando se aprende directamente de la interacción en un entorno real. En ese caso, es poco probable que las condiciones iniciales garanticen este inicio desde todos los posibles pares estado-acción.

El enfoque alternativo más común para asegurar que sean visitados todos los pares estado-acción es considerar políticas estocásticas con una probabilidad distinta de cero de selección para cualquiera de las acciones.

Una forma de conseguirlo es, en lugar de construir una política que siempre selecciona la acción greedy para obtener una buena explotación del conocimiento que tiene el agente, construir una política llamada épsilon-greedy. En esta política es más probable que se elija la acción greedy, pero con alguna probabilidad pequeña, pero distinta de cero, se elige una de las otras acciones en su lugar. En este caso, se utiliza un número positivo, llamado épsilon ϵ, que debe ser entre cero y uno, que nos determina qué proporción de elección de acciones se dedican a la exploración.

Definiremos que una política es ϵ-greedy con respecto a una estimación de función de valor Q si para cada estado con probabilidad 1−ϵ el agente selecciona la acción greedy, y con probabilidad ϵ el agente selecciona uniformemente una acción de forma aleatoria desde el conjunto de acciones disponibles (tanto la greedy como las no greedy). Entonces, cuanto más grande sea ϵ, más probable será que se elija una de las acciones no greedy.

Llevando a cabo esta manera de elegir las acciones, conseguimos una forma para equilibrar la explotación del conocimiento actual con la necesidad de adquirir conocimientos para lograr un mejor comportamiento futuro. Esta será la aproximación que utilizaremos en este capítulo para mostrar cómo podemos usar Monte Carlo para la tarea de control.

Monte Carlo para la tarea de control

En este apartado vamos a presentar una visión general de cómo es un algoritmo que realiza tareas de control basado en el método Monte Carlo. Básicamente, el algoritmo se compone de dos pasos que se irán repitiendo. Primero se buscará una estimación de la función Q a partir de la política actual y, a continuación, se construirá una nueva política épsilon-greedycon respecto a la función Q estimada.

La idea es que iterativamente se va calculando tanto una política aproximada como una función de valor Q aproximada. La función de valor Q, que se almacena en una estructura de datos en forma de tabla, se modifica repetidamente para aproximarse más a la función de valor de la política actual, y la política se mejora repetidamente con respecto a la función de valor actual. Estos dos tipos de cambios juntos hacen que tanto la política como la función de valor se acerquen a la optimalidad.

Por tanto, el agente alterna entre estos dos pasos una y otra vez obteniendo políticas cada vez mejores con la esperanza de que converjan en la política óptima:

  • Paso 1: usar la política π para generar episodios y estimar la tabla Q. Esencialmente es aplicar el algoritmo de predicción Monte Carlo del apartado 5.4.
  • Paso 2: actualizar la política siendo épsilon-greedy con respecto a la función Q como hemos descrito en el apartado anterior (indicado por ϵ-greedy(Q)).

Este algoritmo permite aproximarse a la política óptima, siempre que se ejecute durante el tiempo suficiente para permitir que converja asintóticamente en la función de valor verdadero.

A este algoritmo para estimar la política óptima lo llamamos método de control Monte Carlo; y nos referimos al Paso 1 como evaluación de la política y al Paso 2 como mejora de la política. Esquemáticamente, podríamos representarlo como se muestra en la Figura 6.1.

Figura 6.1 Esquema visual del método de control Monte Carlo, compuesto por el Paso 1 de evaluación de la política y el Paso 2 de mejora de la política.

Por lo tanto, utilizando esta nueva terminología, podemos resumir que el método de control Monte Carlo alterna entre el paso de evaluación de la política y el paso de mejora de la política para encontrar la política óptima, denotada por π∗. Esquemáticamente, se puede resumir el ciclo como se muestra en la Figura 6.2, donde la «E» sobre la flecha indica una evaluación completa de la política y la «I» indica una mejora completa de la política.

En la próxima sección presentamos una implementación del algoritmo de control Monte Carlo. Sin embargo, antes de avanzar, tratemos de responder a algunas preguntas que surgirán en el próximo apartado: ¿Cómo establecer el valor de épsilon al construir políticas greedy?, ¿cómo calcular las probabilidades de cada acción a partir de este valor de épsilon?

Figura 6.2 Ciclo del método de control Monte Carlo, que alterna entre el paso de evaluación de política indicado por la «E» (evaluation) y el paso de mejora de política indicado por la «I» (improvement) para encontrar la política óptima π∗.

Políticas épsilon-greedy

Una política épsilon-greedy como la que hemos presentado antes puede ser una solución para el dilema exploración-explotación; por ejemplo, implementando una modificación gradual del valor de épsilon al construir políticas épsilon-greedy. Tiene sentido que el agente comience su interacción con el entorno optando por la exploración en lugar de la explotación, y probando diversas estrategias para maximizar el retorno.

Teniendo esto en cuenta, la mejor política de partida es una política aleatoria equiprobable, en la que todas las posibles acciones de un estado tengan la misma probabilidad de ser elegidas. El establecimiento, al principio, de ϵ=1 produce una política que es equivalente a una política aleatoria equiprobable.

En etapas posteriores, tiene sentido fomentar la explotación sobre la exploración, donde la política se vuelve gradualmente más greedy con respecto a la estimación de la función de valor de acción. El caso extremo es establecer ϵ=0, lo cual produce una política totalmente greedy. Se ha demostrado que favorecer inicialmente la exploración e ir favoreciendo, gradualmente, la explotación ante la exploración es una buena estrategia.

En un apartado anterior hemos definido cómo es una política ϵ-greedy. Más formalmente, para construir una política π que sea ϵgreedy con respecto a la estimación de la función de valor Q, si la acción a en el estado smaximiza, Q(s,a), matemáticamente estableceremos la probabilidad de selección como

donde

indica el número de acciones que se pueden realizar en ese estado. A las acciones no greedy, se les asigna la mínima probabilidad de selección:

Se incluye un término adicional

para la acción greedy porque la suma de todas las probabilidades debe ser 1. Tenga en cuenta que si sumamos las probabilidades de realizar todas las acciones no óptimas obtendremos

, y sumando esto a

, que corresponde a la probabilidad de la acción greedy, la suma dará uno.

Hiperparámetro decay rate

Para garantizar que el método de control Monte Carlo converja en la política óptima π∗, debemos asegurarnos de que se cumplan dos condiciones: que cada par estado-acción se visite muchas veces (infinitamente, en teoría) y que la política converja en una política que sea greedy con respecto a la estimación de la función de valor Q. Nos referimos a estas condiciones como Greedy in the Limit of Infinite Exploration (GLIE)[1], y son las que aseguran que el agente continúe explorando en todos los times steps y que gradualmente explote más y explore menos.

Una forma de satisfacer estas condiciones es modificar el valor de ϵ, haciéndolo decaer gradualmente al especificar una política ϵgreedy. La práctica habitual es comenzar con ϵ = 1.0 (100% de acciones aleatorias) y disminuir este hiperparámetro lentamente a un valor pequeño, aunque ϵ > 0 (en nuestro ejemplo usaremos ϵ = 0.05 como valor mínimo). En general, esto se puede obtener introduciendo un factor que llamaremos decay rate, ϵ-decay, con un valor cercano a 1 que multiplique el hiperparámetro ϵen cada iteración.

Sin embargo, hay que tener mucho cuidado al establecer el hiperparámetro ϵ-decay. Determinar el mejor valor no es fácil y requiere un poco de «alquimia», es decir, bastante experiencia.

6.2 Método de control Monte Carlo constant-alpha

En la sección anterior hemos avanzado el método de control Monte Carlo en el que, en el paso de evaluación de la política, el algoritmo recopila una gran cantidad de episodios para construir la función Q aprovechando el método de predicción presentado en la sección 5.4. Pero, en realidad, se puede establecer este ciclo de control para cada episodio de interacción. Y esta es la optimización a este algoritmo propuesta en la literatura: el uso de la función Q calculada con solo un episodio para actualizar la política.

Media incremental

En este caso, aunque la política se actualiza antes de que los valores de la tabla Q se aproximen con precisión a la función Q, esta estimación de «menor calidad» tiene suficiente información para ser utilizada para mejorar la política. Y esa nueva política podría usarse para generar el próximo episodio; y así sucesivamente.

Veamos cómo formalizar esta optimización en el algoritmo. Sabemos que la media

de una secuencia

se puede calcular de forma incremental:

Y como

podemos transformar la ecuación de la media:

Esto nos permite expresar de forma incremental la actualización de A(St,At), que es la media de todos los retornos. En cada time step t para cada par estado-acción A(St,At) con retorno Gt podemos actualizar de la siguiente forma:

Constant-alpha

El algoritmo de control Monte Carlo constant-alpha actualiza la política después de cada episodio (en lugar de esperar a que los valores de la tabla Q converjan completamente después de muchos episodios). Este método se esquematiza en la Figura 6.3.

Figure 6.3 Esquema visual del método de control Monte Carlo constant-alpha, que actualiza la política después de cada episodio.

Podemos resumir todas las explicaciones anteriores con el pseudocódigo 6.1 para el algoritmo de control Monte Carlo constant-alpha.

Pseudocódigo 6.1 Algoritmo de control Monte Carlo constant-alpha con ϵ-decay.

6.3 Implementación del método de control Monte Carlo

En esta sección, programaremos una implementación del método de control Monte Carlo constant-alpha para que un agente aprenda la política óptima del entorno de blackjack, guiándonos por el pseudocódigo presentado en la sección anterior.

Selección de hiperparámetros

En el capítulo anterior se han implementado los algoritmos de predicción Monte Carlo para el entorno blackjack basados en una política predefinida por el agente, con la que se han generado los episodios.

Ahora, con este algoritmo de control Monte Carlo, se encontrará una política óptima aprendida directamente de episodios que no requieren de ninguna política predefinida por el programador para ser generados.

El algoritmo lo definiremos en una función que llamaremos MC_control() que, además de devolvernos la política — tal como se indica en el pseudocódigo — , nos devolverá la función Q que usaremos después para analizar y comprobar la calidad de la política encontrada. Lo haremos de la siguiente manera:

Específicamente, la política se retorna en la variable policy en forma de un diccionario cuya clave corresponde a un estado (una tupla de 3 elementos que indica la suma actual de las cartas del jugador, la carta boca arriba del crupier y si el jugador tiene o no un As utilizable). El valor de la entrada correspondiente indica la acción que el agente elige después de observar este estado siguiendo esta política.

Esta función también nos devuelve la función Q en forma de diccionario donde la clave corresponde a un estado y el valor correspondiente es una matriz de dimensión igual al número de acciones (2 dimensiones en nuestro caso) con el valor estimado para cada acción que se puede seleccionar desde este estado.

Como entrada, esta función tiene los siguientes argumentos:

· env: la instancia del entorno Gym.

· num_episodes: número de episodios que se generarán.

· alpha: el step size que se aplicará en la actualización de los elementos de la tabla Q en cada iteración.

· eps_decay: el decay rate que se aplicará para la actualización del hiperparámetro épsilon.

· gamma: el factor de descuento.

Cabe resaltar que, a pesar de que estamos presentando el algoritmo para buscar la política que debe aplicar un agente para desenvolverse en el entorno blackjack, este algoritmo es genérico y puede ser aplicado a cualquier otro entorno de Gym indicándolo en el argumento env.

Antes de entrar a explicar los pasos que realiza el algoritmo que implementa el método propuesto, paremos un momento a ver cómo se modifica el valor de ϵ a lo largo de los episodios para conseguir la política ϵ-greedy (que — recordemos — es clave para conseguir que el método de control Monte Carlo converge hacia la política óptima).

Con el siguiente código que establece el valor de ϵ en cada episodio, y monitorizando su evolución con un print, podemos comprobar que seleccionando un eps_decay = 0.9999965 se obtiene un decaimiento gradual de ϵ de acuerdo a lo que requerimos:

Por lo tanto, antes de empezar el bucle de episodios, inicializamos el valor de epsilon a 1. Luego, para cada episodio, disminuimos ligeramente el valor de epsilon multiplicándolo por el valor eps_decay. Como vemos, hemos puesto un umbral mínimo para asegurarnos de que se realiza un mínimo de exploración durante todo el proceso.

Algoritmo

Comencemos a programar la función principal guiándonos por el pseudocódigo presentado en la sección anterior. Lo primero es inicializar todos los valores de la tabla Q. Igual que en la implementación del método de predicción Monte Carlo, Q se inicializa en un diccionario vacío especificando como tamaño de cada entrada el número total de acciones que están en el entorno:

Después, se realiza un bucle de generación de episodios; tantos como los que se indican en el argumento num_episodes:

En cada iteración de este bucle, antes de generar el episodio, calculamos el valor del épsilon correspondiente, tal como hemos explicado en el anterior apartado:

A continuación, ya se puede construir la política ϵ-greedy con respecto a la estimación más reciente de la tabla Q y, con esta nueva política ϵ-greedy, generamos un nuevo episodio. Todo esto lo haremos con la función generate_episode_from_Q() :

episode_generated = generate_episode_from_Q(env,Q,epsilon,nA)

Finalmente, actualizamos la tabla Q con la función update_Q(), que aplica la ecuación de actualización presentada en la anterior sección:

Q = update_Q(env, episode_generated, Q, alpha, gamma)

Fuera ya de este bucle principal que realiza estas tres líneas de código, y una vez finalizado el buscar la función Q óptima, se crea un diccionario con una entrada por cada estado, que será la política que retorna la función:

Es decir, la política indica para cada estado qué acción debe realizar el agente, que en realidad corresponde a la acción greedy (la que tiene el valor máximo en la tabla Q).

Recapitulando, el código completo de la función que implementa el método de control Monte Carlo se muestra a continuación:

Analicemos ahora con más detalle la función que genera los episodios y la función que actualiza la tabla Q, que hemos programado por separado para tener una mejor legilibilidad del código.

La construcción de la política ϵ-greedy correspondiente y la generación de un episodio usando esta política ϵ-greedy se realizan en la función generate_episode_from_Q() instanciada en el código anterior. Esta función recibe como argumentos el entorno, la estimación más reciente de la tabla Q, el valor de épsilon actual y el número de acciones. Como salida, devuelve un episodio.

En esta función, para seleccionar acciones se utilizará la política ϵ-greedy, que se ha implementado usando el método random.choice de Numpy, que recibe como argumentos el conjunto de posibles acciones y las probabilidades correspondientes a cada opción según la política ϵ-greedy:

Si el estado aún no está en la tabla Q, elegimos al azar una acción usando el método action_space.sample(). El cálculo de las probabilidades para cada acción correspondiente a la política ϵ-greedy se realizará en la función get_probs, que se ha programado como:

Finalmente, el código de la función update_Q() es el siguiente:

Se observa que la función calcula los retornos estimados de la misma manera que en el algoritmo para el caso del método de evaluación. Con este retorno, aplica la fórmula antes indicada a todos los pares estado-acción que aparecen en el episodio que se ha pasado a la función como argumento.

Análisis de resultados

Igual que en el capítulo anterior, proponemos visualizar los valores de la función Q para facilitar su análisis. Podemos hacerlo de la misma manera, visualizando el valor de los estados calculados a partir de esta función Q. Así, podremos comparar visualmente esta política que hemos encontrado con las anteriores.

Podemos obtener la visualización de la función V a partir de la función Q con el siguiente código:

Figura 6.4 Visualización de la función Q en el entorno Black-Jack-v0 correspondiente a la política óptima, calculada por el método de control Monte Carlo constant-alpha.

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 6.4. Con un simple análisis visual, comparando las Figuras 6.4 y 5.3, podemos comprobar que los valores de los estados son, en general, mucho mejores con esta política obtenida con el método de control Monte Carlo que los que se presentaron en el capítulo anterior resultado de la política estocástica que habíamos programado nosotros.

Quizás nos sería útil un valor numérico, más cuantitativo, para poder comparar las tres políticas vistas hasta ahora. Por ejemplo, podríamos medir el comportamiento de las tres políticas presentadas hasta ahora simulando unas cuantas partidas con el siguiente código:

Los resultados parecen razonables. Si el agente usa la primera política, pierde un 65% de las partidas. Con la política de plantarse cuando las cartas suman más de 15 puntos, pierde casi el 53% de las veces. Finalmente, con la política que el método de control Monte Carlo ha conseguido, pierde solo el 48% de las veces.

También podríamos intentar describir de forma visual, directamente, la política obtenida con el método de control Monte Carlo. Para ello, podemos usar un código basado en el original del GitHub de Udacity[2], con el que se puede generar el gráfico de la Figura 6.5, en el que se muestra la política óptima para cada estado de nuestro entorno.

En la Figura 6.5 se ve claramente que la política obtenida con este método sí tiene en cuenta la información de la carta que muestra el crupier, o si disponemos o no de un As — a diferencia de la política estocástica anterior, que solo tenía en cuenta el valor de las cartas del jugador — .

Figura 6.5 Representación visual de la política óptima obtenida por el método de control Monte Carlo constant-alpha.

Este resultado lo podemos comparar con el mostrado en la Figura 5.2 del libro de R. Sutton y A. Barto[3] que muestra, siguiendo el mismo estilo de grafismo, la política óptima para este entorno que simula el juego de blackjack. Podemos ver que en nuestro caso se aproxima bastante. Pero queda margen para mejorar, y esto se puede conseguir ajustando aún más los parámetros épsilon, alpha o el número de episodios. Invito al lector o lectora a probarlo.

Un último análisis de los datos que puede ser interesante es ver cómo el algoritmo va aprendiendo a medida que va viendo episodios. Concretamente, las Figuras 6.6, 6.7 y 6.8 muestran la evolución del porcentaje de partidas ganadas, partidas perdidas y partidas empatadas, que el agente va consiguiendo a medida que va aprendiendo de los episodios (eje horizontal).

Para generar estos gráficos, hemos aprovechado la misma función de test() que hemos usado antes para comparar las políticas, y nos hemos servido de Tensorboard (presentado en el capítulo anterior) para ir recolectando los datos. Se puede encontrar el código que genera estos gráficos en el notebook correspondiente a este capítulo en el GitHub del libro.

Figura 6.6 Evolución del porcentaje de partidas ganadas en función de los episodios generados usando la política obtenida por el método de control Monte Carlo constant-alpha.

Figura 6.7 Evolución del porcentaje de partidas perdidas en función de los episodios generados usando la política obtenida por el método de control Monte Carlo constant-alpha.

Figura 6.8 Evolución del porcentaje de partidas empatadas en función de los episodios generados usando la política obtenida por el método de control Monte Carlo constant-alpha.

6.4 Aprendizaje por diferencia temporal: SARSA y Q-Learning

En las anteriores secciones hemos explorado cómo los métodos Monte Carlo permiten aprender la política óptima sin necesidad de conocer la dinámica del modelo del entorno — a diferencia del método Value Iteration presentado en el capítulo 4 — . Ahora bien, para poder aprender de la experiencia, estos métodos requieren realizar episodios completos y tener que esperar hasta el final de un episodio para obtener el retorno real antes de poder actualizar y realizar mejoras en la estimación de la función de valor.

En esta sección, vamos a presentar una mejora al método Monte Carlo para solucionar este problema. Fue introducida por Richard S. Sutton en 1988 en un artículo de investigación[4], y se conoce como aprendizaje por diferencia temporal (temporal difference). Este artículo mostró que el método Monte Carlo puede usar la diferencia entre predicciones temporalmente sucesivas (de ahí el nombre de aprendizaje de diferencia temporal) combinando las ventajas de la programación dinámica y del método Monte Carlo.

Diferencia temporal como suma de Monte Carlo y programación dinámica

Recordemos que la programación dinámica utiliza la ecuación de Bellman para calcular el valor de un estado, que se puede obtener como la suma de la recompensa inmediata y el valor descontado (multiplicado por el factor de descuento) del siguiente estado. Es decir, para calcular el valor de un estado no tenemos que esperar hasta el final del episodio — como en el caso de Monte Carlo — , sino que utilizando la ecuación de Bellman podemos estimar el valor de un estado basándonos en el valor estimado del siguiente estado con la fórmula:

A esto, en el área de aprendizaje por refuerzo, lo llamamos bootstrapping,que se puede leer como «estimar en base a otra estimación previa». Es decir, los retornos se calculan aprendiendo una estimación a partir de otra estimación. Pero ya hemos avanzado que la desventaja de la programación dinámica es que solo podemos aplicarla cuando conocemos la dinámica del modelo del entorno, es decir, la probabilidad de transición P(s’|s,a).

En cambio, el método Monte Carlo (MC) es un método model-free, lo que significa que no se requiere la dinámica del modelo del entorno para estimar los valores de los estados y las acciones. Sin embargo, la desventaja del método MC es que para obtener estas estimaciones tenemos que esperar hasta el final del episodio y, si la tarea es continua (tarea no episódica), no podemos aplicar dicho método.

Una característica interesante de MC — suponiendo que estemos en una tarea episódica y esperemos al final para obtener el retorno — es que tiene propiedades de convergencia bastante sólidas, porque actualiza la estimación de la función de valor con el retorno real, que es una estimación no sesgada de la función de valor real.

Sin embargo, aunque los retornos reales obtenidos son estimaciones bastante precisas, también es una estimación de alta varianza de la función de valor real. Esto se debe a que los retornos reales acumulan muchos eventos aleatorios en la misma trayectoria; todas las acciones, todos los estados siguientes, todas las recompensas son eventos aleatorios. Eso significa que el rendimiento real recopila y combina toda esa aleatoriedad para múltiples time steps. Por eso decimos que en MC el retorno que se obtiene es no sesgado, pero con una alta varianza.

Además, debido a la alta varianza de los retornos, MC puede ser muy ineficiente en la obtención de las muestras de datos para calcular las funciones de valor. Toda esa aleatoriedad se convierte en ruido que solo puede aliviarse con muchas trayectorias y muestras de retornos reales.

Una forma de disminuir el problema de la alta varianza consiste, en lugar de utilizar el retorno real, en estimar un retorno y aprender de los episodios incompletos. Y este es precisamente el enfoque de diferencia temporal (TD). Entonces, igual que en la programación dinámica, en TD se realiza bootstrapping para no tener que esperar hasta el final de un episodio para calcular el valor de los estados.

Y, de igual modo, para el valor de los pares estado-acción; es decir, los valores de la tabla Q que requerimos para obtener la política óptima. Recordemos que, en el algoritmo de control Monte Carlo para obtener una política óptima, la ecuación de actualización después de un episodio completo es:

En esta ecuación de actualización se coge la estimación actual Q(St,At) de la tabla Q y se compara con el retorno Gt obtenido al final del episodio que ha visitado ese par estado-acción en algún momento de su trayectoria. Usamos ese nuevo retorno Gt para hacer que nuestra tabla Q sea un poco más precisa. La única diferencia entre los métodos TD y los métodos MC es que los métodos TD actualizan la tabla Q en cada time step en lugar de esperar hasta el final del episodio.

Esta mejora tuvo un gran impacto en el avance de los métodos de aprendizaje por refuerzo, y el aprendizaje TD es el precursor de técnicas como SARSA o Q-Learning, que son la base de muchos de los métodos actuales, que implementan dos versiones de la ecuación de actualización. El código para ambos métodos es equivalente al que mostramos en el pseudocódigo 6.1 para el método de control Monte Carlo, con la excepción de que la actualización de la tabla Q se realiza al mismo tiempo que se genera el episodio. Veamos cada uno de estos dos métodos en más detalle.

SARSA

Viendo esta secuencia, se pude comprobar que el nombre de este método es en realidad el acrónimo State-Action-Reward-State-Action.

En la Figura 6.9 podemos encontrar un esquema global que permite visualizar en qué momentos del episodio se actualiza la tabla Q y a su vez se actualiza la política.

Figura 6.9 Representación visual de los puntos de un episodio en los que se actuliaza la tabla Q y la política π en el algoritmo SARSA.

El algoritmo del método SARSA se muestra en el pseudocódigo 6.2. Se puede constatar que es equivalente al mostrado en el pseudocódigo 6.1, con la única diferencia de que la actualización de los valores de la tabla Q se realiza con la nueva fórmula en cada time step.

Pseudocódigo 6.2 Algoritmo de control SARSA.

Q-Learning

El otro método se llama Q-Learning, también conocido como SARSAMAX. Es exactamente como SARSA con la única diferencia de que no sigue una política para encontrar la siguiente acción, sino que elige la acción que tiene el valor Q máximo (de ahí el nombre de SARSAMAX).

Siguiendo la misma esquematización realizada con SARSA, en la Figura 6.10 se representa una trayectoria y en qué momentos se actualiza la tabla Q y a su vez se actualiza la política épsilon-greedy.

Figura 6.10 Representación visual de los puntos de un episodio en los que se actualiza la tabla Q y la política π en el algoritmo Q-Learning.

El algoritmo del método Q-Learning se muestra en el pseudocódigo 6.3. Se puede constatar que es equivalente al mostrado en el pseudocódigo 6.2 para el algoritmo SARSA, con la diferencia principal de que la actualización de los valores de la tabla Q se realiza con la nueva fórmula.

Pseudocódigo 6.3 Algoritmo de control Q-Learning.

Es importante remarcar que en ambos algoritmos la acción se elige de acuerdo con la política épsilon-greedy; la diferencia principal radica en la actualización de la tabla Q.

On-policy versus off-policy methods

Antes de acabar este libro, aprovechemos estos métodos que acabamos de presentar para introducir uno de los conceptos utilizados para clasificar métodos en el aprendizaje por refuerzo: on-policy y off-policy.

En el aprendizaje on-policy, la tabla Q se aprende a partir de acciones que se realizan siguiendo la política π que guía al agente y que es la que queremos optimizar. Mientras que en el aprendizaje off-policy, la tabla Q se aprende seleccionando acciones con estrategias diferentes a las marcadas por la política que guía al agente.

Decimos que SARSA es un algoritmo de control on-policy porque la política épsilon-greedy que se evalúa y se va mejorando para obtener la política óptima es la misma que se utiliza para aprender la tabla Q.

Por otro lado, decimos que Q-Learning es un método off-policy porque la política épsilon-greedy que se evalúa y guía al agente es diferente de la política greedy que se utiliza para aprender la tabla Q.

En el capítulo 10 usaremos esta clasificación.

[1] Dong H, Zhang S. and Ding Z. Deep Reinforcement Learning. Fundamentals, Research and Applications (2020) Ed. Springer ISBN: 978–981–15–4094–3.

[2] Véase https://github.com/udacity/deep-reinforcement-learning/blob/master/monte-carlo/plot_utils.py [Consultado: 16/02/2021].

[3] Véase http://incompleteideas.net/book/RLbook2020.pdf[Consultado: 16/02/2021].

[4] Véase http://www.incompleteideas.net/papers/sutton-88-with-erratum.pdf [Consultado: 15/02/2021].