Aprendizaje por Refuerzo: Predicción Libre de Modelo
La predicción libre de modelos se basa en tener un problema que se pueda expresar por medio de un MDP, pero no necesariamente conocemos la estructura de este, por lo tanto, no sabemos cómo funcionan realmente las mecánicas de este ambiente, siendo el objetivo encontrar como un agente debe comportarse óptimamente dado el ambiente desconocido.
Introducción
En el anterior post vimos cómo resolver un MDP que se conocía por completo, en este post veremos cómo estimar la función de valor de un MDP desconocido.
Aprendizaje de Monte-Carlo
El algoritmo de aprendizaje de Monte-Carlo nos sirve para estimar la función de valor, toma muestras directamente de episodios realizados por un agente dada la política que elegimos, funciona mejor para ambientes que tienen las características de juegos, es decir, que siempre tienen un final.
¿Cómo funciona el MC?
MC estima la función de valor repitiendo una y otra vez la política elegida desde un estado s hasta el final del episodio, al terminar de realizar estas pruebas se promedia todo el retorno obtenido (El retorno representa el total de recompensa utilizando el factor de descuento) y de esta manera se encuentra la función de valor para dicha política, esta el manera más “simple” de encontrar la función de valor, el aprendizaje de Monte-Carlo se puede ejecutar de dos maneras:
Evaluación de Política de Primera Visita de Monte-Carlo
Para evaluar la política π se inicia seleccionando un estado s:
- Se genera una muestra ejecutando la política π sobre el ambiente.
- Se iniciará un episodio si se visita el estado s en dicha muestra, solo se considera un episodio si por lo menos se pasa una vez por el estado s.
- Se añadirá el valor de uno a un contador n por la primera vez que se visite el estado s por episodio (que llevará la cuenta de cuantas veces se ha visitado el estado s en el total de nuestros episodios).
- Se contabilizará el valor del retorno final desde que se visite el estado s por primera vez por episodio hacia adelante, el cual luego se guardará junto al retorno de los siguientes episodios que también pasen por el estado s, el retorno se contabilizará desde el momento que se visita el estado s por primera vez hasta el final del episodio.
- Luego de ejecutar el algoritmo hasta que se estabilicen los valores se hallará la media del retorno total dividiendo el retorno total entre el contador n, la cual nos dará como resultado la función de valor de la política π.
Según la ley de los grandes números, si tomamos el promedio de un gran numero de episodios eventualmente se acercará y convergerá en la función de valor de la política π, como requisito para que funcione esta evaluación de política se necesita que se visiten todos los estados que pueden ser alcanzados por la política π por lo menos una vez, y esto se logra al reproducir el experimento un gran numero de veces.
Evaluación de Política de Cada Visita de Monte-Carlo
Para evaluar la política π se iniciará de nuevo seleccionando un estado s:
- Se genera una muestra ejecutando la política π sobre el ambiente.
- Se iniciará un episodio si se visita el estado s en dicha muestra, se considera un episodio cada vez que se pasa por el estado s.
- Se añadirá el valor de uno a un contador n por cada vez que se visite el estado s.
- Se contabilizará el valor del retorno final desde que se visite el estado s hasta el final del episodio, el cual luego se guardará junto al retorno de los siguientes episodios.
- Luego de ejecutar el programa las veces que uno crea necesario se hallará la media del retorno total dividiendo el retorno total entre el contador n, la cual nos dará como resultado la función de valor de la política π.
Como se ve, la diferencia con este método es que cada vez que se visita el estado s, se generará un nuevo episodio del cual se contabilizará el retorno desde el momento que visitan el estado, hasta el final.
Media Incremental
La media de una secuencia puede calcularse incrementalmente dándole forma a la ecuación de la siguiente manera:
Esto permitiría que el algoritmo de aprendizaje de Monte-Carlo pueda ser actualizado al final de cada episodio, en este caso sería representado de la siguiente manera:
N representa el contador dentro del algoritmo de Monte-Carlo, V la función de valor, G el retorno y S el estado.
Aquí una pequeña implementación de MC en Python, para que el concepto quede mas claro.
Método de Diferencia Temporal
Este método aprende directamente de episodios de experiencias, tambien funciona sin modelo.
¿Cómo funciona el TD?
El método de diferencia temporal aprende de episodios incompletos por medio de boostrapping, esta técnica consiste en tomar un camino parcialmente y estimar cual sería el retorno de este sin recorrerlo en su totalidad, esta retorno estimado se ve actualizado cuando el agente tome otro paso en dirección hacia este camino.
El objetivo es aprender la función de valor de manera online, bajo la política π:
Como se había mostrado TD se encarga de encontrar el retorno estimado (también llamado TD target u Objetivo TD), el cual se representa con la siguiente formula:
Esta fórmula nos muestra que el retorno estimado puede ser representado como el retorno del estado donde nos encontramos más el valor estimado del resto de la trayectoria. Ahora, basados en la fórmula de Actualización Online de MC, variaremos el retorno real Gt, por el retorno estimado, dejándonos la siguiente formula:
La parte final de la formula que se encuentra entre paréntesis es llamada Error TD.
MC vs TD
TD
- Puede aprender antes de ver el resultado final, debido a que puede estimar cual será el retorno de una situación dado el punto en donde se encuentra, esto quiere decir que TD puede ir aprendiendo durante cada paso dentro del camino.
- Puede aprender de episodios incompletos, es decir de episodios donde no se llega nunca a un estado final.
- TD busca la máxima verosimilitud para un modelo de Markov (intenta construir un MDP que encaje de mejor manera con los datos).
- Funciona mejor que MC en ambientes menos aleatorios.
MC
- Debe esperar hasta el final del episodio para saber el retorno.
- Solo puede aprender de secuencias completas.
- Busca la solución con menor error cuadrático medio (Se basa en el retorno obtenido).
- Funciona mejor que TD en ambientes parcialmente explorados y/o más aleatorios.
Intercambio entre el Sesgo y la Varianza
- El retorno que da MC no tiene ningún sesgo.
- El retorno estimado de TD (o TD target) se encuentra sesgado, debido a que podemos estimarlo equivocadamente.
- El TD target tiene menor varianza, debido a que solo depende de una acción aleatoria, una transición y un retorno, en cambio el retorno real depende de varias acciones aleatorias, varias transiciones y varios retornos.
TD(λ)
Predicción de N-pasos
Ahora que sabemos cómo funciona MC y TD, sería válido pensar, ¿Por qué TD solo toma un paso antes de estimar la función de valor?, por qué no tomar 2 o 3; esta es la idea detrás de predicción de n-pasos. Hasta este punto hemos visto cómo funciona TD utilizando solo un paso, llamado TD(0) y también como funciona MC, algoritmo que recorre todos los estados antes de generar una estimación, pero en esta sección veremos que se encuentra entre estos dos algoritmos.
Veremos cómo definir el retorno para n-pasos:
Para este caso, el retorno se define como el retorno para todos los pasos dados en el ambiente y una estimación del retorno que vendría hasta la terminación de este episodio.
Podríamos añadir esto, para generar la función TD para n-pasos:
Dada las posibilidades que se muestran ahora, ¿Cómo podríamos elegir un n que sea mejor para cualquier problema? ¿Podríamos promediar varios retornos?
Si, en realidad se puede promediar varios retornos para obtener lo mejor de ellos, es decir, podríamos promediar el retorno de un n = 4 y de un n = 2 y utilizarlo como TD target, así obtendríamos lo mejor de ambos.
Retorno λ
El retorno λ combina el retorno de todos los n utilizando una media ponderada, el retorno cambia a la siguiente formula:
Donde λ es un número entre 0 y 1.
Lo cual genera la siguiente formula para TD(λ) hacia adelante.
Esa vista de TD(λ) es más que nada teórica, si se desea poner en practica TD(λ) se necesita utilizar TD(λ) hacia atrás, debido a que no podemos saber actualmente cuanto es el valor para cada estado que viene hacia delante en nuestro MDP, es por eso que nos basamos en TD(λ) hacia atrás que nos permite actualizar nuestro valor basado en las recompensas que recibimos y los estados que hemos visitado.
Rastros de Elegibilidad
Si quisiéramos actualizar nuestra función de valor; ¿A qué estado deberíamos asignarle més o menos “responsabilidad” por el descenso del retorno?
Es por esto que nace el concepto de rastros de elegibilidad, que mantiene un conteo de que tan recientemente se visita cada estado y con qué frecuencia, esto nos da una idea de cómo penalizar más justamente a cada estado, y actualizar nuestra función de valor.
Esta fórmula es TD(λ) hacia atrás utilizando rastros de elegibilidad.
Et(s) Representa los rastros de eligibilidad, que designará que estado se actualizará en mayor medida que otro; δ representará el error de TD.
Implementación
A continuación comparto una implementación de TD(λ), si deseas ver el código completo y una implementación de Monte Carlo visita mi página de github.
Esto es todo lo que veremos por este post, espero que les sea de ayuda y cualquier duda por favor escribirme.
Muchas Gracias!
