Sarsa

Definition

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$ Sarsa learns $Q^{\pi }$ by using Bellman Expectation Equation. The both behavior and target policies of Sarsa is derived from $Q$, so it is an on-policy method.

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S),Q(s,a)$ arbitrarily, and $Q(\text{terminal},\cdot )=0$.
2. Repeat for each episode:
   1. Initialize $S$.
   2. Choose an action $A$ from the initial state $S$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
   3. Repeat for each step of an episode until $S$ is terminal:
      1. Take the action $A$ and observe a reward $R$ and a next state $S^{\prime }$.
      2. Choose an action $A^{\prime }$ from the next state $S^{\prime }$ using policy derived from $Q$ (e.g. $ϵ$-greedy).
      3. $Q(S,A)\leftarrow Q(S,A)+\alpha [R+\gamma Q(S^{\prime },A^{\prime })-Q(S,A)]$
      4. Update $S\leftarrow S^{\prime }$ and $A\leftarrow A^{\prime }$