SARSA法

SARSA法（State–Action–Reward–State–Action）はマルコフ決定過程でのポリシーを学習するためのアルゴリズムであり、機械学習のサブカテゴリーである強化学習の分野で使われる。RummeryとNiranjanのテクニカルノートの中で、「Modified Connectionist Q-Learning(MCQ-L, 修正コネクショニストQ学習)」という名前で提案された。リチャード・サットンにより提案された、「SARSA」という名前は、脚注で言及されるに留まった。

このネーミングは、行動価値関数Qの更新アルゴリズムが、現在の状況$S_{1}$、現在の行動$A_{1}$、行動による報酬$R_{2}$、次の状態$S_{2}$、その状態で選ぶ行動$A_{2}$の5つ組で決まることに由来する。一般化すると、$(S_{t},A_{t},R_{t+1},S_{t+1},A_{t+1})$である。なお、$R_{t+1}$は報酬の定義によっては、$R_{t}$とも書かれるが、リチャード・サットンの『強化学習（第2版）』の表記法に合わせた。

アルゴリズム

状態 $S_{t}$ のエージェントが行動 $A_{t}$ を選び、報酬 $R_{t+1}$ を得て、状態が $S_{t+1}$ に遷移し、その次の行動が $A_{t+1}$ だとする。このとき行動価値関数 $Q(S_{t},A_{t})$ を次の式で更新する。$Q(S_{t},A_{t})$ は $R_{t+1}+\gamma \,Q(S_{t+1},A_{t+1})$ に近づくように学習される。

$Q(S_{t},A_{t})\leftarrow (1-\alpha )Q(S_{t},A_{t})+\alpha \left[R_{t+1}+\gamma \,Q(S_{t+1},A_{t+1})\right]$

SARSAでは、エージェントは環境と相互作用し、行われた行動ベースでポリシーを更新する。そのため、オンポリシー型の学習アルゴリズムである。

学習率 $0<\alpha <1$ は、古い情報を、新しく獲得した情報によってどの程度上書きするかを決定する。0にすれば、エージェントは何も学ばないし、1にすれば、最近の情報だけを近視眼的に考慮するようになる。

割引率 $0<\gamma <1$ は、将来の報酬の重要度を決定する。0にすれば、エージェントは日和見主義的、近視眼的になる。要するに、現在の報酬だけを考慮するようになる。1に近づければ、長期的視野で高い報酬を求めるようになる。1にしたり、1を超えたりすると、Q値は発散してしまう可能性がある。

関連項目

• 強化学習
• 時間差分学習（TD学習）
• Q学習