artificial-intelligence - deep q learning
¿Cuál es la diferencia entre Q-learning y SARSA? (5)
¿Cuál es la diferencia matemáticamente?
Como ya se describió en la mayoría de las demás respuestas, la diferencia entre las dos actualizaciones matemáticamente es, de hecho, que al actualizar el valor Q para un par de acciones de estado (S t , A t ) :
- Sarsa usa la política de comportamiento (es decir, la política utilizada por el agente para generar experiencia en el entorno, que típicamente 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 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 su lugar, 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í se puede ver como "seguir" la política completamente codiciosa. Sin embargo , el agente no está realmente siguiendo la política codiciosa ; solo dice, en la regla de actualización, "supongamos que comenzaría a seguir la política codiciosa a partir de ahora, ¿cuáles serían entonces mis retornos futuros esperados?".
¿Qué significa esto intuitivamente?
Como se menciona en otras respuestas, la diferencia descrita anteriormente significa, utilizando la terminología técnica, que Sarsa es un algoritmo de aprendizaje sobre políticas , y Q-learning es un algoritmo de aprendizaje fuera de la 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á a una solución óptima bajo la suposición de que seguimos la misma política que se utilizó para generar la experiencia . Esto a menudo será una política con algún elemento de aleatoriedad (más bien "estúpido"), como epsilon -greedy, porque de lo contrario no podemos garantizar que convergeremos a nada en absoluto.
- Q-Learning convergerá a una solución óptima bajo la suposición 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 generalmente preferible en situaciones en las que nos preocupamos por el rendimiento 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 precipicio. Preferimos que no se caiga demasiado seguido durante el proceso de aprendizaje, porque es costoso. Por lo tanto, nos preocupa su rendimiento durante el proceso de aprendizaje. Sin embargo, también sabemos que necesitamos actuar de forma aleatoria a veces (por ejemplo, épsilon-codicioso). Esto significa que es muy peligroso que el robot camine a lo largo del acantilado, ya que puede decidir actuar de forma aleatoria (con probabilidad de epsilon) y caerse. Por lo tanto, preferiríamos que aprendiéramos rápidamente que es peligroso estar cerca del acantilado; incluso si una política codiciosa pudiese caminar junto a ella sin caerse, sabemos que estamos siguiendo una política ávida de épsilon con aleatoriedad, y nos preocupamos por optimizar nuestro desempeño 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 preocupa el desempeño del agente durante el proceso de capacitación, pero solo queremos que aprenda una política codiciosa óptima a la que eventualmente cambiaremos. Considere, por ejemplo, que jugamos algunos juegos de práctica (donde no nos importa perder debido a la aleatoriedad a veces), y luego jugamos un torneo importante (donde dejaremos de aprender y cambiaremos de épsilon-codicioso a la codiciosa política ) Aquí es donde Q-learning sería mejor.
Aunque sé que SARSA está dentro de la política, mientras que el 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.
De acuerdo con el libro Reinforcement Learning: An Introduction (por Sutton y Barto). En el algoritmo SARSA, dada una política, la función de valor de acción correspondiente Q (en el estado s y la acción a, en timestep t), es decir, Q (s t , a t ), se puede actualizar de la siguiente manera
Q (s t , a t ) = Q (s t , a t ) + α * (r t + γ * Q (s t + 1 , a t + 1 ) - Q (s t , a 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 timestep t.
¿Es la diferencia entre estos dos algoritmos el hecho de que SARSA solo busca el siguiente valor de política, mientras que Q-learning busca el siguiente valor de política máximo ?
Cuando estaba aprendiendo esta parte, la encontré muy confusa también, así que reuní los dos pseudocódigos de R.Sutton y AGBarto 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, exploración NO).
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 la política.
Por el contrario, SARSA utiliza π todo el tiempo, por lo tanto, es un algoritmo de política.
Explicación más detallada :
La diferencia más importante entre los dos es cómo Q se actualiza después de cada acción. SARSA usa la Q ''siguiendo exactamente una política ε-codiciosa, ya que A'' se extrae de ella. Por el contrario, Q-learning utiliza la máxima Q ''sobre todas las acciones posibles para el siguiente paso. Esto hace que parezca seguir una política codiciosa con ε = 0, es decir NO exploración en esta parte.
Sin embargo, al realizar una acción, Q-learning todavía utiliza la acción tomada de una política de ε-codiciosos. Esta es la razón por la cual "Elegir A ..." está dentro del ciclo de repetición.
Siguiendo la lógica de bucle en Q-learning, A ''sigue siendo de la política ε-codicioso.
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 dijo, debe encontrar el valor Q máximo para la actualización eq. cambiando la a , entonces tendrá una nueva Q (St, At). CUIDADOSAMENTE, 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 St por St + 1 (St <- St + 1).
Para cada ciclo;
elija At from the St usando el valor Q
tomar At y observar Rt + 1 y St + 1
Actualiza el valor Q usando la ecuación.
St <- St + 1
Hasta que St sea terminal
Hay un error de índice en su fórmula para Q-Learning. Página 148 de Sutton y Barto''s.
Q (st, at) <- Q (st, at) + alfa * [r (t + 1) + gamma * max Q (st + 1, a) - Q (st, at)]
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.
Sí, esta es la única diferencia. La política SARSA aprende los valores de acción relativos a la política que sigue, mientras que Q-Learning fuera de la política lo hace en relación con la política codiciosa. Bajo algunas condiciones comunes, ambos convergen a la función de valor real, pero a diferentes velocidades. Q-Learning tiende a converger un poco más lento, pero tiene la capacidad de continuar aprendiendo al mismo tiempo que cambia 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 ε-codiciosa, Q-Learning calcula la diferencia entre Q (s, a) y el valor de acción máximo, 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 una Q (s t + 1 , a) + (1-ε) · max a Q (s t + 1 , a)