Aprendizaje por Refuerzo: Control Libre de Modelo

En este capítulo nos centraremos en entender como un agente sin experiencia previa en un ambiente desconocido (el cual puede o no tener final) decide que acciones debe desempeñar para maximizar la recompensa, para lograr esto nos basaremos en lo visto en el capítulo anterior, el cual trató de cómo estimar una función de valor para un MDP desconocido, en este caso buscaremos optimizar esa función utilizando técnicas que hemos visto antes y algunas nuevas, para comenzar revisaremos que tipos de políticas podemos utilizar para esta clase de problemas.

Tipos de política

Aprendizaje usando política

Se sigue la política π, y mientras esto se hace también se le evalúa realizando muestras sobre ellas.

Aprendizaje sin utilizar la política

Se aprende de una política π utilizando muestras realizadas por otro u otros agentes, el ejemplo más entendible sería quizás observar el ejemplo de otra persona (o pedirle consejo a alguien para tomar una decisión) y guiarse de eso para saber que tan bueno sería tomar una decisión.

Iteración de Política Generalizada

Como habíamos visto en capítulos anteriores la iteración de política está basada en una función que evalúe la política π y otra que se encargue de mejorarla, así sucesivamente hasta encontrar la política que nos de la mejor recompensa, la cual sería nuestra política final. Por otro lado, si quisiéramos iniciar explorando este ambiente sin tener conocimiento previos de sus estados, ¿Cómo lo haríamos?.

Para esto debemos tener claro que debemos elegir dos algoritmos, uno para la evaluación y otro para el mejoramiento de política, para evaluación podríamos utilizar un algoritmo que ya venimos conociendo un tiempo atrás, Monte-Carlo, como paso inicial, y para el caso del mejoramiento podríamos utiliza mejoramiento voraz (consiste en siempre elegir los casos que nos aseguran la mejor recompensa), de esta manera Monte-Carlo podría darnos los valores para cada acción y cada estado que visitamos, a la vez que el mejoramiento voraz nos daría una dirección en la cual deberíamos seguir dirigiéndonos para mejorar esta política, para que esto funcione, el mejoramiento voraz necesita un modelo de MDP.

Cómo vamos a centrarnos en encontrar el mejor valor para cada acción nuestra política tiene que estar basada en las posibles acciones que se pueden tomar desde un estado s, en otras palabras, en este nuevo escenario nos centraríamos en usar la política π para encontrar el valor de cada acción que se tomaría en cada estado s, y con esto elegir la acción que genere mayor valor a través de cada estado, generando una nueva politica π.

La desventaja de utilizar este modelo es que se vería limitado por el mejoramiento voraz debido a que siempre tomaría la elección que nos diera el mayor valor inmediato, sin contemplar opciones que podrían ser mas provechosas a largo plazo, en otras palabras, tener opción de mantener:

• Exploración continua.
• Todas las acciones han sido probadas con probabilidades mayores a cero.

Exploración ε-Greedy

Es por esto que nace el concepto de exploración ε-greedy, la cual nos permite tener una probabilidad de 1 — ε de escoger la mejor acción para nuestra política y una probabilidad de ε para escoger una acción totalmente aleatoria, con este método tendremos la posibilidad de visitar estados que no serían posibles de visitar escogiendo siempre el mejor estado, y por otro lado esto nos asegura como mínimo tener una solución igual de buena que la política actual, si es que no mejor.

¿Como podemos seguir mejorando nuestro modelo?

Ahora que ya hemos encontrado un método que nos ayuda a explorar el ambiente y en general a tener una mejor política, deberíamos buscar como mejor la evaluación de la misma, al utilizar Monte-Carlo nos asegura llegar al mejor resultado pero no necesariamente por un proceso veloz, dicho esto haría falta elegir una forma más eficiente de evaluar dichas políticas, quizá podríamos comenzar por no esperar hasta recorrer cierto número de episodios para evaluar nuestra política, en cambio bastaría con evaluarla al final de un sólo episodio, lo cual daría suficiente información para guiarnos hacia una ligeramente mejor política π.

Sin embargo debemos encontrar un balance entre el tiempo que nos tomará encontrar la mejor política y la cantidad de acciones aleatorias que tomaremos, es por esto que nace el concepto de GLIE.

GLIE

GLIE(Greedy in the Limit with Infinite Exploration) parte de la necesidad de limitar la exploración luego de que se hallan cumplido sus dos pilares fundamentales:

• Todas las acciones por cada estado han sido exploradas una infinidad de veces.
• La política al final convergerá en una política voraz.

Una forma de llegar a eso es por medio de ε-greedy, la cual se podría convertir en una política voraz si ε tiende a 0 con el paso del tiempo, aquí dejo una implementación en Python para que veas detalladamente como funciona.

Una pregunta que nacería naturalmente con la experimentación sería la siguiente, ¿Cómo podríamos actualizar nuestra política si estamos hablando de un ambiente continuo (Online)?. Qué acción deberíamos tomar si es que no podemos esperar hasta el final del episodio para actualizar nuestra política, por este motivo nos centraremos en una herramienta que habíamos visto en el capítulo pasado, TD Learning como método de evaluación de política, este algoritmo tambien posee otros beneficios aparte de ser un entrenamiento “Online”, como disminuir la varianza y actualizar nuestra política aun que las secuencias no sean completadas del todo.

SARSA

Al usar TD Learning como método de evaluación y ε-greddy como método de actualización llegamos al algoritmo SARSA, el cual significa:

Estado S -> Acción A -> Recompensa R -> Estado S’ -> Acción A’

Dicho algoritmo representa un patrón de actualización para nuestra política explicado por la siguiente fórmula:

De esta manera se actualiza nuestro valor para cada par estado-acción dependiendo de las acciones que se podrán tomar desde ese punto.

SARSA se centra en actualizar nuestro valor inicial para el estado s y la acción a sumándole TD Target menos nuestro valor de ese par original todo esto multiplicado por un valor α, que representa el impacto con el cual se actualizará los valores, como quedó claro esto se va a actualizar cada vez que se tome una acción en nuestro ambiente, eso significa que si volvemos a caer en un estado que ya ha sido visitado, vamos a tener un valor actualizado de ese estado con la última información que pudimos recabar.

SARSA λ

SARSA λ nos da lo mejor de los dos algoritmos que hemos visto anteriormente en este capitulo, SARSA λ nos permite variar que tanto deseamos “recordar” (al igual que TD λ) los estados y acciones que hemos visitado, nos ayuda a decidir que en que medida valoramos estas acciones y estados ejecutados en el mismo episodio en pasos anteriores con respecto a nuestra actualización de valores, a continuación se muestra gráficamente como el valor de los estados visitados en el pasado se ven afectados por la constante λ, que en cada paso se multiplicará de nuevo por el mismo factor, para así decrecer el impacto de ese paso en el tiempo.

De esta manera se promedian todos los pasos que se realizados desde el inicio del episodio hasta ese momento en el tiempo para actualizar los valores de los estados y acciones visitados.
En el algoritmo también tendremos en cuenta rastros de elegibilidad, en este caso representados por Et(s, a). Al ejecutarse la actualización tendremos en cuenta el TD-Error representado con δ, siempre todo multiplicado por un valor de α que representa la magnitud de actualización de nuestros valores como se muestra en la siguiente formula:

A continuación una implementación de SARSA λ en Python para que el concepto quede mas claro.

Aprendizaje Fuera de Política

Hasta este punto dentro de todos los capítulos solo hemos observado la capacidad de aprender de la misma política que estamos evaluando pero esto no siempre es el caso, es aquí donde nace el concepto de aprendizaje fuera de política el cual se basa en evaluar una política objetivo mientras se sigue otra llamada de comportamiento, un ejemplo de esto sería tener una política exploratoria como política de comportamiento y tener una política objetivo que este basada en la elección de la acción que nos de mayor valor, esto nos puede ayudar a balancear el concepto de la exploración vs explotación uno de los problemas esenciales dentro del Aprendizaje por Refuerzo. Otro motivo por el cual podría interesarnos es que permite aprender múltiples políticas (teniéndolas como políticas objetivo) mientras se sigue la política de comportamiento.

Q-Learning

Es aquí donde nace el concepto de Q-Learning, con la aplicación de el concepto de aprendizaje fuera de política hacia algoritmos que permitan disminuir la variación de la misma, como SARSA, el funcionamiento de estos conceptos juntos es el siguiente, se centra en que la política de comportamiento sea la que siempre elija que acción tomar y a su vez se contempla que valor puede tener una siguiente acción tomada de la política objetivo, de esta manera nos ayudaría a medir mejor el valor de la acción actual tomando en cuenta ambas políticas.

Dicho modelo tiene como objetivo mejorar la política objetivo y de comportamiento, y para lograr esto Q-Learning utiliza una política Voraz como objetivo (para tener el valor de la mejor acción posible) y una política de comportamiento ε-Greddy (para que tengamos la totalidad de estados y acciones explorados), esto nos lleva, por medio de la ecuación de Bellman a encontrar la política óptima, este algoritmo muchas veces converge más rápido que SARSA λ.

Implementación

A continuación comparto una implementación de MonteCarlo, pero en mi repositorio de github tengo implementaciónes de Q-Learning y SARSA.

Esto es todo lo que veremos por este capitulo, espero que les sea de ayuda y cualquier duda por favor escribirme.

Muchas Gracias!

Referencias

• UCL Course on RL Lecture 5: Model-Free Control
• Richard Sutton’s Intro to Reinforcement Learning