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

Aunque sé que SARSA está dentro de la política mientras que Q-learning está fuera de la política, al mirar sus fórmulas es difícil (para mí) ver alguna diferencia entre estos dos algoritmos.

Según el libro Reinforcement Learning: An Introduction (de Sutton y Barto). En el algoritmo SARSA, dada una política, la función de valor de acción correspondiente Q (en el estado sy la acción a, en el paso de tiempo t), es decir, Q (s _t , a _t ), se puede actualizar de la siguiente manera

Q (s _t , una _t ) = Q (s _t , una _t ) + α * (r _t + γ * Q (s _{t + 1} , una _{t + 1} ) - Q (s _t , una _t ))

Por otro lado, el paso de actualización para el algoritmo Q-learning es el siguiente

Q (s _t , a _t ) = Q (s _t , a _t ) + α * (r _t + γ * max _a Q (s _{t + 1} , a) - Q (s _t , a _t ))

que también se puede escribir como

Q (s _t , a _t ) = (1 - α) * Q (s _t , a _t ) + α * (r _t + γ * max _a Q (s _{t + 1} , a))

donde γ (gamma) es el factor de descuento y r _t es la recompensa recibida del entorno en el paso de tiempo t.

¿La diferencia entre estos dos algoritmos es el hecho de que SARSA solo busca el siguiente valor de política mientras Q-learning busca el siguiente valor máximo de política?

TLDR (y mi propia respuesta)

Gracias a todos los que respondieron esta pregunta desde la primera vez que la hice. Hice un repositorio de github jugando con Q-Learning y entendí empíricamente cuál es la diferencia. Todo se reduce a cómo selecciona su próxima mejor acción , que desde un punto de vista algorítmico puede ser una acción media , máxima o mejor , según cómo elija implementarla.

La otra diferencia principal es que esta selección está ocurriendo (por ejemplo, en línea vs fuera de línea ) y cómo / por qué eso afecta el aprendizaje. Si está leyendo esto en 2019 y es más una persona práctica, jugar con un problema de juguetes RL es probablemente la mejor manera de comprender las diferencias.

Una última nota importante es que tanto Suton & Barto como Wikipedia a menudo tienen representaciones de fórmulas mixtas, confusas o incorrectas con respecto a la acción y recompensa mejor / máxima del siguiente estado :

r (t + 1)

es de hecho

r (t)

Espero que esto ayude a cualquiera a quedarse atascado en esto.

Sí, esta es la única diferencia. Dentro de la política SARSA aprende valores de acción en relación con la política que sigue, mientras que Q-Learning fuera de la política lo hace en relación con la política codiciosa. En algunas condiciones comunes, ambos convergen a la función de valor real, pero a velocidades diferentes. Q-Learning tiende a converger un poco más lento, pero tiene la capacidad de continuar aprendiendo mientras se cambian las políticas. Además, no se garantiza que Q-Learning converja cuando se combina con la aproximación lineal.

En términos prácticos, bajo la política ε-codicioso, Q-Learning calcula la diferencia entre Q (s, a) y el valor máximo de acción, mientras que SARSA calcula la diferencia entre Q (s, a) y la suma ponderada de la acción promedio valor y el máximo:

Q-Learning: Q (s _{t + 1} , a _{t + 1} ) = max _a Q (s _{t + 1} , a)

SARSA: Q (s _{t + 1} , a _{t + 1} ) = ε · significa _a Q (s _{t + 1} , a) + (1-ε) · max _a Q (s _{t + 1} , a)

Cuando estaba aprendiendo esta parte, también la encontré muy confusa, así que reuní los dos pseudocódigos de R.Sutton y AGBarto con la esperanza de hacer la diferencia más clara.

Los recuadros azules resaltan la parte en la que 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, NO exploración).

1. Dado que Q-learning está usando 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 la política.

2. Por el contrario, SARSA utiliza π todo el tiempo, por lo que es un algoritmo de política.

Explicación más detallada :

1. La diferencia más importante entre los dos es cómo se actualiza Q después de cada acción. SARSA usa la Q 'siguiendo exactamente una política ε-codiciosa, como A' se extrae de ella. Por el contrario, 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 usa la acción tomada de una política ε-codiciosa. Es por eso que "Choose A ..." está dentro del ciclo de repetición.

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

¿Cuál es la diferencia matemáticamente?

Como ya se describe en la mayoría de las otras respuestas, la diferencia matemática entre las dos actualizaciones es de hecho que, al actualizar el valor Q 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 suele ser épsilon- codicioso) para seleccionar una acción adicional A _{t + 1} , y luego usa Q (S _{t + 1} , A _{t +1} ) (descontado por gamma ) como retornos futuros esperados en el cálculo del objetivo de actualización.
• Q -learning no usa la política de comportamiento para seleccionar una acción adicional A _{t + 1} . En cambio, estima los rendimientos futuros esperados en la regla de actualización como max _A Q (S _{t + 1} , A) . El operador máximo utilizado aquí puede verse como "siguiendo" la política completamente codiciosa. Sin embargo , el agente no sigue realmente la política codiciosa ; sólo dice, en la regla de actualización, "supongamos que empezaría a seguir la política codiciosa de ahora en adelante, ¿cuáles serían entonces mis retornos futuros esperados?".

¿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 dentro de las políticas y Q-learning es un algoritmo de aprendizaje fuera de las políticas .

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

• Sarsa convergerá hacia una solución óptima bajo el supuesto de que seguimos siguiendo la misma política que se utilizó para generar la experiencia . Esta será a menudo una política con algún elemento de aleatoriedad (bastante "estúpida"), como épsilon- codicioso, porque de lo contrario no podemos garantizar que convergiremos a algo en absoluto.
• Q-Learning convergerá en una solución óptima bajo el supuesto de que, después de generar experiencia y capacitación, pasamos a la política codiciosa .

¿Cuándo usar qué algoritmo?

Un algoritmo como Sarsa suele ser 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 con demasiada frecuencia durante el proceso de aprendizaje, porque es caro. Por eso, nos preocupamos por su desempeño durante el proceso de aprendizaje. Sin embargo, también sabemos que necesitamos que actúe de forma aleatoria a veces (por ejemplo, épsilon-codicioso). Esto significa que es muy peligroso para el robot caminar junto al acantilado, ya que puede decidir actuar al azar (con probabilidad épsilon) y caer. Por lo tanto, preferimos que aprenda rápidamente que es peligroso estar cerca del acantilado;Incluso si una política codiciosa pudiera caminar junto a ella sin caer, sabemos que estamos siguiendo una política de codicia épsilon con aleatoriedad, y nos preocupamos por optimizar nuestro rendimiento dado que sabemos que a veces seremos estúpidos . 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 desempeño del agente durante el proceso de entrenamiento, pero solo queremos que aprenda una política de codicia óptima a la que cambiaremos eventualmente. Considere, por ejemplo, que jugamos algunos juegos de práctica (en los que a veces no nos importa perder debido a la aleatoriedad), y luego jugamos un torneo importante (donde dejaremos de aprender y cambiaremos de épsilon-codicioso a la política codiciosa ). Aquí es donde Q-learning sería mejor.

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

Q (st, en) <- Q (st, en) + alfa * [r (t + 1) + gamma * max Q (st + 1, a) - Q (st, en)]

El error tipográfico está en el argumento del máximo:

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

Espero que esto ayude un poco.

En Q-Learning

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

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

Como dijiste, debes encontrar el valor Q máximo para la ecuación de actualización. al cambiar la a , tendrás una nueva Q (St, At). CUIDADOSAMENTE, la 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 St por St + 1 (St <- St + 1).

Para cada bucle;

• elija At de St usando el valor Q

• tomar At y observar Rt + 1 y St + 1

• Actualice el valor Q usando la ecuación.

• St <- St + 1

Hasta que St sea terminal

La única diferencia entre SARSA y Qlearning es que SARSA toma la siguiente acción según la política actual, mientras que qlearning toma la acción con la máxima utilidad del próximo estado.