¿Cuál es la diferencia entre iteración de valor e iteración de política?

En el aprendizaje por refuerzo, ¿cuál es la diferencia entre la iteración de políticas y la iteración de valores ?

Por lo que tengo entendido, en la iteración de valor, utiliza la ecuación de Bellman para resolver la política óptima, mientras que, en la iteración de política, selecciona aleatoriamente una política π y encuentra la recompensa de esa política.

Mi duda es que si está seleccionando una política aleatoria π en PI, ¿cómo se garantiza que será la política óptima, incluso si estamos eligiendo varias políticas aleatorias?

Veámoslos uno al lado del otro. Se destacan las partes clave para la comparación. Las cifras son del libro de Sutton y Barto: Reinforcement Learning: An Introduction .

Puntos clave:

1. La iteración de políticas incluye: evaluación de políticas + mejora de políticas , y las dos se repiten de forma iterativa hasta que la política converge.
2. La iteración de valor incluye: encontrar la función de valor óptimo + una extracción de política . No hay repetición de los dos porque una vez que la función de valor es óptima, entonces la política a partir de ella también debería ser óptima (es decir, convergente).
3. Encontrar la función de valor óptimo también se puede ver como una combinación de mejora de la política (debido al máximo) y evaluación de la política truncada (la reasignación de v_ (s) después de un solo barrido de todos los estados independientemente de la convergencia).
4. Los algoritmos para la evaluación de políticas y la función de búsqueda de valor óptimo son muy similares, excepto por una operación máxima (como se resalta)
5. De manera similar, el paso clave para la mejora de políticas y la extracción de políticas son idénticos, excepto que el primero implica un control de estabilidad.

En mi experiencia, la iteración de políticas es más rápida que la iteración de valores , ya que una política converge más rápidamente que una función de valor. Recuerdo que esto también se describe en el libro.

Supongo que la confusión provino principalmente de todos estos términos algo similares, que también me confundieron antes.

En los algoritmos de iteración de políticas , comienza con una política aleatoria, luego encuentra la función de valor de esa política (paso de evaluación de la política), luego encuentra una política nueva (mejorada) basada en la función de valor anterior, y así sucesivamente. En este proceso, se garantiza que cada póliza será una mejora estricta sobre la anterior (a menos que ya sea óptima). Dada una política, su función de valor se puede obtener utilizando el operador Bellman .

En la iteración de valor , comienza con una función de valor aleatorio y luego encuentra una función de valor nueva (mejorada) en un proceso iterativo, hasta alcanzar la función de valor óptimo. Observe que puede derivar fácilmente la política óptima a partir de la función de valor óptimo. Este proceso se basa en la optimización del operador Bellman .

En cierto sentido, ambos algoritmos comparten el mismo principio de funcionamiento y pueden verse como dos casos de la iteración de política generalizada . Sin embargo, el operador de Optimality Bellman contiene un operador max , que no es lineal y, por lo tanto, tiene características diferentes. Además, es posible utilizar métodos híbridos entre la iteración de valor puro y la iteración de política pura.

La diferencia básica es:

En Iteración de políticas : selecciona aleatoriamente una política y encuentra la función de valor correspondiente, luego encuentra una política nueva (mejorada) basada en la función de valor anterior, y así sucesivamente esto conducirá a una política óptima.

En iteración de valor : selecciona aleatoriamente una función de valor, luego encuentra una función de valor nueva (mejorada) en un proceso iterativo, hasta alcanzar la función de valor óptima, luego deriva la política óptima de esa función de valor óptima.

La iteración de políticas funciona según el principio de "Evaluación de políticas -> Mejora de políticas".

La iteración de valor funciona según el principio de “función de valor óptimo -> política óptima”.

En lo que a mí respecta, al contrario de la idea de @zyxue, VI es generalmente mucho más rápido que PI.

La razón es muy sencilla, como ya sabía, la ecuación de Bellman se usa para resolver la función de valor para una política determinada. Dado que podemos resolver la función de valor para la política óptima directamente , resolver la función de valor para la política actual es obviamente una pérdida de tiempo.

En cuanto a su pregunta sobre la convergencia de PI, creo que podría pasar por alto el hecho de que si mejora la estrategia para cada estado de información, entonces mejora la estrategia para todo el juego. Esto también es fácil de demostrar, si estuviera familiarizado con la Minimización del arrepentimiento contrafáctico: la suma del arrepentimiento para cada estado de información ha formado el límite superior del arrepentimiento general, y por lo tanto, minimizar el arrepentimiento para cada estado minimizará el arrepentimiento general, que conduce a la política óptima.