3 - Evaluación de la política: ejemplo práctico
Lección 3 del curso Aprendizaje por Refuerzo Nivel Intermedio.
Tabla de contenido
Introducción
En la lección anterior vimos todos los detalles de la evaluación de la política, el primer algoritmo básico de la Programación Dinámica.
Para entender en detalle la manera como funciona este algoritmo, en esta lección haremos un ejemplo paso a paso para ver cómo se actualizan los diferentes valores de los estados al momento de aplicar el algoritmo de forma iterativa.
Suscríbete para tener acceso al video con la explicación detallada de esta lección. Además podrás disfrutar de todos los cursos de la Academia Online
El tablero bidimensional estocástico: las reglas del juego
Para implementar este ejemplo volvamos a nuestro juego base: el tablero bidimensional estocástico (que ya analizamos previamente en una de las lecciones del curso anterior).
A continuación resumiremos las reglas de este juego:
- Contiene un total de 16 estados correspondientes a las casillas 0 a 15
- El objetivo es que el agente parta del inicio (estado 0) y llegue a la meta (estado 15)
- En cada transición de estado la recompensa será 0, exceptuando cuando logre pasar de la casilla 14 a la 15 (en este caso recibirá una recompensa igual a 1)
- Los estados 5, 7, 11 y 12, junto con la meta (estado 15) son estados terminales lo cual quiere decir que el episodio terminará si el agente hace la transición a uno de estos estados
- Las acciones tienen un comportamiento estocástico: un movimiento en una dirección especificada por [la política] tendrá una probabilidad de ocurrencia del 33% y el 66% restante estará distribuido equitativamente en las direcciones ortogonales
Por simplicidad de los cálculos que haremos más adelante, asumiremos un factor de descuento $\gamma = 1$.
La política a evaluar
Para este ejemplo supondremos que la política que queremos evaluar es la ilustrada en la figura, donde cada flecha de color amarillo indica la acción que debería ejecutar el agente en cada uno de los estados. Sin embargo tengamos en cuenta que dicha acción no necesariamente será la que en últimas ejecutará el agente, pues dichas acciones tienen un comportamiento estocástico tal como lo mencionamos en el apartado anterior.
El algoritmo de Evaluación de la Política
Como referencia re-escribiremos a continuación el algoritmo de Evaluación de la Política que vimos en detalle en la lección anterior:
-
Entrada: $\pi$, la política a evaluar
-
Parámetros: $\theta > 0$: umbral que permitirá detener la ejecución del algoritmo en un número finito de iteraciones
-
Inicializar:
- Todos los valores a 0. Todos los estados terminales siempre serán 0
- $\Delta \leftarrow 0$: variable que contendrá la máxima variación de estados entre una iteración y otra
-
Iterar
Repetir mientras $\Delta > \theta$:
para cada s en S:
$temp \leftarrow v(s)$
$v(s) \leftarrow \sum_{a}\pi(a|s)\sum_{s’,r}p(s’,r|s,a)[r+\gamma v(s’)]$
$\Delta \leftarrow max(\Delta,|v(s)-temp|)$
Ejemplo de actualización de los estados: entrada e inicialización
La entrada al algoritmo será entonces la política y además inicializaremos cada estado a un valor igual a cero. Recordemos además que los estados terminales siempre se mantendrán iguales a cero.
Además ajustaremos el parámetro $\theta$ en $1x10^{-10}$.
Evaluación iterativa de la política: iteraciones 1 y 2
Recuerda suscribirte para acceder al video con la explicación detallada de esta lección. Además podrás disfrutar de todos los cursos de la Academia Online
Evaluación iterativa de la política: iteraciones restantes
Con los dos ejemplos anteriores ya entendemos cuáles son los cálculos realizados por el algoritmo, así que si seguimos repitiendo el procedimiento veremos que poco a poco se irán actualizando los diferentes valores de los estados y que en la iteración 218 se dentendrá el algoritmo pues el $\Delta$ alcanzado será inferior al umbral establecido, obteniendo así el cálculo aproximado final para cada uno de los estados.
Conclusión
Muy bien con este ejemplo ya entendemos los cálculos y el procedimiento que lleva a cabo internamente el algoritmo de Evaluación de la Política.
Así que es momento de ir al siguiente paso, el algoritmo de Mejora de la Política que veremos en la próxima lección, y que es un algoritmo que nos permite partir de una política y, como su nombre lo indica, aplicar mejoras para obtener un mejor desempeño del agente.