いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その18)

前回までは、モンテカルロ法について説明していた。

今日からはTD学習(Temporal Difference Learning: 時間的差分学習)について説明していく。

おさらい

まず、強化学習のベースとなる考え方は、Bellman方程式を解いて、ある方策の元での状態や行動の価値を推定し、方策を改善していくというものだった。

状態遷移のモデルが分かっている場合、問題はBellman方程式として記述されるので、方策反復や価値反復を使うことで、これを行っていくことが出来た。
この一連の方法を、動的計画法と呼ぶ。

一方、状態遷移のモデルが分からない場合(普通はその方が多い)、Bellman方程式の係数自体が未知となるので、動的計画法を使うことが出来ない。
そこで、実際に何度も試行をすることで、状態や行動の価値を推定していこうというのが、モンテカルロ法だった。

今日から扱っていくTD学習は、この合いの子とも言えるような方法。
具体的には、実際に何度も試行して、そこから状態や行動の価値を推定していこうというのはモンテカルロ法と同じなんだけど、そのとき、動的計画法と同じように、他の状態や行動の価値を参考にして、状態や行動の価値の推定を行っていく。

TD学習の考え方

まず、モンテカルロ法の説明でも触れたとおり、状態遷移のモデルが分からない状態だと、状態の価値だけを推定しても行動の価値が推定できないので、以下では行動の価値を扱っていくことにする。

方策 \piの元での行動価値 Q_{s, a}^{\pi}というのは、次のように定義されていた:

 {
Q^{\pi}_{s, a} = E \left\{ \left. R_t \right| s_t = s, a_t = a \right\}
}

つまり、ある状態 s \in \mathcal{S}で行動 a \in \mathcal{A}(s)をとったときに、それ以降に得られる報酬の合計(収益)の期待値を、その行動の価値としよう、と。

状態遷移のモデル(遷移や報酬に関する確率)が分かっていれば、この期待値を一次式で書き下すことが出来て、それがBellman方程式を成す式の1つとなる。
そこで、その方程式を解いていくのが動的計画法
一方、モデルが分からない場合、方程式に書き下すことが出来ないので、実際に試行を繰り返すことでこの期待値を得ようというのがモンテカルロ法だった。

ところで、この定義式をちょっと変形していくと、次のような再帰的な表現が得られる:

 {
\begin{align}
Q^{\pi}_{s, a} &= E \left\{ \left. R_t \right| s_t = s, a_t = a \right\} \\
&= E \left\{ \left. \sum_{k=0} \gamma^k r_{t+k+1} \right| s_t = s, a_t = a \right\} \\
&= E \left\{ \left. r_{t+1} + \gamma \sum_{k=0} \gamma^k r_{t+k+2} \right| s_t = s, a_t = a \right\} \\
&= E \left\{ \left. r_{t+1} + \gamma Q_{s_{t+1}, a_{t+1}}^{\pi} \right| s_t = s, a_t = a \right\}
\end{align}
}

この表現の意味するところは、「ある状態で行動を行ったとき、その行動の価値は、その行動で得られた報酬と次の状態で(方策に従って)行った行動の価値の和の期待値」ということになる。
そこで、ある行動を行って、報酬と次の状態と行動を観測したタイミングで「報酬と次の状態での行動の価値」をサンプリングし、それを何度も繰り返すことで期待値に収束させていくという方法を考えることが出来る。
これがTD学習の考え方となる。

この考え方に基づいて行動価値の推定を改善させようとしたとき、シンプルに平均をとるという考え方を使うと、 k回目に報酬 rと次の状態行動対 (s', a')が観測されたときに、行動価値 Q_{s, a}

 {
Q_{s, a} \leftarrow \frac{(k - 1) Q_{s, a} + \left( r + \gamma Q_{s', a'} \right)}{k}
}

と改善させることになるけれど、この式をちょっと変形すると、

 {
Q_{s, a} \leftarrow Q_{s, a} + \frac{1}{k} \left( r + \gamma Q_{s', a'} - Q_{s, a} \right)
}

という表現が得られ、これは「1テンポ後に観測された価値( r + \gamma Q_{s', a'})と現在の推定価値( Q_{s, a})の差分を、ある程度の重みをつけて現在の推定価値に足し込む」と読むことが出来る。
すなわち、時間的な価値の差分を使って学習を行う、と。
それゆえ、Temporal Difference(時間的差分)学習と呼ばれるのだと思う。
(明確には書かれてないので、確証はないけど・・・)

一般には、差分につける重みとして \frac{1}{k}が使われることよりも、十分に小さな正の数 \alphaが使われることが多いので、TD学習での行動価値の推定の改善は、次のように表されることが多い:

 {
Q_{s, a} \leftarrow Q_{s, a} + \alpha \left( r + \gamma Q_{s', a'} - Q_{s, a} \right)
}

この \alphaのことをステップサイズ・パラメータと呼んだりする。

TD学習のいいところ

さて、そんなTD学習だけれど、モンテカルロ法に比べて何が嬉しいのかというと、

  • 終端状態になるまで学習を行うのを待つ必要がない
  • 他の行動の価値を使って学習を行うことが出来る

という点。

まず、前者。

モンテカルロ法の場合、終端状態にならないと収益が確定しないので、学習を開始することが出来なかった。
けど、TD学習の場合、次の状態行動対を観測出来た時点で学習を行うことが出来るので、細かく学習を進めていくことが出来る。
これは特に、終端状態が存在しないようなタスクの場合(機械の制御とかだとそういうことがけっこうある)、決定的な差となってくる。

ちょっと気になることとしては、モンテカルロ法の場合、学習さえ行われれば得られた報酬が先頭まですぐ伝わるのに対し、TD学習ではその情報が先頭まで伝達されるのにかなりの時間がかかりそうだということ。
これは実際そうなんだけど、これに関してはTD( \lambda)という拡張を考えることで対処出来る。
(TD( \lambda)については、そのうち説明する)

そして、後者。

このように、他の状態/行動の価値を使ってある状態/行動の価値を学習することを、強化学習ではブートストラップと呼んでいるようなのだけど、経験的に、ブートストラップを使った学習の方が性能がいいことが多いらしい。
おそらくだけど、単純に考えて使える情報の数が多くなっている(モンテカルロ法だと使える情報はその試行での収益情報だけなのに対し、ブートストラップを行った場合はそれまで得られた経験すべてが反映されている情報を使うことが出来る)ので、より性能がよくなるのだと思う。

なお、動的計画法も他の状態の価値を使って価値の更新を行っているので、ブートストラップを使った学習の1つになっている。

方策オン型制御と方策オフ型制御

さて、TD学習についても、方策が決定論的だと、探査が行われない状態行動対が出てきてしまうことが考えられる。
そこで、知識利用と探査をバランス良く行うために、工夫が必要になってくる。

その工夫にはやはり方策オン型制御と方策オフ型制御とがあり、方策オン型制御のアルゴリズムの1つとして、Sarsa法がある。
また、方策オフ型制御の1つとして、Q学習がある。

これらについては、明日以降説明していく。

今日はここまで!

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る