Aprendizaje por Refuerzo: Planificando con Programación Dinámica
Ahora que ya hemos visto cómo formalizar el problema de RL dentro de la serie de Aprendizaje por Refuerzo, ahora el siguiente paso es resolverlo, para esto en este y los siguientes post veremos diferentes técnicas y cómo aplicarlas para resolver dichos problemas.
Una de las técnicas más antiguas y conocidas es la programación dinámica.
Introducción
Programación dinámica viene de las palabras “programación” que en matemáticas viene a significar “optimizar un programa”, y en este caso por un programa nos estamos refiriendo a una política, por otro lado la palabra dinámica significa que el problema tiene un componente secuencial o temporal. Entonces la definición de programación dinámica vendría a ser un método de optimización para problemas secuenciales.
¿Y cómo funciona?
Divide el problema en “sub-problemas” y los resuelve, luego vuelve a unir estos sub-problemas para encontrar la solución general.
Para que la programación dinámica pueda ocurrir deben cumplirse dos propiedades muy importantes:
- Sub-estructura óptima
Para que se cumpla esta propiedad debe cumplirse el principio de optimalidad, lo cual significa que el problema se puede resolver si se parte en 2 o más sub-problemas y las óptimas soluciones para esos sub-problemas al unirlas dan como resultado la solución óptima a todo el problema. - Sub-problemas superpuestos
Significa que para que se cumpla esta propiedad, uno o más de los sub-problemas deben ser similares, debido a que si se comportan de la misma manera su respuesta termina siendo bastante parecida y por lo tanto la solución es hallada más rápidamente, para que se cumpla esta propiedad los sub-problemas se deben repetir.
¿Los Procesos de Decisión de Markov cumplen estas propiedades?
Si, las cumplen debido a la ecuación de Bellman, que permite descomponer el MDP, eso cumple la propiedad de sub-estructura óptima.
Pero, ¿Que hay de sub-problemas superpuestos?. Bueno, para esto existe la función de valor, la cual guarda los mejores valores y decisiones a tomar, para la cual ya no se necesita re-calcular si se llega a un estado en donde ya se tiene el máximo valor hallado previamente.
Planificación con Programación Dinámica
La programación dinámica no afecta al problema completo de RL, si no que asume que se conoce completamente el ambiente.
Ahora la programación dinámica nos puede servir para dos casos especiales de planificación en un MDP.
Primero podríamos tomarlo como un caso de predicción, que como entrada le daríamos un MDP<S, A, P, R, γ> y una política π o un MRP<S, Pπ, Rπ, γ> y como salida obtendremos una función de valor π, esta función de valor nos va a decir cuánta recompensa esperar en cada estado de este MDP, en otras palabras evaluará nuestra política.
El otro caso sería como control, para obtener la mayor optimización de este MDP, para esto también tendríamos como entrada un MDP<S, A, P, R, γ> pero en este caso la salida sería la política óptima que deseamos encontrar y la función de valor óptima.
Evaluación de Política
Comenzaremos viendo el primero de los casos, el problema que resolveremos será evaluar la política π y lo vamos a hacer utilizando la ecuación de expectativa de Bellman, la cual vimos en el anterior post.
Para este proceso iniciaremos con un vector de valores arbitrarios “v”, utilizando en el cual dentro de cada iteración se aplicará la ecuación de expectativa de Bellman para ir conociendo los valores de los otros estados raíces, este proceso irá variando utilizando los estados que previamente fueron utilizados como raíces para luego utilizarlos como nodos hijos y hallar el valor del estado raíz, así se seguirá iterando hasta finalmente llegar al valor de vπ, el utilizar todos los estados a la vez, en cada iteración es llamado Synchronous Backups. En otras palabras significa que volveremos la ecuación de expectativa de Bellman en actualizaciones iterativas.
Para entender mejor este problema propondremos el ejemplo de un mundo cuadrícula de tamaño 4 x 4:
- El descuento será de 1
- El estado 0 y el 15 serán los estados terminales de nuestro MDP.
- Se podrá desempeñar 4 acciones, ir a la derecha, izquierda, arriba, abajo.
- La recompensa es -1 hasta que se llega al estado terminal.
- Movimientos que te llevan fuera del mundo te devuelven al mismo estado (con recompensa -1).
- La política será que la probabilidad de tomar cualquier dirección será la misma, o sea 0.25, básicamente al azar.
Desarrollo
Se iniciará con una función de valor arbitrarios, que en este caso serán ceros, en este caso, los ceros de la imagen de la izquierda representan cuantos pasos se necesitan en promedio para llegar a los estados finales.
Ahora aplicamos la función de expectativa de Bellman para cada uno de los estados, para hacer esto seleccionamos un estado como ejemplo, en este caso el estado (0, 1), vemos que cualquier sea la dirección que tome se llevará como recompensa -1 y esto se le suma el valor que tiene el estado donde se encontraría, entonces tendríamos que el nuevo valor para el estado (0,1) sería (-1+0)(1/4)+(-1+0)(1/4)+(-1+0)(1/4)+(-1+0)(1/4) = -1.
El valor de los estados finales no cambian, por que ya no necesita cambiar de estado cuando llegan a este.
Ahora teniendo esta nueva función de valor aplicaremos de nuevo el mismo proceso iterativo, tomando como ejemplo el mismo estado (0, 1) ahora veremos como cambia su valor de la siguiente manera, dado que tiene la misma probabilidad de tomar cualquier dirección: (-1+-1)(1/4)+(-1+-1)(1/4)+(-1+-1)(1/4)+(-1+0)(1/4) = -1.7
Ahora si seguimos iterando el proceso, se encontrará que llega a converger. En la parte derecha del gráfico se puede ver como sería una política codiciosa si se eligiera siempre el estado con mayor valor, lo cual demuestra que no es necesario iterar hasta el la convergencia para encontrar la política óptima y que observar la función de valor puede servirnos para encontrar una mejor política.
Iteración de Política
Todo parte de la premisa: ¿Como podríamos encontrar una mejor política a la que ya tenemos?
Para lograr esto se partirá el proceso en dos, dada la política π:
- Evaluamos la política π y encontramos su función de valor.
- Mejoras la política actuando ambiciosamente (seleccionas el estado que da más valor en cada paso) con respecto a la función de valor.
En el caso de el mundo de cuadrícula sólo se necesita una iteración sobre la política inicial para hallar la política óptima actuando ambiciosamente sobre esa función de valor, pero para otros problemas mas complejos se necesita muchas mas iteraciones y evaluaciones para llegar a una solución final.
Este procesos se repite una y otra vez hasta que la política deja de mejorar, en este caso habrá convergido en la política óptima, en realidad es un proceso iterativo que resulta al juntar la evaluación de una política y luego sobre esta evaluación se actúa ambiciosamente sobre su función de valor y luego se encuentra una mejor política (tambien llamada iteración de política), estas iteraciones se siguen dando hasta que se termina con la política óptima para ese problema.
Principio de Optimalidad
Cada política óptima puede dividirse en dos componentes:
- Elegir una primera acción óptima.
- Seguida por una política óptima desde el estado sucesor S’.
Esto se puede expresar en el teorema del principio de optimalidad, en el que se asegura que cualquier política optima puede alcanzar el valor optimo desde cualquier estado s que pueda ser alcanzado desde cualquier estado s’ y que se pueda comportar óptimamente dado cualquier estado s’.
Iteración de Valor
Se basa en que si sabemos la solución para el subproblema v*(s’), podemos hallar la solución de v*(s), la idea se basa en iniciar desde la recompensa final e ir retrocediendo para encontrar el valor óptimo de cada uno de los estados anteriores.
A continuación se verá un ejemplo de el mundo cuadrícula, el mismo que vimos en el ejemplo anterior, pero esta vez solo con una salida.
Para resolver este ejemplo se seleccionará la acción que nos de mayor valor, esto nos permitirá llegar a la función de valor óptima luego de iterar algunas veces. De nuevo iniciamos nuestro mundo cuadrícula con un valor arbitrario como se muestra en V1, en el siguiente paso se actualizan todos los estados, esta vez tomando la acción que maximice el valor, en este caso(V2) todas darían el mismo valor, para V3 la situación ya cambia, se puede notar los estados posicionados en (0,1) y (1,0) eligieron la acción de llegar al estado terminal, la cual termina siendo la acción mas óptima.
En las siguientes iteraciones se puede notar como cada estado va tomando la acción que maximiza su valor hasta llegar a converger en la función de valor óptima.
Para aterrizar un poco el uso de la iteración por valor tenemos que el objetivo final de esta es encontrar la política óptima π por medio de la aplicación iterativa de la ecuación de optimalidad de Bellman, si se decide detener el algoritmo en alguna iteración no final, puede ser que la función de valor que se encuentre en el algoritmo no sea necesariamente representada por alguna política, ya que la iteración de valor no se basa en ir iterando políticas si no ir alterando la función de valor, pero al final del funcionamiento de este algoritmo si tendremos claro que se ha encontrado la mejor función de valor que corresponde a la mejor política seleccionando cada vez la acción que genere mayor valor.
Algoritmos de Programación Dinámica Síncrona
Ahora un resumen de lo que hemos visto:
Implementación
Con esto concluimos el tema de programación dinámica, si hubiera alguna duda por favor déjala en los comentarios y espero haberte ayudado con este tema, sigue la serie de mis posts que pronto iré añadiendo más.
Muchas Gracias!!
