SARSA法

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習 半教師あり学習 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

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

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

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

${\displaystyle 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では、エージェントは環境と相互作用し、行われた行動ベースでポリシーを更新する。そのため、オンポリシー型の学習アルゴリズムである。

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

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

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