強化学習の代表的アルゴリズムであるSARSAについて紹介します。
概要（３行で）
- 強化学習の代表的なアルゴリズム
- Q値の更新に遷移先の状態\(s’\)で選択した行動\(a’\)を用いる手法
- Q学習と異なり、Q値の更新に方策を含むため、方策オン型と呼ばれる
基本
強化学習
強化学習は、試行錯誤を通じて得られる報酬を最大化するように行動指針を修正していく、学習フレームワークです。
詳細は以下の記事にまとめています。
強化学習入門
よく用いられる図は以下のような図です。
強化学習エージェント（図中のロボット）は行動\(a\)し、
その行動によって変化した状態\(s\)と報酬\(r\)を観測します。
観測した情報を元に学習を進めていきます。
迷路問題で言えば、
- 環境:迷路
- 状態:マス目(座標)
- 行動:進捗方向(上下左右)
- 報酬:ゴール地点で得られる値
となります。
（これは、一例です。状態、報酬、行動に関しては問題に合わせて設計者が設定します）
Qテーブル
Qテーブルは各状態において各行動を取った時に得られるだろう報酬(期待報酬) を記憶しておくテーブルです。
よく\(Q(s, a)\)と表します。\(Q(s, a)\)は状態\(s\)に対して行動\(a\)を取った時の期待報酬値を意味します。
強化学習エージェントの頭脳といえます。
Q学習等の強化学習では\(Q(s, a)\)を最適化することが目的となります。
以下に、単純な迷路問題での学習したQテーブルの例を示します。
Sがスタート地点、Gがゴール地点、黒が壁を表しています。
強化学習エージェントの目的はSからGまでの経路を求めることです。
各マスを状態\(s\)とし、各状態の各行動\(a\)(矢印)に対する期待報酬値\(Q(s, a)\)(矢印の中の数値)が保存してあります。
ゴールに近づく行動に対しては、高い値となっています。 この値を元に行動選択をすることで、スタート地点からゴール地点までの最短経路を導き出すことができます。
SARSA
SARSAとは
SARSAでは、
Qテーブルの更新時に遷移先の状態\(s’\)における意思決定の結果を用いることが大きな特徴となります。
\(Q(s, a)\)を以下のように更新します。
\begin{eqnarray}
Q(s, a) \leftarrow Q(s, a) + \alpha (r + \gamma Q(s’, a’) – Q(s, a))
\end{eqnarray}
$$
\(Q(s, a)\)の更新時に\(\langle s, a, r, s’, a’ \rangle\) を用いるのでSARSAと呼ばれます。
アルゴリズムは以下のようになります。
- 現在の状態 \(s\)で\(Q(s)\)を元に行動\(a\)の選択（ε-greedyなどを用いて）
- 実際に行動し、状態遷移。遷移先状態\(s’\)と報酬\(r\)の観測
- 遷移先の状態\(s’\)で\(Q(s’)\)を元に次の行動\(a’\)の選択
- \(Q(s, a)\)を、式1を用いて更新(学習)
- 2, 3, 4を\(Q(s, a)\)が収束するまで繰り返す
実装
問題設定
以下のようなマップの迷路問題を扱います。 かなりシンプルなマップになります。
Sはスタート地点はGはゴール地点を表しています。
黒いマスは壁となっています。
状態、行動、報酬は以下の通りです。
- 状態:マス目(座標)
- 行動:上下左右の4択
- 報酬:ゴール地点に着けば100、通常の地点は0、壁や境界線であれば-1の報酬
ソースコード
実験結果
エピソード毎の累積報酬をプロットしました。
(１エピソードはスタート地点からゴールに着くまで)
学習が進むことに高い報酬を得れていることがわかります。
参考文献（教科書）
1.最も古典的な強化学習の教科書です。
2.最近出版された強化学習の教科書です。
3.最近の強化学習の研究等を紹介しています。 教科書としては微妙かもしれませんが、様々な強化学習の発展分野について紹介しています。
コメント
[…] SARSA […]