Model-free Policy Iteration with TD :  SARSA

In questo caso, in ottica di controllo, si procederà in modo simile a quanto già visto, inizializzando una policy \(\pi\)  e iterando valutazione, per calolare \(Q^\pi\) utilizzando TD aggiornata con la \(\epsilon\)-greedy policy, e miglioramento, come nel caso del MC policy improvement ponendo \(\pi=\epsilon\text{-greedy}(Q^\pi)\)

L'algoritmo SARSA calcola una stima di Q della policy utilizzata per agire

• Imposta la politica \(\varepsilon\)-greedy iniziale \(\pi\), \(t = 0\), stato iniziale \(s_t = s_0\)
• Seleziona \(a_t \sim \pi(s_t)\) // Azione campionata dalla politica
• Osserva \((r_t, s_{t+1})\)
• loop
  • Esegui l’azione \(a_{t+1} \sim \pi(s_{t+1})\)
  • Osserva \((r_{t+1}, s_{t+2})\)
  • Aggiorna la funzione Q: \(Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \big(r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\big)\)
  • Aggiorna la politica: \(\pi(s_t) = \arg\max_a Q(s_t, a)\) con probabilità \(1 - \varepsilon\), altrimenti azione casuale
  • Aggiorna il time step: \(t = t + 1\)
  • Aggiorna \(\varepsilon = 1/t\)
• end loop

Vediamo che in questo caso abbiamo un target  \(r_t + \gamma Q(s_{t+1}, a_{t+1})\)   on-policy per l'aggiornamento di \(Q(s_t, a_t)\)  poichè utilizza il vero stato e la vera azione che otterremo seguendo la policy utilizzata. Chiaramente se \(s_{t+2}\) è uno stato finale si resetta l'episodio.