4 - Mejora de la política y ejemplo práctico

Marzo 24, 2022 por Miguel Sotaquirá

Lección 4 del curso Aprendizaje por Refuerzo Nivel Intermedio.

Introducción

En la lección anterior vimos un ejemplo práctico del algoritmo de Evaluación de la Política, que en últimas permite de forma iterativa obtener el valor de cada estado en nuestro problema de Aprendizaje por Refuerzo.

La limitación de este algoritmo de Evaluación de la Política es que, como su nombre lo indica, sólo nos permite cuantificar qué tan buena o mala es una Política, pero no nos permite hacer cambios a la misma.

Sin embargo, el objetivo final es encontrar la mejor Política para el Agente, así que debemos ir un escalón más allá. Así que en esta lección veremos cómo usar la función Acción-Valor, junto con el algoritmo de Evaluación de la Política, para introducir mejoras a una política en particular.

Repaso: algoritmos de Programación Dinámica

Recordemos que la Evaluación de la Política es el primer algoritmo básico de la Programación Dinámica, que recibe como entrada una Política y genera a la salida una cuantificación de la misma a partir de la función Estado-Valor.

Pero en ese momento también mencionamos los algoritmos de mejora e iteración de la Política, y el de iteración de valores, que buscan obtener una Política óptima para el Agente.

Entonces podríamos pensar: si con el primer algoritmo tenemos una manera de evaluar la política, para encontrar la mejor política posible basta con crear múltiples políticas, evaluarlas y de ellas escoger la que tenga los valores más altos.

Pues aunque es una aproximación válida, no es la manera más adecuada de hacerlo por dos razones: (1) porque sería un desperdicio de recursos computacionales y (2) porque nada nos garantiza que de esta forma obtengamos mejores políticas.

Pero entonces, ¿de qué otra forma podemos hacerlo?

¡La función Q (o función acción-valor) al rescate!

Recordemos que la función Acción-Valor (o función Q) vista en el curso anterior, tiene una ventaja frente a la función Estado-Valor: mientras que la segunda evalúa únicamente el valor de un estado, la primera permite evaluar la bondad de tomar una acción en particular partiendo de un estado.

Así que si volvemos a nuestro problema de encontrar la mejor Política, podemos pensar que si partimos de una serie de estados conocidos (calculados con el algoritmo de Evaluación de la Política) y luego calculamos para cada uno de esos estados la función Q para cada una de las posibles acciones, entonces tendremos un panorama completo de cuál será la mejor acción para cada estado, y estos valores nos darán precisamente una pista para mejorar la Política.

Lo anterior quiere decir que la Política que tomamos como punto de partida no necesariamente indicará en cada estado la mejor acción a ejecutar por parte del agente. Pero si en lugar de tomar esta acción evaluamos todas las posibles acciones para cada estado, y luego tomamos en cada caso la mejor de ellas, ¡podríamos obtener una mejor política que la inicial!

Mejora de la Política: el algoritmo en detalle

Así que podemos resumir el algoritmo de Mejora de la Política en los siguientes pasos:

1. Tomar la política a mejorar y evaluarla usando el algoritmo de evaluación de la política.

2. Para cada estado y cada posible acción , calcular la función Q a partir de la Ecuación de Bellman

3. La política mejorada será simplemente el resultado de tomar la mejor acción indicada por la función Q en cada uno de los estados

Mejora de la política: ejemplo práctico

Para entender cómo aplicar el algoritmo de Mejora de la Política veamos un ejemplo práctico para entender cómo realizar los cálculos numéricos.

Retomando nuestro ejemplo del tablero bidimensional estocástico asumamos una política inicial y unos estados como los que se muestran en la figura.

Asumiendo un factor de descuento de 0.99, veamos paso a paso cómo realizar los cálculos de la función Q para el estado 0 y para cada una de las acciones disponibles (los valores Q para los estados restantes se podrán calcular de la misma forma):

1. Acción izquierda: en este caso, y teniendo en cuenta el componente estocástico en las acciones, tendremos tres posibles acciones a ejecutar (a la izquierda, arriba y abajo), cada una con un 33.33% de probabilidad de ocurrencia. Teniendo esto en cuenta, el valor Q para esta primera acción lo podemos calcular de a partir de la Ecuación de Bellman, obteniendo 0.4057

2. Acción derecha: en este caso las tres posibles acciones a ejecutar serán derecha, arriba y abajo, cada una con un 33.33% de probabilidad de ocurrencia. Al realizar el cálculo obtenemos un valor de 0.3951 para esta acción.

3. Acción arriba: en este caso las tres posibles acciones a ejecutar serán arriba, izquierda y derecha, cada una con un 33.33% de probabilidad de ocurrencia. El valor de la acción en este caso será de 0.389

4. Acción abajo: en este caso las tres posibles acciones a ejecutar serán abajo, izquierda y derecha, cada una con un 33.33% de probabilidad de ocurrencia, obteniendo un valor de 0.3951 para esta acción.

Y podemos ver que en este caso particular la mejor acción posible, definida por la función Q, es la acción de movimiento a la izquierda (con un valor de 0.4057). Esta será precisamente la mejor acción a tomar para este estado.

Si repetimos el procedimiento para los estados restantes, tomando en cada caso la mejor acción definida por la función Q, obtendremos la versión mejorada de la Política tal como lo vemos en la figura.

De hecho, si evaluamos esta Política mejorada veremos que en efecto los valores de sus estados son mayores que los de la original: ¡hemos mejorado la Política!

Conclusión

Muy bien, ya hemos ido un paso más allá de la Evaluación de la Política: hemos usado la función Acción-Valor para, en cada estado, determinar la mejor acción posible y de esta forma mejorar la Política.

Pero la pregunta es: ¿será que podemos seguir repitiendo este proceso de evaluación y mejora una y otra vez para cada vez tener una mejor Política hasta llegar a aquella que sea óptima? Pues la respuesta es sí, y este será precisamente el algoritmo de Iteración de la Política del cual hablaremos en la próxima lección.

Ver todas las lecciones de este curso