SARSA

Lo stato–azione–ricompensa–stato–azione (SARSA) è un algoritmo di apprendimento di una funzione di policy per i processi decisionali di Markov, usato nelle aree dell'apprendimento per rinforzo e dell'apprendimento automatico. Fu proposto da Rummery e Niranjan col nome di "Modified Connectionist Q-Learning" (MCQ-L). L'acronimo alternativo e con cui oggi è più noto l'algoritmo, SARSA, fu proposto da Rich Sutton.

Questo acronimo, infatti, sta a indicare che la funzione principale di aggiornamento dei valori di Q dipende esclusivamente dallo stato attuale s_t, dall'azione a_t che l'agente sceglie, dalla ricompensa r_t, dallo stato s_t+1 in cui si entra dopo aver effettuato a_t e dall'azione a_t+1 che l'agente sceglie nel nuovo stato; formalmente, quindi, SARSA rappresenta la quintupla (s_t, a_t, r_t, s_t+1, a_t+1).

Algoritmo

$Q(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})+\alpha [r_{t}+\gamma Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t})]$

L'agente interagisce con l'ambiente e aggiorna la sua funzione di comportamento basandosi sulle azioni prese e per questo motivo viene considerato un algoritmo di apprendimento on-policy. Il valore della funzione Q per una coppia stato-azione (s_t,a_t) viene aggiornato calcolando una funzione di errore e tenendo conto del tasso di apprendimento alfa. I valori della funzione Q rappresentano il valore atteso della ricompensa all'iterazione successiva, eseguendo l'azione a_t sullo stato corrente s_t; questo valore viene sommato alla ricompensa futura, quella ottenuta eseguendo a_t+1 su s_t+1 ed è possibile pesare il contributo di questa ricompensa attraverso il fattore di sconto gamma.

Iperparametri

Tasso di apprendimento α

Cambiando il valore del tasso di apprendimento è possibile modificare il contributo dell'errore stimato a ogni iterazione: un fattore pari a 0 equivale a non apprendere nulla, mentre con un valore di alfa uguale a 1 si considera solo l'osservazione più recente.

Fattore di sconto γ

Il fattore di sconto determina l'importanza delle ricompense future. Un valore di gamma uguale a 0 rende l'agente "opportunista", in quanto considera solo la ricompensa attuale r; al contrario, un valore di gamma prossimo a 1 permette di cercare ricompense anche a lungo termine. Per valori maggiori di 1 i valori di Q possono divergere.