SARSA

Le nom SARSA signifie Etat-Action-Récompense-Etat-Action (en anglais State-Action-Reward-State-Action) qui est la suite des éléments mathématiques considérés par l'algorithme :

• l'algorithme considère l'état courant s (par exemple, la position d'un robot dans un environnement et la position de ses bras)
• puis il choisit une action à exécuter en fonction de ce qu'il a déjà appris, mais aussi un biais d'exploration pour éveiller sa curiosité et essayer des actions non préconisées. Il exécute cette action
• il reçoit alors une récompense r. Par exemple, si le robot est toujours en vie, on peut décider de lui une récompense de 1€, alors que s'il tombe, il perd 100€ (i.e. une récompense négative de -100€)
• il perçoit le nouvel état s' (par exemple, sa nouvelle position)
• il choisit la nouvelle action a' exécuter

La mise à jour de ses valeurs internes tient compte de valeur Q(s', a') et Q(s, a) et la récompense r. On dit que SARSA est un algorithme on-policy car la mise à jour tient compte en particulier de Q(s', a'), où a' a été choisi par la politique en cours d'apprentissage.

Voici le pseudo-code de l'algorithme SARSA. Dans cet algorithme, l'objectif est de calculer un tableau Q où Q(s, a) désigne la valeur sur le long terme estimée d'exécuter l'action a dans l'état s. La politique que l'agent exécute une fois qu'il a appris Q est donnée à partir de ces valeurs Q(s, a). Plus précisément, dans l'état s, il choisit d'exécuter l'action a qui maximise Q(s, a). Voici le pseudo-code l'algorithme SARSA.

entrée : taux d'apprentissage α > 0 et un petit ε > 0, taux γ > 0
sortie : tableau Q[., .]
initialiser Q[s, a] pour tout état s non final, pour toute action a de façon arbitraire, 
         et Q(état terminal, a) = 0 pour tout action a
répéter
      //début d'un épisode
      s := état initial
      choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy)
      répéter
               //étape de l'épisode
               exécuter l'action a
               observer la récompense r et le nouvel état s'
               choisir une action a' depuis s' en utilisant la politique spécifiée par Q (par exemple ε-greedy)
               Q[s, a] := Q[s, a] + α[r + γQ(s', a') - Q(s, a)]
               s := s'
               a := a'
      jusqu'à ce que s soit l'état terminal 

L'algorithme commence par initialiser le tableau Q de façon arbitraire, sauf pour l'état terminal où la valeur vaut 0 pour toute action. L'algorithme réalise alors plusieurs épisodes, autrement dit, il part d'un état s jusqu'à un état terminal. Le nombre d'épisodes effectué est laissé au choix. Durant l'épisode, l'algorithme choisit l'action a à exécuter en fonction du tableau Q courant. Généralement, on choisit a de la façon suivante :

• avec une probabilité ε, on choisit une action au hasard
• avec une probabilité 1-ε, on choisit l'action a qui maximise Q(s, a)

On réalise alors la mise à jour de Q[s, a] de la façon suivante :

Q[s, a] := Q[s, a] + α[r + γQ(s', a') - Q(s, a)]

que l'on peut aussi écrire

Q[s, a] := (1-α)Q[s, a] + α[r + γQ(s', a')].

Dans l'expression précédente, α est le facteur d'apprentissage qui exprime un compromis (une combinaison linéaire) entre :

• (α = 0) rien apprendre du tout, i.e. Q[s, a] := Q[s, a]
• (α = 1) apprendre en oubliant ce que l'on a déjà appris, i.e. Q[s, a] = r + γQ(s', a')

L'expression r + γQ(s', a') représente la valeur de récompense courante r, à laquelle on additionne la valeur d'être en s' et d'exécuter a', pondérée par γ.

L'algorithme précédent manipule les états de manière explicite. Le problème est que le nombre d'états est souvent important en pratique, qui rend le stockage de Q impossible. C'est pourquoi on considère une approximation de la fonction ${\displaystyle (s,a)\mapsto Q(s,a)}$. Cette approximation est représentée par une expression ${\displaystyle q(s,a,\omega )}$ où s est l'état, a l'action, et ${\displaystyle \omega }$ est un vecteur de poids. Le vecteur ${\displaystyle \omega }$ contient les paramètres de ${\displaystyle q(s,a,\omega )}$. A chaque valeur de ${\displaystyle \omega }$, correspond une fonction ${\displaystyle (s,a)\mapsto q(s,a,\omega )}$. On donne ici la version de SARSA donnée page 244 de [1].

La mise à jour générale de la descente de gradient pour la prédiction de la valeur d'action est :

${\displaystyle \omega _{t+1}:=\omega _{t}+\alpha [U_{t}-q(s_{t},a_{t},\omega _{t})]\nabla q(s_{t},a_{t},\omega _{t})}$ avec ${\displaystyle U_{t}}$ la valeur à mettre à jour.

Cela forme la partie de prédiction de la valeur d'action, et pour le contrôle, nous devons coupler cela aux techniques d'amélioration des politiques et de sélection des actions.

Cette estimation est utile dans les cas d'actions continues, ou des grands sets discrets de d'actions.

entrée : fonction action-valeur de paramétrisation q, taux d'apprentissage α > 0 et un petit ε > 0, un taux γ > 0
sortie : vecteur w qui représente une fonction q
Initialisation des poids action-valeur w aléatoirement
pour chaque épisode
      initialiser l'état s et l'action a (avec politique ε-greedy)
      pour chaque étape de l'épisode
               exécuter l'action a
               observer la récompense r et l'état s'
               si s' est terminal :
                          w := w + α[R - q(s, a, w)] ${\displaystyle \nabla }$q(s, a, w)
                          aller à l'épisode suivant
               choisir une action a' depuis q(s', ., w)
                 en utilisant la politique spécifiée par q(par exemple ε-greedy)
               w := w + α[R + γq(s', a', w) - q(s, a, w)] ${\displaystyle \nabla }$q(s, a, w)
               s := s'
               a := a'
      jusqu'à ce que s soit l'état terminal

• L'algorithme SARSA est on-policy : la politique apprise est la même que celle utilisée pour faire les choix des actions à exécuter. Un algorithme proche est le Q-learning, mais qui off-policy.
• L'algorithme de type TD : on utilise l'état suivant s' pour mettre à jour la valeur en l'état courant s.