Introducción al aprendizaje por refuerzo. Parte 2: Q-Learning.
En la parte 1, hemos descrito el problema del bandido multibrazo, y hemos introducido varios conceptos, como el estado, la acción, la recompensa, etc. Sin embargo, el problema del bandido multibrazo no representa el problema completo del aprendizaje por refuerzo. En los problemas de bandidos multibrazo, cada acción es completamente independiente de las anteriores, y el estado siempre es el mismo, como en el ejemplo de la parte 1, donde siempre teníamos los 5 mismos brazos y su probabilidad de éxito no cambiaba en ningún momento.
En el problema completo de aprendizaje por refuerzo, el estado cambia cada vez que ejecutamos una acción. Podemos representar el problema de la siguiente manera. El agente recibe el estado (state) en el que se encuentra el entorno (environment), el cual representaremos con la letra s (state). El agente ejecuta entonces la acción que elija, representada con la letra a (action). Al ejecutar esa acción, el entorno responde proporcionando una recompensa, representada con la letra r (reward), y el entorno se traslada a un nuevo estado, representado con s’ (next state). Este ciclo se puede observar en la imagen 1.
Por lo tanto, la acción que el agente escoja no debe sólo depender de la recompensa a que vaya a recibir a corto plazo. Debe elegir las acciones que a largo plazo le traerán la máxima recompensa (o retorno) posible en todo el episodio (episode). Este ciclo trae una secuencia de estados, acciones y recompensas, desde el primer paso del ciclo hasta el último: s1, a1, r1; s2, a2, r2; …; sT, aT, rT. Aquí, T indica el fin del episodio.
Función de valor
Para cuantificar cuanta recompensa obtendrá el agente a largo plazo desde cada estado, introducimos la función de valor V(s). Esta función produce una estimación de la recompensa que obtendrá el agente hasta el final del episodio, empezando desde el estado s. Si conseguimos estimar este valor correctamente, podremos decidir ejecutar la acción que nos lleve al estado con el valor más alto.
Q-Learning, resolviendo el problema
Para resolver el problema del aprendizaje por refuerzo, el agente debe aprender a escoger la mejor acción posible para cada uno de los estados posibles. Para ello, el algoritmo Q-Learning intenta aprender cuanta recompensa obtendrá a largo plazo para cada pareja de estados y acciones (s,a). A esa función la llamamos la función de acción-valor (action-value function) y este algoritmo la representa como la función Q(s,a), la cual devuelve la recompensa que el agente recibirá al ejecutar la acción a desde el estado s, y asumiendo que seguirá la misma política dictada por la función Q hasta el final del episodio. Por lo tanto, si desde el estado s, tenemos dos acciones disponibles, a1 y a2, la función Q nos proporcionará los valores-Q (Q-values) de cada una de las acciones. Por ejemplo, si Q(s,a1)=1 y Q(s,a2)=4, el agente sabe que la acción a2 es mejor y le traerá mayor recompensa, por lo que será la acción que ejecutará.
Ejemplo: Entorno de cuadrícula
En este ejemplo, tenemos un entorno en el que el agente empieza en el estado inicial s_i, y debe elegir entre moverse a la izquierda o a la derecha. Si llega al estado de más a la izquierda, el episodio termina y el agente recibe una recompensa de -5. Por otro lado, si llega al estado de más a la derecha, el episodio termina y el agente recibe una recompensa de +5. El agente debe aprender a evitar el estado de -5 y moverse hacia el estado de +5. Si la política que aprende siempre termina en el estado con mayor recompensa, diremos que ha encontrado la política óptima (optimal policy).
Para resolver el problema, el algoritmo Q-Learning utiliza la ecuación de Bellman. Esta ecuación se usa para aprender los valores-Q.
Ecuación de Bellman
La explicación para esta ecuación es la siguiente. El valor-Q del estado s y la acción a (Q(s, a))debe ser igual a la recompensa r obtenida al ejecutar esa acción, más el valor-Q de ejecutar la mejor acción posible a’ desde el próximo estado s’, multiplicado por un factor de descuento γ (discount factor), que es un valor con rango γ ∈ (0, 1]. Este valor γ se usa para decidir cuánto peso le queremos dar a las recompensas a corto y a largo plazo, y es un hiperparámetro que debemos decidir nosotros.
El código, resolviendo el ejemplo
Ejecuta tú mismo el código paso a paso en este enlace o sigue leyendo para ver el código sin ejecutarlo.
Empecemos definiendo nuestro entorno. Las recompensas son 0 para todos los estados, excepto para el estado de más a la izquierda y el de más a la derecha, que tienen recompensas de -5 y +5 respectivamente. También definimos una lista que define si un estado es final/terminal o no. Y por último creamos la lista de variables llamada Q_values, donde guardaremos los valores-Q para todos los pares de estados y acciones.
Ahora crearemos una función que escoja una acción usando la política ε-voraz para un estado que pasaremos como parámetro.
También crearemos una función que ejerza de entorno. Le pasaremos el estado y la acción seleccionada por el agente, y nos devolverá la recompensa r y el siguiente estado s’.
Por último, decidimos varios hiperparámetros y ejecutamos el algoritmo que aprende usando el algoritmo de Q-Learning y la ecuación de Bellman.
Al terminar, observamos los valores-Q aprendidos y la mejor acción para cada estado. Al ejecutarlo vemos que ha aprendido exactamente lo que queríamos, la política óptima, a moverse hacia la derecha siempre. Hay que tener en cuenta que los valores-Q han sido descontados por el factor de descuento, que en este caso es 0.9. Los estados de la derecha y la izquierda tienen valores de 0.0 porque son terminales y el episodio termina al llegar a ellos.
Q-values are: [[0.0, 0.0], [-5, 3.28], [2.95, 3.64], [3.28, 4.05], [3.64, 4.5], [4.05, 5], [0.0, 0.0]]
Best action for state 0 is left
Best action for state 1 is right
Best action for state 2 is right
Best action for state 3 is right
Best action for state 4 is right
Best action for state 5 is right
Best action for state 6 is leftSi deseas ejecutar y ver el código completo paso a paso, hazlo en este enlace.
La serie completa de introducción al aprendizaje por refuerzo:
