Como se sabe, la función de valor de estado de una política dada puede determinarse resolviendo una ecuación de Bellman:

Si se dispone de un modelo completo del entorno (es decir, se conocen las probabilidades de transición y las recompensas esperadas para todos los pares estado-acción), las únicas variables desconocidas que quedan en la ecuación son los valores de los estados. Por lo tanto, la ecuación anterior puede reformularse como un sistema de $|S|$ ecuaciones lineales con $|S|$ incógnitas.

Por ejemplo, si un MDP tiene 2 estados ($s_1$, $s_2$) y 2 acciones (moverse a $s_1$, moverse a $s_2$), la función de valor de estado podría definirse así:

Esto puede resolverse utilizando técnicas estándar de álgebra lineal.

Una solución única para este sistema lineal está garantizada si se cumple al menos una de las siguientes condiciones:

• El factor de descuento satisface $γ < 1$;
• La política $\pi$, al seguirse desde cualquier estado $s$, garantiza que el episodio eventualmente termina.

Evaluación Iterativa de Políticas

La solución puede calcularse directamente, pero se utiliza con mayor frecuencia un enfoque iterativo debido a su facilidad de implementación. Este método comienza asignando valores arbitrarios a todos los estados, excepto a los estados terminales, que se establecen en 0. Los valores se actualizan iterativamente utilizando la ecuación de Bellman como regla de actualización:

La función de valor de estado estimada $v_k$ finalmente converge a la verdadera función de valor de estado $v_\pi$ cuando $k \to \infty$ si $v_\pi$ existe.

Estrategias de Respaldo de Valores

Al actualizar las estimaciones de valor, las nuevas estimaciones se calculan en función de los valores anteriores. El proceso de conservar las estimaciones previas se conoce como respaldo. Existen dos estrategias comunes para realizar respaldos:

• Respaldo completo: este método implica almacenar las nuevas estimaciones en un arreglo separado, distinto del que contiene los valores anteriores (respaldados). Por lo tanto, se requieren dos arreglos: uno para mantener las estimaciones previas y otro para almacenar los valores recién calculados;
• Respaldo en el lugar: este enfoque mantiene todos los valores dentro de un solo arreglo. Cada nueva estimación reemplaza inmediatamente el valor anterior. Este método reduce el uso de memoria, ya que solo se necesita un arreglo.

Por lo general, se prefiere el método de respaldo en el lugar porque requiere menos memoria y converge más rápidamente, debido al uso inmediato de las estimaciones más recientes.

¿Cuándo detener la actualización?

En la evaluación iterativa de políticas, no existe un punto exacto en el que el algoritmo deba detenerse. Aunque la convergencia está garantizada en el límite, continuar los cálculos más allá de cierto punto es innecesario en la práctica. Un criterio de parada simple y efectivo es monitorear la diferencia absoluta entre estimaciones de valor consecutivas, $|v_{k+1}(s) - v_k(s)|$, y compararla con un umbral pequeño $\theta$. Si, después de un ciclo completo de actualización (donde se actualizan los valores de todos los estados), ningún cambio supera $\theta$, el proceso puede finalizarse de manera segura.

Pseudocódigo