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

94

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?

Arslán
fuente
13
Habría sido más apropiado hacer esta pregunta en sitios web como ai.stackexchange.com , stats.stackexchange.com o datascience.stackexchange.com .
nbro

Respuestas:

124

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 .

ingrese la descripción de la imagen aquí 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.

zyxue
fuente
3
Estoy de acuerdo en que la iteración de políticas converge en menos iteraciones y también he leído en varios lugares que es más rápida. Hice algunos experimentos sencillos de resolución de laberintos y el mundo de las cajas con ambos métodos en Burlap. Descubrí que la iteración de valor realizó más iteraciones, pero tomó menos tiempo para alcanzar la convergencia. YMMV.
Ryan
1
@Chrom, deberías haber leído lo contrario. Aquí hay una cita del libro, " La iteración de políticas a menudo converge en sorprendentemente pocas iteraciones. Esto se ilustra con el ejemplo de la Figura 4.1. ", De la página 65 de la versión 2017nov5 del libro.
zyxue
3
Sí, he jugado con varios sabores del mundo Grid. Solo estaba tratando de señalar que "más rápido" en términos de iteraciones probablemente favorecerá a PI. Pero "más rápido" en términos de segundos en realidad podría favorecer a VI.
Ryan
3
Para aclarar, la iteración de políticas requerirá menos iteraciones pero es más compleja computacionalmente que la iteración de valor; cuál es más rápido depende del medio ambiente.
RF Nelson
2
Sé que esta es una publicación antigua. Pero recomiendo encarecidamente que investigue esto ( medium.com/@m.alzantot/… ) El enlace proporciona un código y lo hizo mucho más claro para mí.
tándem
73

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.

Pablo EM
fuente
1
Buena descripción de esto. Bueno, permítanme agregar esto en la iteración de políticas, usa la ecuación de expectativa de Belman y en la iteración de valor usa la ecuación de máximo de Melman. Para la iteración de valor, puede haber menos iteraciones, pero para una iteración puede haber mucho trabajo. Para la iteración de políticas, más iteraciones
Shamane Siriwardhana
¿No hay también un operador máximo en la iteración de políticas? de lo contrario, ¿cómo actualizar la política en función de la nueva función de valor?
huangzonghao
No, el algoritmo SARSA es un ejemplo típico de iteración de políticas. Como puede ver en este pseudocódigo ( incompleteideas.net/book/ebook/node64.html ), la actualización de la función de valor no contiene ningún operador máximo. Sin embargo, si te refieres a un operador máximo para elegir las mejores acciones de la función de valor (es decir, acciones codiciosas), sí, hay una operación máxima en dicho proceso.
Pablo EM
11

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”.

Himanshu Gupta
fuente
0

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.

Respuesta777
fuente