2 - Evaluación de la política
Lección 2 del curso Aprendizaje por Refuerzo Nivel Intermedio.
Tabla de contenido
Introducción
En la lección anterior vimos una introducción a los Algoritmos Clásicos del Aprendizaje por Refuerzo, y allí hablamos de las tres grandes familias: la Programación Dinámica, los algoritmos Monte Carlo y los de Diferencias Temporales.
En esta lección comenzaremos a hablar de la primera familia de algoritmos clásicos: la Programación Dinámica, y nos enfocaremos específicamente en el primer algoritmo básico de esta familia: la evaluación de la política o la evaluación iterativa de la política.
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
Introducción a la Programación Dinámica
Los algoritmos de Programación Dinámica fueron desarrollados por el matemático Richard Bellman (el mismo de las Ecuaciones de Bellman) en los años 50s.
La idea general, como veremos al final de la lección, es que toman un problema relativamente complejo y para resolverlo lo dividen en sub-problemas más simples de resolver, introduciendo además un componente recursivo.
Como lo vimos en la lección anterior, estos algoritmos son el pilar sobre el cual posteriormente se desarrollaron otros métodos de Aprendizaje por Refuerzo más elaborados y más completos.
Recordemos también que el principal requerimiento de estos algoritmos es que se deben conocer todos los elementos del [Proceso de Decisión de Markov], incluyendo el modelo mismo del entorno.
Tipos de algoritmos de Programación Dinámica
En este curso veremos los 4 principales algoritmos que conforman la Programación Dinámica: la Evaluación de la Política (el tema de esta lección), la Mejora de la Política, la Iteración de la Política y la Iteración de Valores, estos tres últimos los veremos en lo que resta de esta sección del curso.
Recordemos que el objetivo del Aprendizaje por Refuerzo es lograr que el agente aprenda a tomar las mejores decisiones posibles al interactuar con el entorno, es decir que esto lo podríamos resumir como lograr encontrar la mejor política posible.
Pero para encontrar la mejor política posible primero debemos contar con una herramienta que nos permita cuantificar qué tan buena o mala es una política en particular, para luego sí poder determinar la mejor política para un entorno determinado.
Pues la Evaluación de la Política precisamente permite hacer esto, cuantificar la política. Por eso decimos que este algoritmo responde a una tarea de predicción: dada una política nos permite evaluar qué tan buena o mala es.
Por otra parte los tres algoritmos restantes (Mejora e Iteración de la Política y la Iteración de Valores), responden a una tarea de control, es decir encontrar la mejor política posible.
La Evaluación de la Política: generalidades
La idea de este algoritmo es muy sencilla: como entrada acepta una política y a la salida lo que arroja son los valores de la función estado-valor para cada uno de los estados en el Proceso de Decisión de Markov.
Es decir que en el fondo la Evaluación de la Política es simplemente un algoritmo que resuelve la Ecuación de Bellman para la función estado valor.
La Evaluación de la Política: principio de funcionamiento
Como lo mencionamos, la Evaluación de la Política permite calcular la función estado-valor. Y para hacer esto se debe conocer:
- La política (que es la entrada al algoritmo)
- Junto con todos los componente del Proceso de Decisión de Markov: los espacios de estados y de acciones, las funciones de transición y de recompensa y el descuento
En la Evaluación de la Política este cálculo de la función estado-valor para cada estado se hace de manera iterativa:
- En la primera iteración se inicializa en 0 el valor de cada estado. Si es un estado terminal, como en el caso del tablero bidimensional visto en el curso anterior, entonces siempre su valor será 0 independientemente de la iteración.
- En las iteraciones subsiguientes la estimación de cada valor se actualiza usando precisamente la Ecuación de Bellman
A medida que progresan las iteraciones cada valor se va refinando, y en teoría si tenemos un número infinito de iteraciones obtendremos la función estado-valor teórica (en la práctica se tiene un número finito de iteraciones, como veremos más adelante).
Así, al finalizar la ejecución del algoritmo tendremos para cada estado el valor asociado, que corresponde precisamente a la Evaluación de la Política.
La Evaluación de la Política: las ecuaciones
Para calcular la actualización de cada estado en cada iteración, se toma la Ecuación de Bellman para la función estado-valor y se usa como base para escribir la regla de actualización de cada estado.
Luego, en cada iteración el algoritmo actualiza el valor de cada estado según la Ecuación de Bellman, y los cálculos se detienen cuando la máxima variación entre uno y otro estado ha alcanzado el umbral definido inicialmente.
La Evaluación de la Política: utilidad
Teniendo claro el principio de funcionamiento del algoritmo podemos entender su utilidad, pues si tenemos dos políticas diferentes, podemos aplicar la Evaluación de la Política para cuantificar qué tan buena o mala es cada una de ellas y esto, como veremos en las próximas lecciones, nos permitirá precisamente determinar qué política funciona mejor para una interacción agente-entorno en particular.
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
Conclusión
Muy bien, ya tenemos el primer algoritmo de Programación Dinámica que permite de forma iterativa aproximar la función estado-valor para de esta manera cuantificar o evaluar una política.
Entonces, para comprender en su totalidad el funcionamiento del algoritmo, en la próxima lección veremos paso a paso un ejemplo práctico de Evaluación de la Política.