Aquí hay una explicación simple. Consideremos un proceso de decisión finito de Markov (MDP), con un espacio de estado finito S, un espacio de acción finito A, dinámica invariante en el tiempo P y una función de recompensa fija R.
La iteración de políticas encuentra la política óptima, que está asociada con la función de valor óptimo, en un número finito de iteraciones porque, en cada iteración, la política cambia cada vez a través de las fases gemelas de la evaluación de políticas y la mejora de políticas. Se puede demostrar que en un MDP finito, si la política actual aún no es óptima, hay una mejora “local” de la política actual que se descubrirá en el paso de mejora de la política. La prueba original está en la clásica tesis doctoral de Howard sobre MDP de 1959, una disertación histórica en este campo. La tesis de Howard también introdujo el algoritmo de iteración de políticas por primera vez, y también se centró en el caso de la recompensa promedio.
Recuerde que solo hay un número finito de políticas “estacionarias” en un MDP finito (es decir, un mapeo fijo de S a A) y, por lo tanto, si mejora la política en cada paso, debe converger en un número finito de pasos .
- ¿Qué tan buenas son las clases de aprendizaje profundo de Stanford?
- ¿Desde dónde comienzo el aprendizaje automático?
- ¿Cómo funciona el aprendizaje profundo y en qué se diferencia de las redes neuronales normales aplicadas con SVM?
- Después de aprender Python, ¿cómo aprendo el aprendizaje automático / IA?
- Si la IA reemplazara a los humanos, ¿seguirían interesados en encontrar vida en el universo?
Un tipo de prueba más sofisticado es introducir una métrica de distancia en funciones de valor en términos de algo llamado la “norma máxima” (la distancia entre dos funciones de valor es la mayor diferencia absoluta en valores entre V1 (s) y V2 (s), sobre todos los estados) Se puede demostrar que cada paso de la iteración de la política es una contracción en la norma máxima (es decir, la distancia entre la función de valor actual y la función óptima se reduce), a menos que ya haya descubierto la política óptima.
En el libro de Puterman sobre los procesos de decisión de Markov, así como las diversas “iteraciones” de los libros de Bertsekas sobre programación dinámica en las últimas tres décadas, se ofrece una discusión detallada del valor y la iteración de políticas.
Para el tratamiento más simple e intuitivo, recomiendo volver a la tesis de Howard. Él resuelve el problema del taxi en detalle, y siempre es refrescante para mí leer el documento original que introdujo una idea. Entonces, la tesis doctoral de Howard que introdujo el modelo MDP es, en mi humilde opinión, sin igual en este sentido.
