SARSAとは
SARSA（State-Action-Reward-State-Action）とは、オンポリシー型のTD制御アルゴリズムです。名前の由来は更新に使用する経験タプル（S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}）の頭文字で、現在の状態・行動、報酬、次の状態・行動を使ってQ値を更新します。
SARSAの更新則
SARSAの更新式は Q(s,a) ← Q(s,a) + α[r + γQ(s',a') - Q(s,a)] です。Q学習との違いは、次の状態s'での行動a'として、実際にエージェントが選択した行動を使う点です。Q学習がmax_a' Q(s',a')を使うのに対し、SARSAは方策に従って選択されたa'のQ値を使います。
オンポリシー学習の特徴
SARSAはオンポリシー手法であり、学習に使う方策と学習対象の方策が同じです。これは安全性の面で利点となります。例えばε-greedy方策で学習する場合、SARSAはランダム行動のリスクも考慮した「安全な」方策を学習します。崖歩き問題ではQ学習が崖の縁を歩く最短路を学習するのに対し、SARSAは崖から離れた安全なルートを学習します。
SARSAの変種
Expected SARSAは次状態での全行動のQ値の期待値を用いる変種で、更新のバリアンスが低減されます。n-step SARSAは複数ステップ先まで実際のリターンを使う拡張です。