Aprendizaje por refuerzo: algoritmo Q Learning
Todos los seres vivos exhiben algún tipo de comportamiento, en el sentido que realizan alguna acción como respuesta a las señales que reciben del entorno en el que viven. Algunos de ellos, además, modifican su comportamiento a lo largo del tiempo, de forma que ante señales equivalentes se comportan de forma distinta con el paso del tiempo... en algunos de estos casos decimos que estos seres vivos han aprendido de su entorno (independientemente de si esa variación en la respuesta ha generado alguna ventaja o no en el individuo). De hecho, esta variación es la que aprovechamos cuando entrenamos un perro para que se siente cuando se lo pidamos.
Como ya hemos visto en entradas anteriores, el campo del aprendizaje automático estudia la generación de algoritmos que sean capaces de aprender de su entorno (en este caso, el entorno es el conjunto de datos que el algoritmo recibe en una etapa particular que se llama entrenamiento).
En esas entradas destacábamos dos tipos principales de aprendizaje automático: por una parte, el Aprendizaje Supervisado, y por otra el Aprendizaje no Supervisado. Sin embargo, junto a estos dos grandes tipos de aprendizaje, suele considerarse un tercer tipo que es conocido como Aprendizaje por Refuerzo, en el que el algoritmo de aprondizaje recibe algún tipo de valoración acerca de la idoneidad de la respuesta dada. Cuando la respuesta es correcta, el aprendizaje por refuerzo se parece al aprendizaje supervisado: en ambos casos el aprendiz recibe información acerca de lo que es apropiado. Sin embargo, ambas aproximaciones difieren significativamente ante las respuestas erróneas, cuando el aprendiz responde de forma inadecuada. En este caso, el aprendizaje supervisado le dice exactamente al aprendiz qué debería haber respondido, mientras que el aprendizaje por refuerzo solo le informa acerca de que el comportamiento ha sido inapropiado y (normalmente) cuánto error se ha cometido. Esta aproximación, la del aprendizaje por refuerzo, es mucho más habitual en la naturaleza que el aprendizaje supervisado. En el ejemplo que comentábamos, cuando al perro le damos la orden de sentarse, si lo hace recibe algún tipo de recompensa (una galleta, o una caricia), y si no lo hace puede recibir algún tipo de castigo (si no somos unos salvajes bastaría con una palabra de tono más elevado). Repetir esta tarea con el perro produce un refuerzo de los comportamientos que reciben recompensa en detrimento de aquellos comportamientos que reciben castigo.
Aprendizaje por Refuerzo
Para simular el aprendizaje de sistemas biológicos reales necesitamos hacer algunas suposiciones que simplifican el comportamiento de nuestros agentes (o aprendices). Estas simplificaciones nos permitirán tener un sistema más flexible para proyectar diversas situaciones con el mismo sistema y, a la vez, nos permitirá extraer conclusiones más generales acerca de las propiedades de los algoritmos que implementen estos sistemas de aprendizaje.
En general, y como primera aproximación, supondremos que los aprendices siguen un Proceso de Decisión de Markov, es decir:
- El agente percive un conjunto finito, \(S\), de estados distintos en su entorno, y dispone de un conjunto finito, \(A\), de acciones para interactuar con él.
- El tiempo avanza de forma discreta, y en cada instante de tiempo, \(t\), el agente percive un estado concreto, \(s_t\), selecciona una acción posible, \(a_t\), y la ejecuta, obteniendo un nuevo estado, \(s_{t+1}=a_t(s_t)\).
- El entorno responde a la acción del agente por medio de una recompensa, o castigo, \(r(s_t,a_t)\). Formalizaremos esta recompensa/castigo por medio de un número, de forma que cuanto mayor es, mayor es el beneficio.
- Tanto la recompensa como el estado siguiente obtenido no tienen porqué ser conocidos a priori por el agente, y dependen únicamente del estado actual y de la acción tomada. Es decir, antes de aprender, el agente no sabe qué pasará cuando toma una acción determinada en un estado particular. Precisamente, un buen aprendizaje es aquel que permite adelantarse al agente en las consecuencias de las acciones tomadas, reconociendo las acciones que sobre estados concretos le llevan a conseguir con más eficacia y mayores recompensas, sus objetivos.
El objetivo del aprendizaje por refuerzo es extraer qué acciones deben ser elegidas en los diferentes estados para maximizar la recompensa. En cierta forma, buscamos que el agente aprenda lo que se llama una política, que formalmente podemos verla como una aplicación que dice en cada estado qué acción tomar. Dividiremos la política del agente en dos componentes: por una parte, cómo de buena cree el agente que es una acción sobre un estado determinado y, por otra, cómo usa el agente lo que sabe para elegir una de las acciones posibles.
Hay varias formas de implementar estos procesos de aprendizaje. En esta entrada nos centraremos en lo que se conoce como Q learning, una forma de aprendizaje por refuerzo en la que el agente aprende a asignar valores de bondad a los pares \((estado, acción)\).
Para diseñar un algoritmo que use estas ideas hemos de hacer una distinción entre lo que es verdad en el mundo, y lo que el agente cree que es verdad en el mundo:
Comencemos por lo que es verdad en el mundo. Si un agente está en un determinado estado y toma una acción concreta, estamos interesados en la recompensa inmediata que recibe, pero también en las recompensas futuras que se obtendrán por pasar a otros estados donde se pueden tomar otras acciones, que seguirán un política particular. En el algoritmo Q Learning, el valor \(Q\) de un par \((estado, acción)\) contiene la suma de todas estas posibles recompensas. El problema es que esta suma podría ser infinita en caso de que no haya un estado terminal que alcanzar y, además, es posible que no queramos dar el mismo peso a las recompensas inmediatas que a las recompensas futuras, en cuyo caso se hace uso de lo que se llama un refuerzo acumulado con descuento: las recompensas futuras quedan multiplicadas por un factor, \(\gamma\in [0,1]\), de forma que cuanto mayor sea este factor, más influencia tienen las recompensas futuras en el valor \(Q\) del par analizado.
Si el agente supiera a priori los valores \(Q\) de todos los posibles pares \((estado, acción)\) podría usar esta información para seleccionar la acción adecuada para cada estado. El problema es que al principio el agente no tiene esta información, por lo que su primer objetivo es aproximar lo mejor posible esta asignación de valores \(Q\). Como los valores de \(Q\) dependen tanto de recompensas futuras como de recompensas actuales, hemos de proporcionar un método que sea capaz de calcular el valor final a partir de los valores inmediatos y locales. Para ello:
- Si una acción en un estado determinado causa un resultado no deseado, hay que aprender a no aplicar esa acción en ese estado. Si una acción en un estado determinado causa un resultado sí deseado, hay que aprender a aplicar esa acción en ese estado.
- Si todas las acciones que se pueden tomar desde un estado determinado dan resultado negativo, es conveniente aprender a evitar ese estado. Es decir, no tomar acciones desde otros estados que nos lleven a él. Por contra, si cualquier acción en un determinado estado da un resultado positivo, se debe aprender que es conveniente llegar a él. Este hecho es lo que permite propagar la recompensa de un par (estado, acción) a los pares de los estados adyacentes.
Matemáticamente, podemos formalizar el cálculo de los valores \(Q\) por medio de la siguiente ecuación:
\(Q(s_t,a_t)= r(s_t,a_t) + \gamma \max_{a_{t+1} } Q(s_{t+1},a_{t+1})\)
Esto es, el valor de \(Q\) óptimo para un par \((estado, acción)\) es la suma de la recompensa recibida cuando se aplica la acción junto al valor descontado del mejor valor \(Q\) que se puede conseguir desde el estado alcanzado al aplicar esa acción. Para aproximar este cálculo, al principio del aprendizaje los valores \(Q\) se establecen a un valor fijo (puede ser aleatorio), a continuación el agente va tomando pares de \((estado, acción)\) y anota cuánta recompensa recibe en ellos, entonces, actualiza el valor almacenado del valor \(Q\) de cada par considerando como ciertas las anotaciones tomadas de los otros pares (algunas de las cuales habrán sido aproximadas en pasos anteriores).
Una variante de la ecuacion anterior podría ser la siguiente:
\(Q'(s_t,a_t)= (1-\nu) Q(s_t,a_t) + \nu [r(s_t,a_t) + \gamma \max_{a_{t+1} } Q(s_{t+1},a_{t+1})]\)
Esta segunda ecuación intenta que la actualización de la función sea más gradual, no permitiendo cambios en una determinada dirección de forma tan brusca, para ello, introduce un factor de aprendizaje, \(\nu\), que controla la variación de \(Q\). El nuevo valor de \(Q\) es la combinación ponderada del antiguo valor de \(Q\) y la nueva información que el agente debe creer.
Un aspecto importante del aprendizaje por refuerzo es la restricción de que solo se actualizan los valores \(Q\) de acciones que se ejecutan sobre estados por los que se pasa, no se aprende nada de acciones que no se intentan. Pero puede ser interesante que, sobre todo al principio del aprendizaje, el agente intente una gama más amplia de acciones, para hacerse una idea de lo que funciona y lo que no. Más concretamente, en cualquier momento el agente puede elegir entre:
- seleccionar una acción con el valor \(Q\) más alto para ese estado (explotación), o
- seleccionar una acción al azar (exploración).
Vamos a formalizar este proceso de decisión en términos de probabilidades:
La posibilidad más simple es elegir completamente al azar entre una opción y otra, pero usaremos una opción un poco más inteligente y asignaremos una probabilidad a cada acción en función del valor \(Q\) asociado, de forma que cuanto mayor sea el valor \(Q\) de esa acción, mayor será la probabilidad de ser elegida. De esta forma, incluso las acciones con valores \(Q\) más bajos tendrán opciones de ser elegidas. También tiene sentido hacer que la probabilidad de exploración dependa del tiempo que el agente lleva aprendiendo, de tal forma que, al principio, se favorece la exploración porque lo que el agente haya aprendido todvía no es confiable y porque todavía quedan muchas opciones que no han sido consideradas, y más tarde se potencia la explotación, porque la experiencia del agente hace que su conocimiento sea más confiable. Así, la ecuación de la probabilidad de seleccionar la acción \(a_t\) sería:
\[P(a_t)=\frac{e^{E\cdot t \cdot Q(s_t,a_t)} }{\sum_{a\in A_{s_t} } e^{E\cdot t \cdot Q(s_t,a)} }\]
donde \(E\) es una constante de explotación, y \(A_{s_t}\) representa todas las posibles acciones que se pueden tomar desde \(s_t\). Gracias a la función exponencial, a medida que \(t\) aumenta, las acciones que tengan un valor \(Q\) más alto se hacen mucho más grandes, por lo que tendrán más probabilidad de ser elegidas.
Se puede comprobar que estos valores \(Q\) convergen al valor óptimo que estamos buscando.
En caso de que el espacio de estados sea una cantidad finita y manipulable, no es necesario realizar toda la segunda parte de selección de acciones para equilibrar la exploración con la explotación, basta realizar un recorrido completo de todos los posibles pares e ir actualizando el valor de \(Q\). La convergencia del método asegura que obtendremos el resultado deseado.
Un pequeño ejemplo: Las Torres de Hanoi
Por ejemplo, en el caso de estar intentando aprender a resolver el problema de las Torrres de Hanoi, cuando tanto el número de torres como el de discos es bajo podemos trabajar con el espacio completo de estados y representar las acciones (mover el disco superior de una torre a otra) como aristas del grafo completo de transiciones.
En la figura siguiente se muestra el caso de 3 torres con 3 discos y el camino aprendido (en rojo) por el programa para pasar de la configuración en la que todos los discos están en la primera torre ([ [1 2 3] [ ] [ ] ]) a la configuración final en la que todos los discos se encuentran en la tercera torre ([ [ ] [ ] [1 2 3] ]). El grosor de las aristas asociadas a las diversas acciones representa el valor \(Q\) aprendido por el algoritmo (a mayor grosor, mayor valor).
Se inicia el algoritmo proporcionando una recompensa inicial de 100 a las transiciones que llevan directamente a la configuración deseada, y posteriormente se irá propagando hacia las demás transiciones por medio del valor \(Q\), hasta que el algoritmo se estabiliza. Puede observarse que aquellas transiciones que están más cerca de la solución final obtienen un valor de \(Q\) más alto. En este caso, como el grafo completo es manejable y lo hemos podido calcular a priori, no hemos tenido la necesidad de explorar aleatoriamente el espacio de soluciones, y podemos permitirnos el lujo de recorrer completamente todo el espacio de pares \((estado, acción)\) las veces necesarias hasta considerar que el algoritmo se ha estabilizado.
Tras el entrenamiento del algoritmo lo único que hemos de hacer es partir de la configuración inicial (en verde en la parte inferior del grafo) e ir aplicando las acciones con mayor recompensa hasta llegar a la configuración final (en rojo en la esquina superior izquierda).
El entrenamiento completo depende únicamente del estado final que se quiere alcanzar (lo que no ocurre cuando no podemos trabajar con el espacio completo de soluciones), por lo que una vez entrenado para una determinada salida no necesitamos reentrenarlo, y podemos modificar la configuración inicial deseada para obtener automáticamente la solución que proporciona el aprendizaje.
Q Learning en casos continuos
En el método visto en el apartado anterior todo es discreto (estados, acciones, y tiempo), y por esa razón el algoritmo visto es fácilmente implementable. Sin embargo, puede haber casos en que el método así visto no es aplicable, bien sea porque el conjunto de posibles pares es excesivsamente grande (incluso infinito siendo discreto) o porque alguno de ellos es continuo. Aunque no abordaremos el caso continuo por completo, sí merece la pena dar algunas ideas de cómo se podría abordar su solución por medio de aprendizaje con refuerzo.
Un ejemplo donde el estado es continuo es un robot vigilante. Su estado se forma a partir de la información recibida por una serie de sensores que le indican distancia a paredes, rugosidad del suelo, etc. Estos sensores producen información prácticamente continua (la distancia puede tomar en teoría infinitos valores diferentes).
Un ejemplo donde la acción es continua es en el sistema de control de un vehículo, donde las acciones incluyen el ángulo de giro del volante o la presión que hay que ejercer en los pedales.
Para sistemas con estados continuos, un posible solución pasa por sustituir la matriz de pares para almacenar los refuerzos por medio de algún método de aproximación de funciones (por ejemplo, una red de neuronas), donde la entrada sea el estado y se usa una función para cada posible acción. En este caso, la actualización de los valores Q se consigue por entrenamiento de la función.
Si, además, tenemos un sistema con acciones continuas, el truco pasaría por usar una única función que reciba dos datos de entrada continuos (el par). Puede haber un problema en la selección de la mejor acción para un estado, ya que habría que realizar un muestreo y probar con múltiples acciones para buscar la mejor, un proceso que puede llegar a ser muy lento. Para resolver este problema se suele considerar una variante, el algoritmo Actor-Crítico, del algoritmo general para poder decidir la mejor acción de forma eficiente, que veremos en una entrada posterior.
Para saber más...
A Painless Q Learning Tutorial
Q Learning: Aprendizaje Automático por refuerzo (Rubén López)