強化学習について学んでみた。（その19）

昨日はTD学習の考え方について説明した。

今日は方策オン型制御であるSarsa法と、方策オフ型制御であるQ学習について説明していく。

Sarsa法

Sarsa法は方策オン型制御のアルゴリズムの1つで、方策としてソフト方策を使うことで知識利用と探査のバランスをとっていく。

そして、ある状態 $s \in \mathcal{S}$ での行動 $a \in \mathcal{A}(s)$ の価値 $Q_{s, a}$ を、その行動を行って観測された報酬 $r$ と次状態 $s' \in \mathcal{S}$ 、および、その状態で方策に従って選ばれた次行動 $a' \in \mathcal{A}(s')$ の価値 $Q_{s', a'}$ を使って、

と更新する。

この更新を行うときに必要な情報 $s, a, r, s', a'$ を繋げて、Sarsa法、と。

具体的なアルゴリズムは、以下のとおり：

$Q_{s, a}$ を任意に初期化。
以下を繰り返す：
1. $s$ を初期化。
2. $\boldsymbol{Q}$ から導かれるソフト方策を用いて行動 $a$ を選択する。
3. 各ステップについて、以下を繰り返す：
  1. 行動 $a$ を行い、報酬 $r$ と次状態 $s'$ を観測する。
  2. $\boldsymbol{Q}$ から導かれるソフト方策を用いて行動 $a'$ を選択する。
  3. $Q_{s, a}$ を以下のように更新する。
    $Q_{s, a} \leftarrow Q_{s, a} + \alpha \left( r + \gamma Q_{s', a'} - Q_{s, a} \right)$
    ただし、 $s'$ が終端状態の場合、 $Q_{s', a'}$ は0とする。
  4. $s \leftarrow s'$ 、 $a \leftarrow a'$ とする。
  5. $s$ が終端状態なら、繰り返しを終了。

なお、 $\alpha$ はステップサイズ・パラメータで、十分に小さい正の定数とする。

比較的シンプルなアルゴリズムなんだけど、これが意外といい結果を出してくれる。

Q学習

一方、Q学習は方策オフ型制御のアルゴリズムの1つで、推定方策としては決定論的なグリーディ方策、挙動方策としてはソフト方策を用いるアルゴリズムになっている。

状態 $s \in \mathcal{S}$ で挙動方策によって選択された行動 $a \in \mathcal{A}(s)$ を行い、報酬 $r$ と次状態 $s'$ が観測されたとき、推定方策として決定論的なグリーディ方策を用いるので、 $Q_{s', a'} = \mathop{\mbox{max}}_{a \in \mathcal{A}(s')} Q_{s', a}$ となる。
そこで、行動価値 $Q_{s, a}$ を

と更新する。

（なお、なんで「Q」学習なのかは、諸説あるっぽい・・・）

具体的なアルゴリズムは、以下のとおり：

$Q_{s, a}$ を任意に初期化。
以下を繰り返す：
1. $s$ を初期化。
2. 各ステップについて、以下を繰り返す：
  1. $\boldsymbol{Q}$ から導かれるソフトな挙動方策を用いて行動 $a$ を選択する。
  2. 行動 $a$ を行い、報酬 $r$ と次状態 $s'$ を観測する。
  3. $Q_{s, a}$ を以下のように更新する。
    $Q_{s, a} \leftarrow Q_{s, a} + \alpha \left( r + \gamma \mathop{\mbox{max}}_{a' \in \mathcal{A}(s')} Q_{s', a'} - Q_{s, a} \right)$
    ただし、 $s'$ が終端状態の場合、 $\mathop{\mbox{max}}_{a' \in \mathcal{A}(s')} Q_{s', a'}$ は0とする。
  4. $s \leftarrow s'$ とする。
  5. $s$ が終端状態なら、繰り返しを終了。

こちらもSarsa法と同じく比較的シンプルなアルゴリズム。

Sarsa法との違いは、行動価値の推定を改善するときに参照する行動価値で、Sarsa法は推定方策と挙動方策が同じなので、ソフト方策に従って選ばれた次行動の価値を参照するのに対し、Q学習では推定方策と挙動方策が別なので、推定方策（グリーディ方策）に従った現時点で最適と思われる次行動の価値を参照している。

Sarsa法 vs Q学習

では、Sarsa法とQ学習のどちらがいいのか・・・？

これに関しては、本でも明確には言及していない・・・
ただ、「学習中の」収益の平均をとるという比較を行った場合には、Sarsa法の方がいい結果になるみたい。
これは、Sarsa法だと推定方策と挙動方策が同じなので、推定方策の改善が挙動方策の改善にも繋がり、その挙動による収益も向上するのに対し、Q学習では推定方策と挙動方策が異なるので、推定方策が改善されても挙動方策に悪い挙動が紛れたままになる可能性があるからみたい。

あと、個人的な感覚としては、Q学習は最初の方が学習の勢いがいいけど、途中で頭打ちになって学習の進みが悪くなりやすく、一方、Sarsa法の方はゆっくりだけれども着実に学習が進んでいって、最終的には同じ学習回数でQ学習よりもいい性能になっている気がする。
あくまで気がするだけで、ちゃんと比較をしたわけではないのだけど・・・

それと、Q学習の方は推定方策と挙動方策が分かれているので、理論的には解析がしやすいらしい。
そういった意味で、Q学習は重要とのこと。

今日はここまで！