Muchos de los algoritmos que conforman el así llamado machine-learning (y no digamos nada la antigua inteligencia artificial simbólica) son relativamente sencillos, lógicos y basados en intuiciones o razonamientos perfectamente inteligibles.
Donde comienza creo, el misterio, la semejanza con la magia es, cuando entramos en el campo del deep learning, de las grandes redes neuronales, donde se escapa un poco de nuestra lógica natural el funcionamiento de estos ingenios y cómo pueden obtener resultados.
Y eso que ocurre, en mi opinión, en toda la inteligencia artificial, también tiene lugar en el área del aprendizaje por refuerzo ('reinforcement learning'), donde existen algoritmos relativamente lógicos y sencillos pero donde también reinan cada vez más los mágicos algoritmos del deep learning.
En este cuarto post de la serie dedicada al aprendizaje por refuerzo, nos vamos a quedar, todavía, en los algoritmos más o menos sencillos, los que no utilizan redes neuronales, unos métodos que en la referencia que estoy siguiendo en toda esta serie, el libro 'Deep reinforcement learning' de Aske Plaat, denomina 'tabulares' porque utilizan unos datos tabulados.
Remataremos con un esbozo del algoritmo Q-Learning, aunque antes nos tendremos que detener a aprender algunos nuevos conceptos y otro algoritmo, SARSA.
Recordatorio: procesos de decisión y aprendizaje por refuerzo
Antes, recordemos todo el marco en que nos estamos moviendo, y que se esquematiza en la figura que estoy usando repetidamente en esta serie de artículos.
Tenemos un agente, por ejemplo un robot, que se mueve en un entorno, un entorno que, en un momento dado, se encuentra en un estado (s). De cara a conseguir sus objetivos, el agente realiza acciones (a) sobre el entorno. Eventualmente, la aplicación de esa acción provoca un cambio de estado en el entorno que pasa del estado (s) al (s'), y el agente recibe una recompensa (r), una suerte de feedback de si se acerca o no a sus objetivos.
Las transiciones de estado del entorno, están regidas por una función Ta. En algunos casos estas transiciones son deterministas, pero con frecuencia siguen distribuciones de probabilidad hallándonos en este caso ante entornos estocásticos. Para elegir la acción a realizar, el agente aplica una política (π).
En general, en un aprendizaje por refuerzo lo que queremos es aprender, u optimizar, esa política π, un poco por ensayo y error, aplicando acciones, viendo las recompensas obtenidas, y ajustando la política.
Modelos del mundo. Algoritmos con y sin modelo
De alguna forma, esa función Ta que hemos mencionado, constituye un modelo del mundo (un modelo del entorno para ser más precisos, pero es común y seguramente 'más bonito' hablar de modelo del mundo).
Con bastante frecuencia, el agente NO conoce ese modelo del mundo, no sabe qué función Ta gobierna los cambios de estado del entorno, por lo que debe optimizar su política (π) sin conocer realmente el modelo del mundo, sólo con base en la interacción con el mismo y las recompensas obtenidas. Ese es el caso de los algoritmos que se denominan sin modelo ('model-free').
Veremos más adelante en esta serie, el caso en que el agente SI puede conocer o al menos aproximar el comportamiento del entorno. En este caso se habla de algoritmos basados en modelo ('model-based').
Explotación y exploración
En un post anterior, hablamos de una función, el valor estado-acción Q(s,a) que nos proporcionada el valor (es decir la recompensa acumulada esperada) ante la aplicación de una acción a, en un estado s.
La lógica más inmediata nos lleva a pensar que lo que tiene que hacer un agente en cada momento es seleccionar aquella acción que proporciona un mayor valor de Q. Es intuitivo y razonable, e incluso pudiera funcionar, pero la experiencia demuestra que esa estrategia, que se denomina 'greedy' (algo así como 'glotona') tiende a conducirnos a máximos locales, pero no globales, con lo que no llegamos realmente a determinar la mejor política de todas, sino una sólo una buena solución, pero no la mejor.
Por eso, se aconseja combinar los mecanismos que se denominan de explotación y exploración.
En explotación funcionamos de modo, digamos normal, usando las mejores acciones hasta donde conocemos (con base en nuestra función estado-valor), pero en exploración introducimos aleatoriedad en lugar de lo que dicte la función Q, para seleccionar la siguiente acción.
Los algoritmos mejores utilizan una combinación de ambos mecanismos, existiendo diversas teorías sobre la mejor forma de establecer ese equilibro o compromiso de en qué medida utilizamos uno u otro.
Aprendizaje de política on y off
A la hora de actualizar la política con base en la recompensa obtenida por el agente, el aprendizaje propiamente dicho mediante el mecanismo de 'backpropagation' que mencionamos en el segundo post de esta serie, lo primero que se nos viene a la cabeza es, simplemente, usar la recompensa para la última acción aplicada. Eso es lo que se denomina un aprendizaje de política 'on' ('on-policy learning').
Sin embargo, también es posible, y puede ser conveniente, no aplicar la retropropagación (el aprendizaje) de acuerdo con la recompensa a la última acción sino adoptar una perspectiva más amplia y, eventualmente, hacer el aprendizaje con otra recompensa quizá anterior. Esto es lo que se denomina aprendizaje de política off ('off-policy learning') y puede tener sentido, por ejemplo, cuando estamos aplicando la exploración que mencionábamos hace un momento. ¿Por qué? porque al explorar fácilmente nos podemos encontrar respuestas muy poco óptimas y no tendría sentido empeñarnos en utilizar la recompensa obtenida como un buen indicador de una buena decisión.
El algoritmo SARSA
Uno de los los algoritmos tabulares conocidos es SARSA. SARSA utiliza sólo explotación y aprendizaje de política on ('on-policy').
¿Cómo funciona? Pues, como conocemos, el agente selecciona una acción y obtiene una recompensa,. Con base en ella actualiza sus función valor-estado Q(s, a) que, indirectamente es como actualizar su política (π). En esa actualización sigue la fórmula:
Q(st, at) ← Q(st, at) + α[ rt+1 + γQ(st+1, at+1) - Q (st, at)]
No entraré en el detalle del significado de la fórmula, sólo indicar que la función valor-estado se va actualizando con base en la recompensa recibida.
El algoritmo Q-Learning
Bueno, pues culminamos el post esbozando, sin entrar en muchos detalles, el algoritmo Q-Learning. En el caso de Q-Learning estamos ante uno de esos denominados algoritmos tabulares (utilizan reglas o tablas en lugar de redes neuronales), utiliza tanto explotación como exploración y un aprendizaje de política off ('off-policy').
A priori, el funcionamiento va a ser muy similar al de SARSA y, si nos nos fijamos, la fórmula de actualización de las funciones valor-estado parece la misma
Q(st, at) ← Q(st, at) + α[ rt+1 + γmaxaQ(st+1, a) - Q (st, at)]
Parece la misma, pero no lo es.
Fijémonos en la parte central de la fórmula, la que he destacado con negritas, y comparemos con el caso de SARSA. Vemos que si en SARSA se utilizaba la función valor del estado finalmente alcanzado, en el caso de Q-Learning se utiliza aquella función valor máxima de entre todas las acciones, no sólo la aplicada en último término. Eso es lo que le confiere la característica de aprendizaje de política off, en lugar de on.
Podemos, de una forma más estructurada y que nos acerca un poquito a un pseudocódigo, expresar el algoritmo Q-Learning de la siguiente maneta:
- Inicializa la tabla de valores (Q) con números aleatorios
- Repite
- Selecciona un estado (s)
- Para todas las posibles acciones (a) aplicables en ese estado (s), selecciona la que proporciona el mayor valor de Q (cuando estés aplicando explotación), o bien, si en esta iteración vas a aplicar exploración, selecciona una al azar.
- Mira la recompensa (r) obtenida y actualiza la tabla de valores Q con la fórmula que hemos visto más arriba
- así hasta que se alcance el objetivo
- Alcanzado el objetivo, repite todo el bucle hasta que los valores de la tabla Q ya no varíen mucho (eso implica fijar algún umbral de variación concreto).
Con esto no hemos especificado del todo el comportamiento, aunque tampoco estamos tan lejos, pero sí es lo suficiente para, si lo leemos despacio, entender la filosofía básica del algoritmo.
Conclusiones
En este post, hemos ampliado algunos conceptos respecto a otros ya utilizados en los tres artículos anteriores. Así, hemos hablado de:
- Algoritmos con y sin modelo ('model based' o 'model-free')
- Concepto de explotación y exploración y la conveniencia de utilizarlos conjuntamente
- Aprendizaje de política on y off ('on-policy' learning y 'off-policy' learning)
Y, finalmente, quizá en la parte más formal y difícil del post, hemos esbozado los algoritmos SARSA y, un poco más, el Q-learning. Ambos tabulares, pero el primero usando aprendizaje 'on-policy' y el segundo introduciendo la exploración y usando aprendizaje 'off-policy'.
Y todavía no hemos llegado a la magia, a la introducción del deep learning porque estos algoritmos que hemos visto, que entran dentro de los llamados tabulares, son un poco más tradicionales, más modestos en sus campos de aplicación y más fáciles de entender (dentro de lo que cabe) .
Pero no tardaremos ya mucho en llegar al aprendizaje con refuerzo usando redes neuronales y deep learning aunque veremos que, si no se entra en detalles, habrá mucha continuidad expositiva con lo visto hasta ahora.
Artículos de este blog relacionados
- Notas sobre aprendizaje por refuerzo (III): recompensas, trazas y valores
- Notas sobre aprendizaje por refuerzo (II): Visualizando el aprendizaje en procesos de Markov
- Notas sobre aprendizaje por refuerzo (I): Procesos de decisión de Markov