Tema

Iteración de valor

Aprendizaje por refuerzo
Nivel intermedio
Con simulador interactivo

La iteración de valor aplica repetidamente el operador de optimalidad de Bellman a una tabla de valores hasta que deja de cambiar, y extrae la política al final tomando en cada estado la acción de mayor valor.

Nombre en inglés

Value iteration

Intuición

Cada barrido propaga la información de las recompensas un paso hacia atrás, igual que una mancha que se extiende desde la meta. El operador es una contracción con factor igual al descuento, lo que garantiza que la distancia al valor óptimo se multiplique por ese factor en cada barrido y que exista un único punto fijo. Por eso no hace falta esperar a la convergencia exacta, ya que la política deja de cambiar mucho antes que los números.

Fórmula

V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a) [R(s, a, s') + \gamma V_k(s')] \qquad \lVert V_{k+1} - V^{*} \rVert_{\infty} \le \gamma \lVert V_k - V^{*} \rVert_{\infty}

Ejemplo resuelto

Sea un mundo de tres estados en línea. Desde A la acción derecha lleva a B y la acción quedarse deja en A, ambas sin recompensa. Desde B la acción derecha lleva a la meta M con recompensa 10 y la acción izquierda vuelve a A sin recompensa. La meta es terminal y el descuento vale 0.9. Se parte de todos los valores en cero. El primer barrido deja A en 0 y B en el máximo entre 10 y 0, es decir, 10. El segundo deja A en el máximo entre 0.9 por 0 y 0.9 por 10, es decir, 9, y B sigue en 10. El tercero deja A en el máximo entre 0.9 por 9 = 8.1 y 0.9 por 10 = 9, es decir, 9, de modo que nada cambia y el proceso termina. La política óptima elige derecha en los dos estados, con valores 9 y 10.

Errores frecuentes

Actualizar la tabla en el sitio y dar por hecho que el resultado coincide barrido a barrido con el de la versión sincrónica, cuando ambas convergen al mismo punto fijo pero por caminos distintos.
Extraer la política en cada barrido en lugar de al final, lo que cuesta tiempo sin cambiar el resultado.
Detener el bucle con un umbral sobre el cambio del valor sin traducirlo a una cota sobre la política, ya que ese cambio máximo hay que multiplicarlo por el descuento dividido entre 1 menos el descuento.

Ejercicio

En el mundo del ejemplo, ¿cuánto valdría el estado A si el descuento fuese 0.5?

Ver la solución

El valor de B no depende del descuento en este mundo, porque la acción derecha cobra 10 y lleva a un estado terminal, de modo que sigue valiendo 10. Desde A la mejor acción sigue siendo derecha y su valor es 0 más 0.5 por 10, es decir, 5. La impaciencia mayor reduce a la mitad lo que vale estar a un paso de distancia.