¿Cuál es la diferencia entre Q-learning y SARSA?

Cuando estaba aprendiendo esta parte, me pareció muy confuso también, así que junté los dos pseudo-códigos de R. Sutton y A. G. Barto con la esperanza de hacer la diferencia más clara.

Los cuadros azules resaltan la parte donde los dos algoritmos realmente difieren. Los números resaltan la diferencia más detallada que se explicará más adelante.

TL; NR :

|             | SARSA | Q-learning |
|:-----------:|:-----:|:----------:|
| Choosing A' |   π   |      π     |
| Updating Q  |   π   |      μ     |

Donde π es una política ε-codiciosa (por ejemplo, ε > 0 con exploración), y μ es una política codiciosa (por ejemplo, ε = = 0, SIN exploración).

1. Dado que Q-learning está utilizando diferentes políticas para elegir la siguiente acción A' y actualizar Q. En otras palabras, está tratando de evaluar π mientras sigue otra política μ, por lo que es un algoritmo fuera de política.

2. En contraste, SARSA usa π todo el tiempo, por lo tanto es un algoritmo de política.

Explicación Más detallada:

1. La diferencia más importante entre los dos es cómo Q es actualizado después de cada acción. SARSA utiliza la Q 'siguiendo una política ε-codiciosa exactamente, ya que A' se extrae de ella. En contraste, Q-learning utiliza el máximo Q ' sobre todas las acciones posibles para el siguiente paso. Esto hace que parezca que sigue una política codiciosa con ε = 0, es decir, NO hay exploración en esta parte.

2. Sin embargo, cuando realmente se toma una acción, Q-learning todavía utiliza la acción tomada de una política ε-greedy. Esta es la razón " Elegir A..."está dentro de la repetición bucle.

3. Siguiendo la lógica de bucle en Q-learning, A ' sigue siendo de la política ε-codiciosa.

Hay un error de índice en tu fórmula para Q-Learning. Página 148 de Sutton y Barto.

Q (st, at)

El error tipográfico está en el argumento de max:

Los índices son st + 1 y a, mientras que en su pregunta son st + 1 y at + 1 (estos son correctos para SARSA).

Espero que esto ayude un poco.

¿Cuál es la diferencia matemáticamente?

Como ya se describe en la mayoría de las otras respuestas, la diferencia entre las dos actualizaciones matemáticamente es que, al actualizar el Q - valor para un par estado-acción (S_t , A_t):

• Sarsa utiliza la política de comportamiento (es decir, la política utilizada por el agente para generar experiencia en el entorno, que normalmente es epsilon - greedy) para seleccionar una acción adicional A _t+1, y luego usa Q (S _t+1 , A _t+1) (descontado por gamma ) como rendimientos futuros esperados en el cálculo del destino de actualización.
• Q - el aprendizaje no utiliza la política de comportamiento para seleccionar una acción adicional A _t+1. En su lugar, estima los rendimientos futuros esperados en la regla de actualización como max_A Q(S_t+1, A). El operador max utilizado aquí puede verse como "siguiente" al política completamente codiciosa. El agente no está realmente siguiendo la política codiciosa, aunque; solo dice, en la regla de actualización, "supongamos que comenzaría a seguir la política codiciosa de ahora en adelante, ¿cuáles serían mis rendimientos futuros esperados entonces?".

¿Qué significa esto intuitivamente?

Como se mencionó en otras respuestas, la diferencia descrita anteriormente significa, utilizando terminología técnica, que Sarsa es un algoritmo de aprendizaje de políticas, y Q-learning es un algoritmo de aprendizaje fuera de política.

En el límite (dada una cantidad infinita de tiempo para generar experiencia y aprender), y bajo algunas suposiciones adicionales, esto significa que Sarsa y Q-learning convergen en diferentes soluciones / políticas "óptimas" :

• Sarsa convergerán a una solución óptima bajo el supuesto de que seguimos con la misma política que se utilizó para generar la experiencia. Esto a menudo será un política con algún elemento de aleatoriedad (más bien "estúpido"), como epsilon-codicioso, porque de lo contrario no podemos garantizar que convergeremos a nada en absoluto.
• Q-Learning convergerá hacia una solución óptima bajo el supuesto de que, después de generar experiencia y capacitación, cambiamos a la política codiciosa .

¿Cuándo usar qué algoritmo?

Un algoritmo como Sarsa es normalmente preferible en situaciones en las que nos preocupamos por el desempeño del agente durante el proceso de aprendizaje / generación de experiencia. Considere, por ejemplo, que el agente es un robot caro que se romperá si cae por un acantilado. Preferimos que no se caiga demasiado a menudo durante el proceso de aprendizaje, porque es caro. Por lo tanto, nos preocupamos por su rendimiento durante el proceso de aprendizaje. Sin embargo, también sabemos que necesitamos que actúe al azar a veces (por ejemplo, epsilon-greedy). Esto significa que es muy peligroso para el robot caminar a lo largo del acantilado, ya que puede decidir actuar al azar (con probabilidad epsilon) y caer. Por lo tanto, preferiríamos aprender rápidamente que es peligroso estar cerca del acantilado; incluso si una política codiciosa sería capaz de caminar a su lado sin caer, sabemos que estamos siguiendo una política épsilon-codiciosa con aleatoriedad, y nos preocupamos por optimizar nuestro rendimiento dado que sabemos que seremos estúpidos a veces. Esta es una situación en la que Sarsa sería preferible.

Un algoritmo como Q-learning sería preferible en situaciones en las que no nos importa el rendimiento del agente durante el proceso de entrenamiento, pero solo queremos que aprenda una política codiciosa óptima a la que cambiaremos eventualmente. Consideremos, por ejemplo, que jugamos algunos juegos de práctica (donde no nos importa perder debido al azar a veces), y después jugamos un torneo importante (donde dejaremos de aprender y cambiar de epsilon-codicioso a la política codiciosa). Aquí es donde Q-learning sería mejor.

En Q-Learning

Esta es su: Q-Aprendizaje: Q (St, At) = Q (St,At) + a [ R(t+1) + descuento * max Q (St+1, At ) - Q (St, At)]

Debe cambiarse a Q-Aprendizaje: Q (St, At) = Q (St,At) + a [ R (t+1) + descuento * max Q (St + 1, a ) - Q (St, At)]

Como has dicho, tienes que encontrar el valor Q máximo para el eq de actualización. cambiando la a , entonces tendrás una nueva Q(St,At). CON cuidado, el a que le da el valor Q máximo no es la siguiente acción. En esta etapa, solo conoce el siguiente estado (St + 1), y antes de pasar a la siguiente ronda, desea actualizar el St por el St+1 (St

Para cada bucle;

• Elija At desde el St usando el valor Q

• Tomar y observar Rt + 1 y St+1

• Actualizar Q-value usando la eq.

• St

Hasta que St sea terminal