SARSA法のソースを表示

{{Machine learning bar}}
'''SARSA法'''（'''State–Action–Reward–State–Action'''）はマルコフ決定過程でのポリシーを学習するためのアルゴリズムであり、機械学習のサブカテゴリーである[[強化学習]]の分野で使われる。RummeryとNiranjanのテクニカルノート<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2539&rep=rep1&type=pdf Online Q-Learning using Connectionist Systems" by Rummery & Niranjan (1994)]</ref>の中で、「Modified Connectionist Q-Learning(MCQ-L, 修正コネクショニストQ学習)」という名前で提案された。[[:en:Richard_S._Sutton|リチャード・サットン]]により提案された、「SARSA」という名前は、脚注で言及されるに留まった。

このネーミングは、行動価値関数Qの更新アルゴリズムが、現在の状況<math>S_1</math>、現在の行動<math>A_1</math>、行動による報酬<math>R_2</math>、次の状態<math>S_2</math>、その状態で選ぶ行動<math>A_2</math>の5つ組で決まることに由来する。一般化すると、<math>(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})</math>である<ref>[http://incompleteideas.net/book/ebook/node64.html Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto (chapter 6.4)]</ref>。なお、<math>R_{t+1}</math>は報酬の定義によっては、<math>R_t</math>とも書かれるが、リチャード・サットンの『強化学習（第2版）』の表記法に合わせた<ref>{{Cite book
| author    = Richard S. Sutton
| author2   = Andrew G. Barto
| year      = 2018
| title     = Reinforcement Learning, second edition: An Introduction
| publisher = Bradford Books
| isbn      = 978-0262039246
| url       = http://incompleteideas.net/book/the-book-2nd.html
}}
</ref>。

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

: <math>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]</math>

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

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

割引率 <math>0<\gamma<1</math> は、将来の報酬の重要度を決定する。0にすれば、エージェントは日和見主義的、近視眼的<ref>https://www.lesswrong.com/posts/GqxuDtZvfgL2bEQ5v/arguments-against-myopic-training (Retrieved 2021-09-29)</ref>になる。要するに、現在の報酬だけを考慮するようになる。1に近づければ、長期的視野で高い報酬を求めるようになる。1にしたり、1を超えたりすると、Q値は発散してしまう可能性がある。

== 関連項目 ==
* [[強化学習]]
* [[時間差分学習]]（TD学習）
* [[Q学習]]

== 出典 ==
{{Reflist}}

[[Category:強化学習]]
[[Category:機械学習アルゴリズム]]