Tema

Iteración de política

Aprendizaje por refuerzo
Nivel intermedio

La iteración de política alterna un paso de evaluación, que calcula el valor de la política actual, con un paso de mejora, que fija en cada estado la acción de mayor valor, y se detiene cuando la política no cambia.

Nombre en inglés

Policy iteration

Intuición

En vez de mejorar los números poco a poco como hace la iteración de valor, se resuelve del todo el valor de una política y después se da un salto a otra política mejor. Como el número de políticas es finito y cada salto mejora de forma estricta salvo al final, el proceso termina en pocas rondas. Cada evaluación cuesta más, pero suelen bastar dos o tres rondas frente a decenas de barridos.

Fórmula

V^{\pi}(s) = \sum_{s'} P(s' \mid s, \pi(s)) [R + \gamma V^{\pi}(s')] \qquad \pi'(s) = \arg\max_a \sum_{s'} P(s' \mid s, a) [R + \gamma V^{\pi}(s')]

Ejemplo resuelto

En el mundo de tres estados con descuento 0.9, se parte de la política que elige derecha en A e izquierda en B. La evaluación plantea el valor de A igual a 0.9 por el de B y el de B igual a 0.9 por el de A, sistema cuya única solución deja ambos en cero. La mejora compara en B la acción derecha, que vale 10, con la izquierda, que vale 0, y cambia a derecha; en A ambas acciones valen 0 y se conserva derecha. La segunda evaluación da 10 en B y 0.9 por 10 = 9 en A. La segunda mejora confirma derecha en los dos estados, ya que en A la derecha vale 9 frente a 8.1 de quedarse, de modo que el ciclo termina con la misma solución que la iteración de valor pero con dos evaluaciones en lugar de tres barridos.

Errores frecuentes

Evaluar la política con un solo barrido y llamar a eso iteración de política clásica, cuando esa variante es la iteración truncada y la clásica resuelve el sistema hasta el final.
Cambiar la política en la mitad de los estados y olvidar reevaluar, lo que mezcla valores de dos políticas distintas.
Creer que la política puede empeorar en algún paso, cuando el teorema de mejora garantiza que el valor no baja en ningún estado.

Ejercicio

Una política fija recibe siempre recompensa 1 por paso en un único estado que se repite, con un descuento de 0.9. ¿Qué valor le asigna la evaluación?

Ver la solución

La ecuación de evaluación es el valor igual a 1 más 0.9 por el propio valor. Al despejar queda el valor menos 0.9 por el valor igual a 1, es decir, 0.1 por el valor igual a 1, de donde el valor es 10.

Respuesta: 10