Q-learning

Q-learning is a model-free approach to active reinforcement learning. It does not need to learn $P(s^{\prime }|s,a)$, instead resolves around notion of a $Q$-value like bandit learning. But instead we learn $Q$-value of state/action pair as opposed to just an action.

$Q(s,a)$ denotes the value of doing $a$ in $s$, so that: $U(s)={\max }_{a}Q(s,a)$

Abstract

We can write $Q(s,a)=R(s)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,a){\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ Which uses the sum over $s^{\prime }$, which can compute estimates of $Q(s,a)$ by running value-iteration style updates but it would not be model-free.

Instead, we write the update rule as: $Q(s,a)\leftarrow Q(s,a)+\alpha (R(s)+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a))$ and recalculate every time $a$ is executed in $s$ and takes the agent to $s^{\prime }$. Where the $a^{\prime }$ are all the actions we know about in $s^{\prime }$.

SARSA

Update rule is: $Q(s,a)\leftarrow Q(s,a)+\alpha (R(s)+\gamma Q(s^{\prime },a^{\prime })-Q(s,a))$ Where $a^{\prime }$ is the actual action taken in $s^{\prime }$.