Estado-Acción-Recompensa-Estado-Acción (SARSA)

Estado-acción-recompensa-estado-acción (SARSA) es un algoritmo para el aprendizaje de una política de proceso de decisión de Markov, utilizado en el área de aprendizaje de refuerzo del aprendizaje automático. Fue propuesto por Rummery y Niranjan en una nota técnica​ con el nombre de "Modified Connectionist Q-Learning" (Q-Learning conexionista modificado) (MCQ-L). El nombre alternativo SARSA, propuesto por Rich Sutton, sólo se mencionó como nota a pie de página.

Este nombre refleja el hecho de que la función principal para actualizar el valor Q depende del estado actual del agente "S₁", la acción que elige el agente "A₁", la recompensa "R₂" que obtiene el agente por elegir esta acción, el estado "S₂" en el que entra el agente después de realizar esa acción y, por último, la siguiente acción "A₂" que elige el agente en su nuevo estado. El acrónimo de la quíntuple (S_t, A_t, R_t+1, S_t+1, A_t+1) es SARSA.​ Algunos autores utilizan una convención ligeramente diferente y escriben la quíntuple (S_t, A_t, R_t, S_t+1, A_t+1), dependiendo del paso temporal en el que se asigne formalmente la recompensa. En el resto del artículo se utiliza la convención anterior.

Algoritmo

$Q^{new}(S_{t},A_{t})\leftarrow (1-\alpha )Q(S_{t},A_{t})+\alpha \,[R_{t+1}+\gamma \,Q(S_{t+1},A_{t+1})]$

Un agente SARSA interactúa con el entorno y actualiza la política en función de las acciones realizadas, por lo que se conoce como algoritmo de aprendizaje sobre política. El valor Q de un estado-acción se actualiza mediante un error, ajustado por el índice de aprendizaje α. Los valores Q representan la posible recompensa recibida en el siguiente paso temporal por realizar la acción a en el estado s, más la recompensa futura descontada recibida de la siguiente observación del estado-acción.

El Q-learning de Watkin actualiza una estimación de la función de valor óptimo estado-acción $Q^{*}$basado en la recompensa máxima de las acciones disponibles. Mientras que SARSA aprende por sí mismo los valores Q asociados a la adopción de la política que sigue, el Q-learning de Watkin aprende los valores Q asociados a la adopción de la política óptima mientras sigue una política de exploración/explotación.

Algunas optimizaciones del aprendizaje Q de Watkin pueden aplicarse a SARSA.​

Hiperparámetros

Tasa de aprendizaje (alfa)

El índice de aprendizaje determina hasta qué punto la información recién adquirida anula la antigua. Un factor 0 hará que el agente no aprenda nada, mientras que un factor 1 hará que el agente sólo tenga en cuenta la información más reciente.

Factor de descuento (gamma)

El factor de descuento determina la importancia de las recompensas futuras. Un factor de descuento de 0 hace que el agente sea "oportunista", o "miope", por ejemplo,​ ya que sólo tiene en cuenta las recompensas actuales, mientras que un factor cercano a 1 hará que se esfuerce por obtener una recompensa elevada a largo plazo. Si el factor de descuento es igual o superior a 1, el valor $Q$ pueden divergir.

Condiciones iniciales (Q(S₀, A₀))

Dado que SARSA es un algoritmo iterativo, asume implícitamente una condición inicial antes de que se produzca la primera actualización. Un valor inicial alto (infinito), también conocido como "condiciones iniciales optimistas",​ puede fomentar la exploración: no importa qué acción tenga lugar, la regla de actualización hace que tenga valores más altos que la otra alternativa, aumentando así su probabilidad de elección. En 2013 se sugirió que la primera recompensa $r$ podría utilizarse para restablecer las condiciones iniciales. Según esta idea, la primera vez que se realiza una acción, la recompensa se utiliza para fijar el valor de $Q$. Esto permite un aprendizaje inmediato en caso de recompensas deterministas fijas. Este enfoque de restablecimiento de las condiciones iniciales (RIC) parece ser coherente con el comportamiento humano en experimentos de elección binaria repetida.​

Véase también

• Q-learning
• Aprendizaje por diferencias temporales
• Aprendizaje por refuerzo