6 - Iteración de valores

Marzo 29, 2022 por Miguel Sotaquirá

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

Introducción

En el algoritmo de la iteración de la política que vimos en la lección anterior, logramos ver cómo obtener una política óptima repitiendo de forma iterativa los algoritmos de evaluación de la Política y mejora de la Política

En esta lección veremos una manera alternativa de obtener una Política Óptima, que en lugar de partir de la secuencia de Evaluación y Mejora, como lo hace el algoritmo de Iteración de la Política, lo hace directamente a partir de las funciones estado-valor y acción-valor. Hablaremos entonces de la Iteración de Valores.

Repaso: algoritmos de Programación Dinámica

Hasta este punto hemos visto tres algoritmos de la familia de la Programación Dinámica:

• La evaluación de la Política, que permite de forma iterativa obtener una aproximación a la [función estado-valor], lo que equivale precisamente a evaluar la Política del Agente.
• La mejora de la Política, que permite usar la función acción-valor para escoger la mejor acción posible para cada estado, logrando de esta manera mejorar la Política del Agente.
• La iteración de la Política, que combina de forma iterativa la evaluación y la mejora, para en últimas obtener una Política óptima para el agente.

Como veremos a continuación, el algoritmo de iteración de valores calcula de manera simultánea, es decir en el mismo bloque de iteraciones, la Evaluación y la Mejora, generando así una forma alternativa de obtener la Política Óptima.

Veamos en detalle cómo funciona.

Modificaciones al algoritmo de Iteración de la Política

A continuación vemos el algoritmo en detalle:

1. Entradas

   • Una Política arbitraria
   • Todos los elementos del [Proceso de Decisión de Markov] que describen el problema de Aprendizaje por Refuerzo, incluyendo el factor de descuento
   • El parámetro θ que controlará la convergencia del algoritmo de Evaluación de la Política

2. Iterar indefinidamente, y en cada iteración:

   2.1. Almacenar una copia de la política antes de modificarla

   2.2. Repetir hasta que haya convergencia

   2.3. Actualizar Q

   2.4. Mejorar la política

   2.5. Detener las iteraciones si no hay cambios en la política

Iteración de Valores: las ecuaciones

Como el algoritmo combina en un solo paso la evaluación y la mejora, resulta de hecho posible combinar estas dos ecuaciones de actualización de los valores en una sola.

Para ver esto partamos de las dos Ecuaciones de Bellman usadas durante la evaluación y la mejora.

Iteración de valores: el algoritmo

Teniendo en cuenta lo que acabamos de discutir, a continuación resumimos este algoritmo:

A continuación vemos el algoritmo en detalle:

1. Entradas

   • Una Política arbitraria
   • Todos los elementos del [Proceso de Decisión de Markov] que describen el problema de Aprendizaje por Refuerzo, incluyendo el factor de descuento
   • El parámetro θ que controlará la convergencia del algoritmo de Evaluación de la Política

2. Iterar indefinidamente, y por cada estado en cada iteración:

   2.1. Actualizar el valor del estado usando la ecuación de Bellman 2.2. Detenerse si hay convergencia

3. Obtener la política óptima a partir de la función estado-valor óptima obtenida en (2)

Conclusión

Muy bien, con este algoritmo de Iteración de Valores ya hemos visto los principales algoritmos que hacen parte de esta familia de la Programación Dinámica.

Así que ya estamos listos para comenzar con el componente práctico del curso. Entonces en la próxima lección veremos una introducción a OpenAI gym, una librería de Python que facilita la implementación de Algoritmos de Aprendizaje por Refuerzo.

Ver todas las lecciones de este curso