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[1] 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)[2].

Dunque SARSA è un algoritmo di apprendimento basato sul concetto di learning from interaction.

Questo va a significare che gli agenti imparano a migliorare le proprie azioni interagendo con l’ambiente circostante e ricevendo feedback sotto forma di ricompense. Quindi tramite l'esperienza si modificano le interazioni future.

SARSA tiene traccia dello stato corrente dell’ambiente, dell’azione intrapresa dall’agente, della ricompensa ricevuta, del prossimo stato raggiunto e dell’azione successiva scelta.[3]

Algoritmo

${\displaystyle 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.

Importanza di SARSA nel Reinforcement Learning

SARSA ha e riveste un assoluto ruolo cruciale nel reinforcement learning per diverse ragioni chiave:[4]

• Controllo della politica: SARSA è un algoritmo basato sul controllo della politica che consente agli agenti di apprendere le ottimali politiche tramite un processo di interazione con l’ambiente.
• Gestione delle azioni che verranno dopo: SARSA tiene conto delle azioni future selezionate dall’agente stesso, consentendo una migliore gestione delle scelte a lungo termine.
• Addestramento rimane stabile tramite gli agenti: SARSA favorisce un addestramento stabile degli agenti grazie all’utilizzo di una politica ε-greedy che bilancia in modo ottimale l'esplorazione e lo sfruttamento.
• Convergenza garantita: SARSA è garantito di convergere all’ottimalità sotto determinate condizioni, rendendolo affidabile per applicazioni reali.[5]

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.

Note

1. G. A. Rummery e M. Niranjan, On-Line Q-Learning Using Connectionist Systems, 1994. URL consultato il 7 aprile 2019.
2. 6.4 Sarsa: On-Policy TD Control, su incompleteideas.net. URL consultato il 7 aprile 2019.
3. Cos’è SARSA?, su riccardodebernardinis.com.
4. riccardodebernardinis.com, https://www.riccardodebernardinis.com/blog/sarsa-importanza-nel-reinforcement-learning/ Titolo mancante per url url (aiuto).
5. Importanza di SARSA nel Reinforcement Learning, su riccardodebernardinis.com.