1. Introducción

En este blog hablaremos del algoritmo A3C: una modificación al algoritmo original de Actor-Critic, que muestra buenos resultados en muchas aplicaciones y que se considera a día de hoy estado del arte con algunas modificaciones (como por ejemplo, utilizar capas LSTM). Hay toda una base que sustenta al aprendizaje por refuerzo, que si no conoces te recomendaría leer mi blog anterior en el cual explico a muy grandes rasgos el aprendizaje por refuerzo, algunos algoritmos, muestro resultados interesantes, y pongo las referencias más imprescindibles para poder entender el blog y sacarle jugo.

Video de mi blog donde explico las bases del RL.

Como he mencionado, en el blog que hice acerca de DDQN buscábamos aprender una función de valor, la cual hace un mapeo $S \times A \rightarrow R$. Estos métodos, en general, buscan encontrar la mejor acción para cada estado. Sin embargo, no siempre contaremos con un espacio tan limitado de acciones, algunas veces incluso nuestros estados y acciones podrían ser infinitas.

Sin embargo, el aprovechar funciones de valor no es el único acercamiento que existe. También podemos clasificar algunos métodos como basados solamente en política. Y dirás, “pero Víctor, la función Q que ajustamos está bajo la política $\pi$”. Y es cierto, pero en estos nuevos métodos ya no existe una función de valor que optimizar, sino directamente la política. Esto es bastante útil cuando nuestro espacio de acciones es muy grande, continuo o estocástico. Sin embargo, ambas tienen problemas serios a la hora de aplicarlas en problemas reales. Es por esto que se desarrolló un paradigma que pudiera cubrir ambos huecos que dejaban estos dos acercamientos. Este paradigma se le llamó Actor-Critic.

2. Actor-Critic

Actor-Critic es un paradigma de RL profundo que cuenta con dos agentes:

• El crítico, el cual evalúa qué tan buena fue la decisión tomada.
• El actor, el cual controla cómo reacciona el agente.

El primer agente es básicamente una funcion de acción-valor (como las de Q-learning), mientras que el segundo se basa solamente en la política (como REINFORCE). Es por esto que comunmente se dice que Actor-Critic es un método híbrido.

Con esto, ya tenemos bien marcados, clasificados y reconocidos los algoritmos de RL:

Entre muchos otros algoritmos, aunque puramente basados en políticas no son tan populares actualmente. También, en algunas referencias encontraremos una categorización diferente, como en la siguiente:

Imagen tomada del repositorio en Github del framework Coach

Nótese que que en vez de poner a los métodos Actor-Critico como el tercer paradigma del RL, consideran que es otra subcategoría de los métodos basados en políticas (lo cual es cierto, pero entonces también debería ser basada en valores) junto con los métodos de descendo de gradiente de política (básicamente los algoritmos REINFORCE y sus variantes).

Métodos de descenso de gradiente en políticas

El problema principal de estos métodos es encontrar una función que evalúe correctamente la política que estamos aprendiendo, ya que suele usar la recompensa total de todo un episodio (en un juego, por ejemplo Space Invaders, un episodio podría ser hasta que se acabe el juego por quedarnos sin vidas), lo que implica lo siguiente:

• En un episodio con muy alto puntaje, cualquier acción mala ¡es buena!
• En un episodio con bajo puntaje, las acciones buenas ¡son las que debemos evitar!

Todo porque nuestra única retroalimentación es el fin, y el fin no siempre justifica los medios. Puede que hagamos la mejor jugada de nuestras vidas en un episodio, pero si resulta mal, nuestro agente no querrá volver a hacer una maravillosa jugada.

Entonces, ¿Cómo lo resolvemos? Bueno, a alguien se le ocurrió decir, oigan chicos, ¿y si actualizamos nuestra política por cada acción, en vez de cada episodio? Algunos fieles seguidores del método de Montecarlo se rieron a carcajadas mientras veían pésimos resultados en sus bots jugando ATARI, mientras que el sujeto en cuestión escribía la siguiente ecuación en secreto:

Donde $\theta$ son los parámetros de nuestro agente. Nótese que, en los métodos de REINFORCE no hay na función Q, por lo que antes de Actor-Critic ahí estaba la recompensa del episodio. Pero entonces, aquí viene de nuevo el problema: ¿cómo encontramos ahora Q? ¡Ya teníamos suficiente con $\theta$ !

Bueno, ¿sabes qué es mejor que utilizar una red neuronal para aprender? Pues sí, ¡Dos redes neuronales! Una para aprender los parámetros y la otra para Q. También debe notarse que los métodos Actor-Critic son REINFORCE, salvo que utilizan métodos de diferencias temporales en vez de Montecarlo.

3. A2C: Actor Crítico con ventaja

El método A2C sigue básicamente la misma idea que el AC normal, salvo que no usan la misma función de valor así como la conocemos en los métodos como DQN, ya que hay evidencia que muestra que tiene mucha variabilidad. Es por esto que se definió la función de ventaja, la cual se calcula

Donde $V(s)$ es el valor promedio de ese estado. Esto nos dirá basicamente si hubo mejora o no, ya que si es positivo significa que nuestra $Q(s,a)$ es mejor que el promedio, por lo cual estamos mejorando. Sin embargo, esto solo implica que hay que calcular ahora dos funciones. ¿Es aquí donde llega la legendaria tercer red neuronal? No amigos, aún no llegamos a eso, pues resulta que:

Es decir, es igual al error en las diferencias temporales, lo cual se vuelve más sencillo de calcular.

4. A3C: Actor Crítico asíncrono con ventaja

En este paper encontrarán las primeras versiones del A3C, así como de otros algoritmos clásicos del RL en su versión asíncrona. Es un excelente paper, y es justamente el que cubre la mayor parte del estado del arte actual en RL, ya que hoy en día todos los grandes métodos son asíncronos, es decir, que corren en paralelo varios agentes completamente dependiente. Esto reemplaza al RL del 2015, que utilizaba mecanismos muy interesantes y elegantes llamados replay debido a su alto consumo de memoria. Para realizar el entrenamiento, utilizan solo 16 cores de CPUs y muestran mejores resultados que las grandes GPUs y en menor tiempo en muchos de los juegos. Las redes neuronales son prácticamente las mismas que en los papers del DQN Bootstrapped, salvo que ahora hay una modificación en la que agregan una capa LSTM con 256 unidades después de la última capa convolucional. También muestran una versión del A3C FF (FeedForward).

Gracias a Papers with code decidí utilizar el A3C LSTM ya que es el segundo mejor algoritmo para jugar Space Invaders, con las características que vienen en el paper que aseguran dar mejores resultados.

6. Resultados

En un total de 8 horas de entrenamiento, con 16 agentes corriendo simultaneamente, se obtuvieron grandes resultados. No están al nivel del paper, pues ocuparíamos tener cuatro días de entrenamiento. Sin embargo, es un bot que ya puede jugar Space Invaders a un nivel humano. Gracias por leer hasta aquí.